hashMap的底层原理

1.谈一下hashMap中put是如何实现的？

- 根据传入的key,计算hash值,调用对象.hashCode()获取. 进行高16位和低16位进行扰动计算.

- 判断成员变量table是否为空,如果为空,说明该还没有初始化.

- 调用resize进行初始化,初始化默认长度为16,拓容阈值为16*0.75. 如果构造方法指定了数组的长度,按照指定的来(如果输入的长度不是2的幂次方,默认找到离传入值最近的2的幂次方的数值作为数组的长度)

- 使用hash & (数组长度-1) 等于求模取余 ,计算当前元素需要存放的索引位置

- 当前位置的元素为空

- 创建Node对象,将key,value,hash值存储到对象中

- 当前位置的元素不为空

- 判断当前传入的元素和数组位置上的元素是否相同元素(1.判断hash值是否相等2.判断内存地址或者equals相等),如果是相同对象,把旧的值取出,将新的值覆盖,返回旧的值

- 判断当前节点是否TreeNode对象,如果是,说明当前节点已经是红黑树,元素往红黑树中添加元素

- 遍历链表,判断链表上的元素是否和当前传入的元素时相同元素,如果是相同对象,把旧的值取出,将新的值覆盖,返回旧的值,如果不是,已经达到链表尾部,在链表尾部插入元素,返回null.

- 如果链表大于8,但数组长度小于64,仅仅进行拓容,不会转成红黑树

- 如果链表大于8,但数组长度大于64,转成红黑树

- 将链表变成双向链表,然后再转成红黑树.

2.谈一下hashMap中什么时候需要进行扩容，扩容resize()又是如何实现的？

- 添加的元素大于拓容阈值

- 如果链表大于8,但数组长度小于64

扩容resize()

- 数组长度变成原数组长度两倍.

- 遍历旧数组,将旧数组上的元素迁移到新数组上.

- 原数组的位置上的元素为null

- 原数组的位置上的元素只有一个,重新计算索引位置,将这个元素转移过去.

- 原数组的位置上是链表,将链表拆分成高位链表和低位链表,低位链表放入新数组j位置,高位链表放入新数组j+旧数组长度位置

- 原数组的位置上是红黑树

- 将双向链表,拆分成高位链表和低位链表

- 所有的元素都在低位链表,依然是原来的红黑树,直接将对应树的根节点. 直接放入到新数组j的位置

- 所有的元素都在低位链表,依然是原来的红黑树,直接将对应树的根节点. 直接放入到新数组j+旧数组长度的位置

- 高位和低位链表都有元素的情况

- 链表的长度小于6,直接退化成单向链表.

- 链表的长度大于6,将双向链表重新生成新的红黑树,然后放入到对应的位置中.

3.为什么不直接将key作为哈希值而是与高16位做异或运算？

防止用户的hash函数写得不好,导致哈希冲突激烈,进行高16和低16异或运算,可以让生成hash值分布更加均匀.

4.为什么是16？为什么必须是2的幂？如果输入值不是2的幂比如10会怎么样？

源码默认就是16. 源码使用 hash & (数组长度-1) 代替 hash % 数组长度 ,这个等式的前提,数组长度必须要是2的幂次方.

如果输入值不是2的幂比如10会怎么样,找离他最近的2的幂次方的值作为数组长度

HashMap map = new HashMap(10000);

for(int i = 0;i<100001;i++){

map.put(i,"") ===>执行10001,进行了几次拓容?

}

5.谈一下当两个对象的hashCode相等时会怎么样？

判断是否同一个对象

如果内存地址相同或者equals相同,说明同一个对象.替换值.

6.如果两个键的hashcode相同，你如何获取值对象？

如果内存地址相同或者equals相同,说明同一个对象,返回值

如果不相同,继续顺着链表往后寻找,或者在红黑树寻找

7.如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

进行拓容,默认负载因子的值为0.75

8.请解释一下HashMap的参数loadFactor，它的作用是什么？

描述HashMap拥挤程度,大于这个值对应容量,进行拓容 *** 作.

9.传统HashMap的缺点(为什么引入红黑树？

链表在特殊情况下,时间复杂度比较高.