HashMap的底层工作原理(详细版)

前言：HashMap的一些特性：譬如HashMap可以接受null键值和值，而HashTable则不能；HashMap是非synchronized;HashMap很快；以及HashMap储存的是键值对等等这一些都是必须知道的。下面来深入了解HashMap的底层工作原理：

1 HashMap 的存储机制
a在 Java 1.8 中，如果链表的长度超过了 8且数组长度最小要达到64 ，那么链表将转化为红黑树；链表长度低于6，就把红黑树转回链表; 初始化 当创建一个 HashMap 实例时，它会初始化一个默认大小的数组（默认为16），每个数组元素是一个链表。

总的来说，HashMap 通过散列函数将键映射到数组中，采用链表解决冲突的方法来存储数据。

2 Java 1.8 中 HashMap 的不同
a在 Java 1.8 中，如果链表的长度超过了 8 ，那么链表将转化为红黑树；链表长度低于6，就把红黑树转回链表;
b发生 hash 碰撞时，Java 1.7 会在链表头部插入，而 Java 1.8 会在链表尾部插入；
c在 Java 1.8 中，Entry 被 Node 代替（换了一个马甲）。

3 存储数据 当我们使用 put() 方法添加键值对时，HashMap 首先会计算键的 hashCode() 值，然后根据该值计算该键值对应在数组中的位置（即散列码），如果该位置上还没有元素，则直接把该键值对存储到该位置上；如果该位置上已经有元素了，则将该键值对插入到该位置对应的链表的末尾。
理解：（对Key求Hash值，然后再计算下标，如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的Hash值相同，需要放到同一个bucket中）如果碰撞了，以链表的方式链接到后面
d如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表，如果节点已经存在就替换旧值，如果桶满了(容量16*加载因子0.75)，就需要 resize（扩容2倍后重排））

4 访问数据 当我们使用 get() 方法来获取某个键对应的值时，HashMap 首先也会计算该键的 hashCode() 值，然后根据该值找到该键值对应在数组中的位置。如果该位置上没有元素，则返回 null；如果该位置上有元素，则遍历该位置对应的链表，找到与该键相等的键值对，然后返回该键值对的值。

5 扩容 当 HashMap 中存储的键值对数量超过数组大小的75%时，就会触发扩容操作。具体来说，HashMap 会将数组大小翻倍，并重新计算每个键值对在新数组中的位置，然后将所有键值对重新放置到新的数组中。

6 红黑树何时会退化为链表?

①扩容时由于原始hash值不同,重新计算下标,拆分树时,树的个数小于等于6会退化为链表

②remove树节点时,移除之前若 左孩子/左孙子/右孙子节点 有一个不存在个会变为链表

7 hashmap的key能否为null?作为key的对象有什么要求?为什么要重写hashcode，equals

①可以为null,其他的Map实现不一定:Treemap,Hashtable,currentHashMap(会出现空指针)

②作为key对象,必须实现hashCode和equals,并且key的内容不能修改

equals:万一两个元素的hashCode的值相等,通过equals判断是否为相同的元素

注意:如果hashCode值相等,不一定是同一个元素;如果两个元素equals相等,那么是同一个元素

因为 Set 和HashMap的key存储的是不重复的对象，依据 hashCode 和 equals 进行判断，所以存储的对象必须覆写这两个方法。

8.HashMap如何避免内存泄漏问题？

new不同的对象参数内容相同,内存地址不同;

如果没有重写equals底层默认的是使用==比较,比较的是内存地址

解决:重写自定义对象的hashcode和equals方法

9.HashMap的扩容机制？

默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。

总结：

①通过hash的方法，通过put和get存储和获取对象。

②存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。

③获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。

④如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

④HashMap如何解决Hash冲突问题?

链表+红黑树