面试之HashMap

原理

HashMap基于Hash算法,我们通过put(key,value)存储,get(key)来获取。当传入key时,HashMap会根据key.hashCode()计算出hash值,根据hash值将value保存在bucket里。当数据多的时候肯定会有计算出来的hash值是相同的,这时候发生hash冲突。当数据过多的时候也会自动扩容。

hash冲突

jdk1.8之前:数组加链表,hash冲突它会将相同hash值的value追加到链表后面,然后去遍历它。

jdk1.8之后:数组加链表加红黑树,引入了一个阈值,那么当大于默认阈值8的时候,它就会将链表变成一个红黑树。

自动扩容

如果在初始化HashMap中没有指定初始容量,那么默认容量为16,负载因子是0.75,如果后来HashMap中存放的数量超过了16×0.75=12的时候,HashMap便会调用resize()方法,扩大为原来的2倍(2的n次幂)。

线程不安全

扩容引发的线程不安全:

jdk1.8之前,它会调用到transfer()方法,采用头插法的形式,头插法会将链表的顺序翻转,会形成死循环以及数据丢失的问题。

jdk1.8之后,就没有transfer()方法了,采用了尾插法的形式,在并发执行put操作时会发生数据覆盖的情况。

如何保证线程安全

首用CurrentHashMap,也可以用HashTable、加锁、Collections.

版权声明:玥玥 发表于 2021-05-18 4:36:19。
转载请注明:面试之HashMap | 女黑客导航