HashMap的底层实现原理

HashMap的底层实现原理

一、HashMap的底层实现原理

HashMap 在 JDK1.8 之前的实现方式：数组+链表
JDK1.8之后的实现方式：数组+链表+红黑树

原理：

当你 new 一个 HashMap() 的时候，它底层并没有创建数组。
/
只有当你首次调用 put() 方法时，底层就会创建一个长度为16的数组
/
用数组容量大小乘以加载因子得到一个阈值，一旦数组中存储的元素个数超过该阈值就会进行扩容，通过 rehash() 方法将数组容量增加到原来的两倍，在做扩容的时候会生成一个新的数组，原来的所有数据需要重新计算哈希码值重新分配到新的数组，所以扩容的操作非常消耗性能。

不同的对象算出来的数组下标是相同的这样就会产生 hash 冲突

二、为什么加载因子设置为0.75，初始化临界值是12？

默认的数组大小为16，加载因子为0.75

0.75是对空间和时间效率的一种平衡选择。
/
如果负载因子小一些比如是0.4，那么初始长度16*0.4=6，数组占满6个空间就进行扩容，很多空间可能元素很少甚至没有元素，会造成大量的空间被浪。
/
如果负载因子大一些比如是0.9，这样会导致扩容之前查找元素的效率非常低。
/
oadfactory设置为0.75是经过多重计算检验得到的可靠值，可以最大程度的减少rehash的次数，避免过多的性能消耗。

三、HashMap的判断机制

当链表长度超过8的时候，此时会继续判断哈希表的长度是否小于64。
/
如果小于64，会扩容，如果大于等于64，就会将链表转换为红黑树，提高查询的效率。
/
当红黑树节点小于等于6时又会退化为链表。

四、map.put实现原理

首先通过k的hashCode()方法得出哈希值，通过哈希算法转为数组下标。
/
如果数组下标位置没有元素，就直接添加元素。如果下标对应位置上有链表的话，就会拿k跟链表上所有的k进行equals比较，如果都返回false，就将新元素追加到链表的尾部。
/
如果其中有一个equals返回true，就会将这个节点的value覆盖

五、map.get实现原理

首先通过k的hashCode()方法得出哈希值，通过哈希算法转为数组下标。
/
如果数组下标位置没有元素，就直接返回null。如果下标位置上有链表的话，就会拿k跟链表上所有的k进行equals比较，如果都返回false，就直接返回null。
/
如果有一个返回true，就返回这个节点的value值。