HashMap实现原理

r囧r小猫 2021-12-16 05:59 354阅读 0赞

##### HashMap #####

1.  HashMap基础数据结构：

![\[外链图片转存失败(img-uBtujeaq-1562295943916)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps1.png)\]][img-uBtujeaq-1562295943916_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps1.png]

*  如上结构课看出，HashMap主要是有一个链表的形式来存储数据 ，上面Node类和C语言中的结构体很像，如上可以看出HashMap底层由是一个数组结构，数组中的每一项又是一个链表，新建一个HashMap的时候，会初始化数组。数组中的每个元素都是Node类，其中包括了Key，Value，还有对应的下一个节点的地址信息，类似指针。

1.  提到Hashmap首先要知道的一个是哈希分布和哈希碰撞

*  对于每个对象X和Y，如果当（且仅当，译者注）X.equals(Y)为false，使得X.hashCode() != Y.hashCode()为true，这样的函数叫做完美Hash函数。下面是完美哈希函数的数学表达.
    
     *  ∀*X*,∀*Y*∈*S*, (*h*(*X*)=*h*(*Y*))⟺*X*=*Y*:*S* 是所有对象的几何，*h*为哈希函数。
 *  从上面可以看出，哈希分布主要是通过Hash函数来实现的，但那是hash函数返回的是int类型的数据，也就是能表示的范围 在2^23个数据，当数据量超过这个范围时候吗，就必定会出现两个数据对应同一个Hash值的情况，这种时候就出现了哈希碰撞

1.  现在解决哈希碰撞的方法一种是**开放寻址**，一种是**分离链接**。其他的用于解决Hash冲突的方式，大多基于这两种方法

![\[外链图片转存失败(img-6dOpBr5h-1562295943917)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps2.jpg)\]][img-6dOpBr5h-1562295943917_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps2.jpg]

1.  开放寻址是一种解决哈希冲突的方式，当计算出的桶索引的位置被占据时，通过一定的算法，来寻找未被占据的哈希桶（适合数量确定，冲突较少的情况，译者注）。而分离链接则将每一个哈希桶作为一个链表的头结点，当哈希碰撞发生时，仅需在链表中进行储存、查找。这两种方法都有着同样的最坏时间复杂度*O*(*M*)，但是开放寻址使用连续的空间，因此有着缓存效率的提升。因此当数据量较小时，能够放到系统缓存中时，开放寻址会表现出比分离链接更好的性能。但是当数据量增长时，它的性能就会越差，因为我们无法期待一个大的数组能够得到缓存性能优化。这也是HashMap使用分离链表来解决哈希冲突的原因。此外，开放寻址还有一个弱点。我们调用remove()方法会十分频繁，当我们删除数据时，一个特定的哈希冲突，可能会干扰总体的性能，而分离链表则没有这样的缺点。
2.  HashMap中几个重要参数：

*  Int threshold 所能容纳的key-value的极限
 *  Final float loadFactor 负载因子
 *  Int modCount 分布式锁标记
 *  Int size 数组中node的数量
 *  Node\[\] table 初始化大小是16，loac factor负载因子默认大笑是0.75， threshold是HashMap所能容纳的最大数据量Node 个数， 计算公式 Threshold = length\* loacFactor，也就是说数组定义好之后负载因子越大，所能容纳的键值对越多。
 *  由上面公式可以看出，threshold是在loacfactor和length长度允许下最大元素的数量。超过这个容量之后就要resize（扩容）扩容之后的容量是之前的两倍， loadFactor的定义是对空间课时间复杂度的一个权衡，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。
 *  Size是hashMap中实际存在的node的个数，和table的length还有最大容量threshold是有区别的。

1.  存在的一个问题，就是不管hash算法多么合理，都避免不了hash被占满的情况，这时候会出现链表过长的情况，在jdk1.8之前，没有对链表过长情况做优化，在jdk1.8版本中，对数据结构做了进一步的优化，引入了红黑树，而当链表过长时候（默认8个）链表就会转成红黑树，利用红黑树的快速增删改查来提高hashMap的性能，其中会用到红黑树的插入、删除、查找等算法。
2.  HashMap中包有四个构造方法，方法如下。
    
    ![\[外链图片转存失败(img-RaXvv7Sh-1562295943918)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps3.png)\]][img-RaXvv7Sh-1562295943918_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps3.png]
    
    1.  第一个构造方法：带两个参数构造方法： 其中initialCapacity 指定HashMap 的总容量，loadFactor指加载因子，表示当HashMap满的时候扩容的依据。
    
    \[外链图片转存失败(img-ywVMSeTR-1562295943918)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps4.png)\]
    
    1.  第二个构造方法：如上，只有一个参数信息，表示HashMap的总容量信息。DEFAULT\_LOAD\_FACTOR加载因子默认是0.75f
    
    ![\[外链图片转存失败(img-ZaJbgCrp-1562295943919)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps5.png)\]][img-ZaJbgCrp-1562295943919_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps5.png]
    
    1.  第三个构造方法：初始化一个空的HashMap 加载因子也是默认数值0.75f
    2.  第四个构造方法：直接将一个类型相同的HashMap赋值，加载因子还是默认大笑0.75

![\[外链图片转存失败(img-TFCCb9Tv-1562295943919)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps6.png)\]][img-TFCCb9Tv-1562295943919_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps6.png]

1.  HashMap实现原理

![\[外链图片转存失败(img-wS5sbQoD-1562295943919)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps7.png)\]][img-wS5sbQoD-1562295943919_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps7.png]

*  Put方法 如上源码中可见，HashMap的put方法
    
     *  首先对key做hash检查NodeTable是否为空，如果是空的数组，先对数组进行初始化。
     *  第二个判断，HashMaP允许存放key为null和value为null的情况，当key == null时候，HashMap会将这个值放到第一位置
     *  第二个判断，通过对Key的hash值的判断指定hash对应的table中是否存在对应的元素，如果指定hashCode的table索引处值是null表示此处还没有Node节点，接着新建一个Node节点并且初始化KeyValue，next为null。
     *  如果判断hash处存在key碰撞，则以链表的形式存在buckets后面
     *  如果碰撞导致链表过长就把链表转成红黑树，如果bucket满了，那么通过resize重新分配内存空间,如下.

![\[外链图片转存失败(img-Gw7TX7js-1562295943920)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps8.png)\]][img-Gw7TX7js-1562295943920_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps8.png]

*  HashMap中的get方法：
    
     *  首先检查第一个元素，每次都会先检查第一个元素，如果没有命中，执行下面
     *  通过key获取对应的entry
     *  如果拿到的entry是树，择通过getTreeNode获取
     *  如果拿到的是链表,择通过ke.equalsa(key)查找。

1.  HashMap桶的扩容：

*  HashMap中Node数组的我们称他为Hash桶，当不断的向HashMap中曾加数据到固定的阀值时候会触发扩容，如下代码：

![\[外链图片转存失败(img-POUBVfUd-1562295943920)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps9.png)\]][img-POUBVfUd-1562295943920_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps9.png]

*  如上代码：Threshold = DEFAULT\_LOAD\_FACXTOR*DEFAULT\_INITIAL\_CAPACITY = 0.75*16 = 12所以当使用默认值初始化HashMap的时候，第一次是12个元素开始触发扩容。扩容之后的容量是原来容量的两倍如下代码：

![\[外链图片转存失败(img-0ajY75gN-1562295943920)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps10.png)\]][img-0ajY75gN-1562295943920_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps10.png]

*  如上逻辑，如果扩容之后的容量小于HashMap可承载的最大值 1<<30 （2^30），则扩容到原来的两倍 newTHr = oldThr<<1.就是新建一个Node数组，并且将老数组中的值按照原来的规则重新Hash到新的数组中。
 *  之后的操作在jdk1.7和jdk1.8 中不一样：
    
     *  Jdk1.7中：在新建链表的过程中是使用的单链表的头结点插入方式，旧的数组中数据经过重新计算Hash值，然后放入新的数组中，同一个Hash位置上的新元素总会被放在Hash链表的头部位置。

![\[外链图片转存失败(img-7uXuveYB-1562295943921)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps11.jpg)\]][img-7uXuveYB-1562295943921_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps11.jpg]

*  JDK1.8中：
    
     *  在1.8 中做了一部分优化，其中使用的是2次幂的扩张（原来的2被）， 所以元素的位置要么在原来位置，要么在移动2次幂的位置。如下图：

![\[外链图片转存失败(img-dBRHK5Gd-1562295943921)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps12.jpg)\]][img-dBRHK5Gd-1562295943921_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps12.jpg]

*  图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。
 *  注意：如上后面的值是hash之后的值比如 hash2： 1111 1111 1111 1111 0000 1111 0001 0101 最后得到的hash是一个int类型，只有四位，所以是最后的四位：0101
 *  当扩容之后，n变为原来的两倍，相当于左移动一位，择变成了1 0101得到之后的结果

![\[外链图片转存失败(img-prZTu2WQ-1562295943921)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps13.jpg)\]][img-prZTu2WQ-1562295943921_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps13.jpg]

*  所以扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

![\[外链图片转存失败(img-tz6hP7I9-1562295943922)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps14.jpg)\]][img-tz6hP7I9-1562295943922_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps14.jpg]

1.  总结：

*  hashMap工作原理：
    
     *  通过hash的方法，通过put和get存储和获取对象，存储的位置通过HashCode计算hash得到对应的bucket位置，然后在存储，HashMap会根据当前的node数组占用情况来来自动调整容量，（size的值超过LoadFacotr的值则resize到原来的2倍），
     *  获取对象的时候，我们就将key传给get方法，他调用hashCode计算hash从而buacket位置，并且进一步调用equals方法来确认key是否一直，如果发生碰撞，HashMap通过链表来存储这些元素， 在java8 中，如果一个bucket中碰撞冲突的元素超过了某个限制（8个），择会将原来的链表转换成红黑树来替换，利用红黑树的CURD高性能来提高hashMap的效率。
 *  Hash具体实现以及1.8优化：
    
     *  对于任意给定的对象只要HashCode返回值相同，那么调用方法所计算得到的hash码应该是相同的，然后通过hash和数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的：具体方法：

![\[外链图片转存失败(img-SX0pIOwK-1562295943922)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps15.png)\]][img-SX0pIOwK-1562295943922_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps15.png]

*  因为HashMap的长度总是2的N次方，这是HashMap在速度上的一个有事，当length总是2的n次方的时候，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。如下图：

![\[外链图片转存失败(img-nVdvT13e-1562295943922)(file:///C:\\Users\\ADMINI~1\\AppData\\Local\\Temp\\ksohtml7216\\wps16.jpg)\]][img-nVdvT13e-1562295943922_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps16.jpg]  
如上图所示，异或和取摸运算得到的hash值是一样的。

*  String，Integer这样的wrapper类适合做键：
    
     *  因为String是不可变的类型，也是Final类型，而且重写了equals和hashCode方法，其他的包装类也有这个特点，因为在计算的时候需要用到hashCode方法，而且在get的时候需要用到queals方法，这种情况下需要key对应的hash值是前后不变的这样可以准确找到对应的位置，并且还有线程安全的优点。所以键对象重写hashCode和equals方法是很有必要的。
 *  参考文章：
    
     *  [https://blog.csdn.net/richard\_jason/article/details/53887222][https_blog.csdn.net_richard_jason_article_details_53887222]
     *  [https://blog.csdn.net/c139352227/article/details/47861815][https_blog.csdn.net_c139352227_article_details_47861815]
     *  https://blog.csdn.net/super\_me\_jason/article/details/79741298

[img-uBtujeaq-1562295943916_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps1.png]: /images/20211214/6e60535bdb5d4659971c22436149467a.png
[img-6dOpBr5h-1562295943917_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps2.jpg]: /images/20211214/9638ee8c5754462dbbf94ce2d533ff3f.png
[img-RaXvv7Sh-1562295943918_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps3.png]: /images/20211214/dc27b020c4174756b7ae18317f1566c1.png
[img-ZaJbgCrp-1562295943919_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps5.png]: /images/20211214/d178b26f0937430f9fa1a40e5db4e7aa.png
[img-TFCCb9Tv-1562295943919_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps6.png]: /images/20211214/143d45bc95be4a57bbb04ecc8ddb2f22.png
[img-wS5sbQoD-1562295943919_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps7.png]: /images/20211214/2f625204bc9846e887e2b1ff25ac4bed.png
[img-Gw7TX7js-1562295943920_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps8.png]: /images/20211214/953209160ec740549eaa534133001e64.png
[img-POUBVfUd-1562295943920_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps9.png]: /images/20211214/ef8a14ed04904730acc83b1afc84aeda.png
[img-0ajY75gN-1562295943920_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps10.png]: /images/20211214/4da957972e1946c1bfa42b88d2c08463.png
[img-7uXuveYB-1562295943921_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps11.jpg]: /images/20211214/212d035cad054e29854172aff947c6b4.png
[img-dBRHK5Gd-1562295943921_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps12.jpg]: /images/20211214/f63d0efaa9f4473bb9e5bd20a7249050.png
[img-prZTu2WQ-1562295943921_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps13.jpg]: /images/20211214/56d3771f7ecd46c5a361714e4a408853.png
[img-tz6hP7I9-1562295943922_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps14.jpg]: /images/20211214/038fcd4b1b8c493bb62eb46059be06a3.png
[img-SX0pIOwK-1562295943922_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps15.png]: /images/20211214/e831f2deafe0474cbd6eab277187a1d5.png
[img-nVdvT13e-1562295943922_file_C_Users_ADMINI_1_AppData_Local_Temp_ksohtml7216_wps16.jpg]: /images/20211214/8528233748d44b299535665d4a6a8934.png
[https_blog.csdn.net_richard_jason_article_details_53887222]: https://blog.csdn.net/richard_jason/article/details/53887222
[https_blog.csdn.net_c139352227_article_details_47861815]: https://blog.csdn.net/c139352227/article/details/47861815