HashMap底层原理（图文并茂，简单易懂）_hashmap底层实现原理

大家先看下这张图片：

1、HashMap是基于哈希表实现的，而哈希表的底层是数组加上链表的形式。

2、数组内存连续查询效率高，链表内存分散增删改效率高，哈希表采用此种存储数据的形式极大的提高操作数据的效率。

3、哈希表的默认长度是16，编号从0开始。图中编号0-4的长方形代表了一个数组，箭头指向的代表了一个一个的链表。

 

HashMap存储数据原理

1、用HashMap存储数据（ put(key，value) ）时，会先操作key调用.hashcode（）方法得出hash值，然后再通过哈希算法转换成数组的一个下标，对应的就是在数组上的的存储位置。

2、如果该位置没有数据，则直接存储。如果该位置有数据，则会发生数据碰撞。

3、数据碰撞的时候遍历该位置上链表中的所有数据，并且通过equals()方法来比对每个数据的key。如果key相同的话，会将链表上该位置的数据进行覆盖。如果key不相同的话，在JDK1.8之前是实行的头插法，数据存储在链表头部，1.8之后实行的是尾插法数据存储在链表尾部。

4、JDK1.8之后，当链表上的节点个数（数据个数）大于等于8时并且数组长度不小于64的时候，链表数据结构自动进行树化转化成红黑树，当链表上的数据小于8个时，又会自动退化成链表

5、如果数组的长度小于64的话链表数据个数达到了8的话也不会转化成红黑树，而是先进行扩容，直到数组长度达到64

6、HashMap默认的数组长度是16，扩容的话有两种情况：
1）一种是数组上的元素达到了阈值，16*默认负载因子0.75，也就是12个元素的时候，数组长度扩容为两倍32，阈值变为24
2）还有一种是在没有红黑树的情况下，添加元素后数组中某个链表的长度超过了8，数组会扩容为两倍（比如创建HashMap集合后刚开始添加元素全都在一个链表中，当链表长度是9的时候数组扩容成32，链表长度是10的时候数组扩容成64，此时再添加元素，满足了数组长度为64链表长度到达8的两个条件，链表转换成红黑树）