java集合之HashMap底层实现原理

    Map集合是java集合中比较常用的一个，它下面比较常用的有HashMap、HashTable、ConcurrentHashMap等。今天我们重点讲一下HashMap的底层实现原理。

    HashMap是一个用来存储key-value键值对的集合，每个键值对称组成一个Entry实体。Entry类是一个单向链表结构，它里面存储着hash值、key、value和next。如下图

    这些Entry分散存储在一个数组中。因此，HashMap底层是由数组+链表组成的。HashMap初始容量为16，即数组的长度为16， 填充因子为0.75.当数组长度不满足时，扩容长度为当前的一倍。如下图

    由上图可以发现，长度为16的数组中的每个元素（Entry）存储的是一个链表的头节点。当一个Entry需要存储到数组时，需要计算Entry中key的hash值来确定存储到数组中的位置。如果数组中当前的位置己经有值，刚新插入的Entry会存放到当前位置的最前面，新的Entry的next会存储下一个Entry的地址。取值时也是通过Entry中key的hash值来找到所存储到数据的位置，然后顺着对应链表的头切点一个一个的向下查找，直到找到结果为止。

    可以举一个简单的例子来说明HashMap是如何存储Entry的。

    例如第一个键值对A要存储进来，通过对其key通过hash算法获取当插入到数组的下标为index=2，则：Entry[2]=A.见图一。

当第二个键值对B要存储进来，通过对其key通过hash算法获取当插入到数组的下标也为index=2，因此当前数组中下标为2的己经有了A，HashMap会将B.next=A，Entry[2]=B.见图二

当第三个键值对C要存储进来，存储位置任然为数组下标为2的位置时，同理C.next=B,Entry[2]=C.最后我们发现index=2的地方己存储了三个键值对：C、B、A。它们是通过键值对的next这个属性连在一起的。也就是说数组存储的是最后插入的元素。

图一：

图二：