最新面试题集锦（14）

基础题

（1）TreadLocal的用途，以及实现原理，使用的时候需要注意什么？

threadlocalMap进行存储键值 每个ThreadLocal类创建一个Map，然后用线程的ID作为Map的key，实例对象作为Map的value，这样就能达到各个线程的值隔离的效果。 ThreadLocal的作用是提供线程内的局部变量，这种变量在线程的生命周期内起作用，减少同一个线程内多个函数或者组件之间一些公共变量的传递的复杂度。线程之间的threadLocal变量是互不影响的，使用private final static进行修饰，防止多实例时内存的泄露问题线程池环境下使用后将threadLocal变量remove掉或设置成一个初始值

（2）如何实现负载均衡，有哪些算法可以实现？

1、轮询调度
 　　轮询调度算法就是以轮询的方式依次将请求调度到不同的服务器，即每次调度执行i = (i + 1) mod n，并选出第i台服务器。算法的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调度。
 　 2、最小连接调度
 　　最小连接调度算法是把新的连接请求分配到当前连接数最小的服务器。最小连接调度是一种动态调度算法，它通过服务器当前所活跃的连接数来估计服务器的负载情况。
 　　在实际实现过程中，一般会为每台服务器设定一个权重值，这就是加权最小连接
 　　3、 基于局部性的最少链接(LBLC)
 　　基于局部性的最少链接调度(以下简称为LBLC)算法是针对请求报文的目标IP地址的负载均衡调度，目前主要用于Cache集群系统，因为在Cache集群中客户请求报文的目标IP地址是变化的。
 　　LBLC调度算法先根据请求的目标IP地址找出该目标IP地址最近使用的服务器，若该服务器是可用的且没有超载，将请求发送到该服务器; 若服务器不存在，或服务器超载或有服务器处于其一半的工作负载，则用“最少链接”的原则选出一个可用的服务器，将请求发送到该服务器。 
 　　4、带复制的基于局部性最少链接(LBLCR)
 　　带复制的基于局部性最少链接调度以下简称为LBLCR)算法也是针对目标IP地址的负载均衡，目前主要用于Cache集群系统。它与LBLC算法的不同之处是它要维护从一个目标IP地址到一组服务器的映射，而LBLC算法维护从一个目标IP地址到一台服务器的映射。
 　　LBLCR调度算法将“热门”站点映射到一组Cache服务器(服务器集合)，当该“热门”站点的请求负载增加时，会增加集合里的Cache服务器，来处理不断增长的负载; 当该“热门”站点的请求负载降低时，会减少集合里的Cache服务器数目。
 　　5、目标地址散列调度
 　　目标地址散列调度算法是针对目标IP地址的负载均衡，但它是一种静态映射算法，通过一个散列(Hash)函数将一个目标IP地址映射到一台服务器。
 　　目标地址散列调度算法先根据请求的目标IP地址，作为散列从静态分配的散列表找出对应的服务器，若该服务器是可用的且未超载，将请求发送到该服务器，否则返回空。
 　　6、 源地址散列调度
 　　和目标地址散列调度类似，唯一的区别是按照源地址为散列函数的散列键。 

算法题

（1）有一亿个数字，其中有2个是最重要的，快速找到它，时间和空间都要最优。

通过计数排序联想到
原理：把数字值直接映射到数组下标（时间最优），这里重复的数字只有两次，为了空间最优，就用bit来表示（只有0和1），1byte=8bit，一个byte可以存储8个数字的计数。
所以建立数组 byte[] bucket=new byte[(最大值-最小值)/8+1];

public class Test{
    public static void main(String[] args){
        long time=new Date().getTime();
        int[] arr=new int[100000000];//1亿长度
        for(int i=0;i<arr.length;i++){
            arr[i]=i+1;
        }
        arr[99999999]=2020;
        int min=arr[0];
        int max=arr[0];
        for(int i=0;i<arr.length;i++){
            if(arr[i]<min)
                min=arr[i];
            if(arr[i]>max)
                max=arr[i];
        }
        byte[] bucket=new byte[(max-min)/8+1];
        for(int i=0;i<arr.length;i++){
            int num=arr[i];
            int j=(num-min)/8;
            int k=(num-min)%8;
            if(((bucket[j]>>k)&1)>0){//重复了
                System.out.println("Number of repeats："+num);
                break;
            }else{
               bucket[j]|=(1<<k);
            }
        }
        long time2=new Date().getTime();
        System.out.println("millisecond:"+(time2-time));
    }
}

关注 易学在线 公众号

每日更新大量优质技术文档
第一时间获知最新上架课程
与众多大数据猿分享与交流