一、HashMap实现原理
JDK1.7之前:HashMap由数组+链表组成。
JDK1.8之后:HashMap由数组+链表、红黑树组成,当链表长度超过8,且
二、HashMap中put()方法的过程
①首先检查数组table是否为空, 为空的话通过resize()方法进行创建。
②接着通过Hash函数计算key应该插入当数组的位置判断table[i]是否为空,为空的情况下直接插入,不为空的话判断table[i]的链表或树中是否有key,有key的话进行覆盖,没有的话进行插入操作,
③插入后如果为链表,需要判断是否长度大于8且table数组长度大于64,如果是的话转为红黑树
④size++,判断size大小是否大于threshold(负载因子 * table数组长度),如果大于的话,resize()方法进行扩容。
三、HashMap为什么是线程不安全的
jdk1.7之前:HashMap链表的插入的方式是是头插法,在多线程的情况下,容易产生环形链表,查询时就会产生死循环问题。
jdk1.8之后:HashMap的插入法改为了尾插法,但是多线程情况下依然会产生一些问题,例如前面说到的put()操作,有可能产生覆盖的情况。
比如A、B两个线程put()插入同一个HashMap数组的位置,如果A操作判断该位置为null后时间片结束,那么B插入时该位置仍为空,会直接插入,当A线程继续执行插入操作时,该位置B插入的数据就会被覆盖掉了。
四、HashMap实现线程安全的几种形式
①HashTable
不推荐,HashTable将几乎所有方法都使用了synchronized加锁,效率较低
②ConcurrentHashMap
jdk1.7之前:将数据分成一段一段(Segment),每一段数据配一把锁,Segment 继承了ReentrantLock 所以Segment 是一种可重入锁。一个Segment包含一个HashEntry的数组。
jdk1.8之后:取消了Segment分段锁,使用Node + CAS + synchronized,其中synchronized只锁红黑树或者链表的头结点,锁的粒度更细,效率更高。
五、HashMap的扩容机制
HashMap的默认负载因子是0.75,当元素个数 > 0.75 * 数组长度时,开始扩容,数组长度变为之前的2倍。
六、HashMap为什么采用2倍扩容
在解答这个问题之前,我们要知道二进制的取模 % 运算可以视为 & 运算。 向HashMap插入一个val值时,判断该val应该处于数组哪个位置的方法就是 val %( length - 1)。
因此,HashMap的2倍会使得扩容后更新数据位置非常容易。比如当前HashMap的length为8,二进制为1000, length - 1 为 111,2倍扩容后,length扩大到16.只需要左移一位变为10000, length - 1是1111。对于需要更新位置的val,只需要多%1位就可以了,这一位就是length-1新增的那个位置,如果val的该位为0,那么val % length - 1的值也不会变,位置不需要变化;如果该位为1,那么val的位置只需要增加数组扩大的长度即可。
hash = 10101100
length - 1 = 111
index = 100
扩容后:
hash = 10101100
length - 1 = 1111
index = 1100