java面试汇总(二)

8、拉链法导致的链表过深问题为什么不用二叉查找树代替&＃xff0c;而选择红黑树&＃xff1f;为什么不一直使用红黑树&＃xff1f;
之所以选择红黑树是为了解决二叉查找树的缺陷&＃xff0c;二叉查找树在特殊情况下会变成一条线性结构&＃xff08;这就跟原来使用链表结构一样了&＃xff0c;造成很深的问题&＃xff09;&＃xff0c;遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋&＃xff0c;右旋、变色这些操作来保持平衡&＃xff0c;引入红黑树就是为了查找数据快&＃xff0c;解决链表查询深度的问题&＃xff0c;我们知道红黑树属于平衡二叉树&＃xff0c;但是为了保持“平衡”是需要付出代价的&＃xff0c;但是该代价所损耗的资源要比遍历线性链表要少&＃xff0c;所以当长度大于8的时候&＃xff0c;会使用红黑树&＃xff0c;如果链表长度很短的话&＃xff0c;根本不需要引入红黑树&＃xff0c;引入反而会慢。

9、 说说你对红黑树的见解&＃xff1f;

1、每个节点非红即黑
2、根节点总是黑色的
3、如果节点是红色的&＃xff0c;则它的子节点必须是黑色的&＃xff08;反之不一定&＃xff09;
4、每个叶子节点都是黑色的空节点&＃xff08;NIL节点&＃xff09;
5、从根节点到叶节点或空子节点的每条路径&＃xff0c;必须包含相同数目的黑色节点&＃xff08;即相同的黑色高度&＃xff09;

10、解决hash 碰撞还有那些办法&＃xff1f;
开放定址法。
当冲突发生时&＃xff0c;使用某种探查技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找&＃xff0c;直到找到给定的地址。
按照形成探查序列的方法不同&＃xff0c;可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
下面给一个线性探查法的例子　　
问题&＃xff1a;已知一组关键字为(26&＃xff0c;36&＃xff0c;41&＃xff0c;38&＃xff0c;44&＃xff0c;15&＃xff0c;68&＃xff0c;12&＃xff0c;06&＃xff0c;51)&＃xff0c;用除余法构造散列函数&＃xff0c;用线性探查法解决冲突构造这组关键字的散列表。
解答&＃xff1a;为了减少冲突&＃xff0c;通常令装填因子α由除余法因子是13的散列函数计算出的上述关键字序列的散列地址为(0&＃xff0c;10&＃xff0c;2&＃xff0c;12&＃xff0c;5&＃xff0c;2&＃xff0c;3&＃xff0c;12&＃xff0c;6&＃xff0c;12)。
前5个关键字插入时&＃xff0c;其相应的地址均为开放地址&＃xff0c;故将它们直接插入T[0]&＃xff0c;T[10)&＃xff0c;T[2]&＃xff0c;T[12]和T[5]中。
当插入第6个关键字15时&＃xff0c;其散列地址2(即h(15)&＃61;15&＃xff05;13&＃61;2)已被关键字41(15和41互为同义词)占用。故探查h1&＃61;(2&＃43;1)&＃xff05;13&＃61;3&＃xff0c;此地址开放&＃xff0c;所以将15放入T[3]中。
当插入第7个关键字68时&＃xff0c;其散列地址3已被非同义词15先占用&＃xff0c;故将其插入到T[4]中。
当插入第8个关键字12时&＃xff0c;散列地址12已被同义词38占用&＃xff0c;故探查hl&＃61;(12&＃43;1)&＃xff05;13&＃61;0&＃xff0c;而T[0]亦被26占用&＃xff0c;再探查h2&＃61;(12&＃43;2)&＃xff05;13&＃61;1&＃xff0c;此地址开放&＃xff0c;可将12插入其中。

类似地&＃xff0c;第9个关键字06直接插入T[6]中&＃xff1b;而最后一个关键字51插人时&＃xff0c;因探查的地址12&＃xff0c;0&＃xff0c;1&＃xff0c;…&＃xff0c;6均非空&＃xff0c;故51插入T[7]中。

11、如果HashMap的大小超过了负载因子(load factor)定义的容量&＃xff0c;怎么办&＃xff1f;

默认的负载因子大小为0.75&＃xff0c;也就是说&＃xff0c;当一个map填满了75%的bucket时候&＃xff0c;和其它集合类(如ArrayList等)一样&＃xff0c;将会创建原来HashMap大小的两倍的bucket数组&＃xff0c;来重新调整map的大小&＃xff0c;并将原来的对象放入新的bucket数组中。这个过程叫作rehashing&＃xff0c;因为它调用hash方法找到新的bucket位置。这个值只可能在两个地方&＃xff0c;一个是原下标的位置&＃xff0c;另一种是在下标为<原下标&＃43;原容量>的位置

12、重新调整HashMap大小存在什么问题吗&＃xff1f;
当重新调整HashMap大小的时候&＃xff0c;确实存在条件竞争&＃xff0c;因为如果两个线程都发现HashMap需要重新调整大小了&＃xff0c;它们会同时试着调整大小。在调整大小的过程中&＃xff0c;存储在链表中的元素的次序会反过来&＃xff0c;因为移动到新的bucket位置的时候&＃xff0c;HashMap并不会将元素放在链表的尾部&＃xff0c;而是放在头部&＃xff0c;这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了&＃xff0c;那么就死循环了。(多线程的环境下不使用HashMap&＃xff09;
为什么多线程会导致死循环&＃xff0c;它是怎么发生的&＃xff1f;
HashMap的容量是有限的。当经过多次元素插入&＃xff0c;使得HashMap达到一定饱和度时&＃xff0c;Key映射位置发生冲突的几率会逐渐提高。这时候&＃xff0c;HashMap需要扩展它的长度&＃xff0c;也就是进行Resize。1.扩容&＃xff1a;创建一个新的Entry空数组&＃xff0c;长度是原数组的2倍。2.ReHash&＃xff1a;遍历原Entry数组&＃xff0c;把所有的Entry重新Hash到新数组。
&＃xff08;这个过程比较烧脑&＃xff0c;暂不作流程图演示&＃xff0c;有兴趣去看看我的另一篇博文"HashMap扩容全过程"&＃xff09;
达摩&＃xff1a;哎呦&＃xff0c;小老弟不错嘛~~意料之外呀
小鲁班&＃xff1a;嘿嘿&＃xff0c;优秀吧&＃xff0c;中场休息一波&＃xff0c;我先喝口水
达摩&＃xff1a;不仅仅是这些哦&＃xff0c;面试官还会问你相关的集合类对比&＃xff0c;比如&＃xff1a;

13、HashTable
数组 &＃43; 链表方式存储
默认容量&＃xff1a; 11(质数 为宜)
put:

• 索引计算 : &＃xff08;key.hashCode() & 0x7FFFFFFF&＃xff09;% table.length
  若在链表中找到了&＃xff0c;则替换旧值&＃xff0c;若未找到则继续
  当总元素个数超过容量*加载因子时&＃xff0c;扩容为原来 2 倍并重新散列。
  将新元素加到链表头部
  对修改 Hashtable 内部共享数据的方法添加了 synchronized&＃xff0c;保证线程安全。

14、HashMap &＃xff0c;HashTable 区别
默认容量不同。扩容不同
线程安全性&＃xff0c;HashTable 安全
效率不同 HashTable 要慢因为加锁
15、ConcurrentHashMap 原理
1、最大特点是引入了 CAS&＃xff08;借助 Unsafe 来实现【native code】&＃xff09;
CAS有3个操作数&＃xff0c;内存值V&＃xff0c;旧的预期值A&＃xff0c;要修改的新值B。当且仅当预期值A和内存值V相同时&＃xff0c;将内存值V修改为B&＃xff0c;否则什么都不做。
Unsafe 借助 CPU 指令 cmpxchg 来实现
使用实例&＃xff1a;

1、对 sizeCtl 的控制都是用 CAS 来实现的 1、sizeCtl &＃xff1a;默认为0&＃xff0c;用来控制 table 的初始化和扩容操作。
-1 代表table正在初始化 N 表示有 -N-1 个线程正在进行扩容操作 如果table未初始化&＃xff0c;表示table需要初始化的大小。 如果table初始化完成&＃xff0c;表示table的容量&＃xff0c;默认是table大小的0.75倍&＃xff0c;居然用这个公式算0.75&＃xff08;n - (n >>> 2)&＃xff09;。
CAS 会出现的问题&＃xff1a;ABA
对变量增加一个版本号&＃xff0c;每次修改&＃xff0c;版本号加 1&＃xff0c;比较的时候比较版本号。

16、我们可以使用CocurrentHashMap来代替Hashtable吗&＃xff1f;

我们知道Hashtable是synchronized的&＃xff0c;但是ConcurrentHashMap同步性能更好&＃xff0c;因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable&＃xff0c;但是HashTable提供更强的线程安全性。它们都可以用于多线程的环境&＃xff0c;但是当Hashtable的大小增加到一定的时候&＃xff0c;性能会急剧下降&＃xff0c;因为迭代时需要被锁定很长的时间。因为ConcurrentHashMap引入了分割(segmentation)&＃xff0c;不论它变得多么大&＃xff0c;仅仅需要锁定map的某个部分&＃xff0c;而其它的线程不需要等到迭代完成才能访问map。简而言之&＃xff0c;在迭代的过程中&＃xff0c;ConcurrentHashMap仅仅锁定map的某个部分&＃xff0c;而Hashtable则会锁定整个map。
此时躺着床上的张飞哄了一声&＃xff1a;睡觉了睡觉了~

见此不太妙&＃xff1a;小鲁班立马回到床上&＃xff08;泉水&＃xff09;&＃xff0c;把被子盖过头&＃xff0c;心里有一丝丝愉悦感&＃xff0c;不对。好像还没洗澡。。。

by the way
CocurrentHashMap在JAVA8中存在一个bug&＃xff0c;会进入死循环&＃xff0c;原因是递归创建ConcurrentHashMap 对象&＃xff0c;但是在1.9已经修复了,场景重现如下

public class ConcurrentHashMapDemo{private Map cache &＃61;new ConcurrentHashMap<>(15);public static void main(String[]args){ConcurrentHashMapDemo ch &＃61; new ConcurrentHashMapDemo();System.out.println(ch.fibonaacci(80));}public int fibonaacci(Integer i){if(i&＃61;&＃61;0||i &＃61;&＃61;1) {return i;}return cache.computeIfAbsent(i,(key) -> {System.out.println("fibonaacci : "&＃43;key);return fibonaacci(key -1)&＃43;fibonaacci(key - 2);});}
}