HashMap内部实现原理(简述)

HashMap内部实现原理

HashMap表面上是由key-value对组成的,key具有唯一性.
而HashMap在内部实现时运用了数组以及链表.
初始数组长度为16.

[ 0 ]——>{k-v}->{k-v}->{k-v}  
[ 1 ]——>{k-v}->{k-v}  
[ 2 ]  
[ 3 ]  
[ 4 ]——>{k-v}  
[ 5 ]  
[ 6 ]——>{k-v}->{k-v}->{k-v}  
[ 7 ]  
[ 8 ]——>{k-v}->{k-v}  
[ 9 ]  
[ 10]  
[ 11]——>{k-v}->{k-v}->{k-v}  
[ 12]  
[ 13]——>{k-v}  
[ 14]  
[ 15]——>{k-v}  

其中,
数组[ ]叫做table.
{k-v}->{k-v}叫做链表.
{k-v}在链表中叫做Node,在Map中叫做Entry.

那么,如何将一个键值对加入这样一个数据结构？

1.如果键为null,加入[0]号链表,如果链表中里有该键,覆盖其value,否则直接加入链表.
2.如果键不为null,进行hashcode(key),并将这个数与这个数无符号右移16位进行异或(保证所有位参与运算,更加离散)
3.将异或得到的数与0xF相与,得到4bit有效值,用来表示0～15.来确定键值对所加入的链表.
4.如果所加入的链表为空,直接加入链表,如果链表中有该键,覆盖其value.
这样即保证了散列性,又保证了键的唯一性。