HashMap的原理

缺乏、安全感 2022-01-26 10:45 254阅读 0赞

**目录**

是什么？

Put方法

Get方法

HashMap的初始长度？

Hash算法

为什么长度必须是16或者2的幂？

如果长度是10会怎么样？

扩容

原则

步骤

--------------------

# 写在前头的话： #

本文是以jdk1.7的基础上进行的。

# 是什么？ #

HashMap是一个用于存储Key-Value键值对的集合，每一个键值对叫做Entry。Entry分散存储在数组当中，这个数组是HashMap的主干。是数组+链表的形式。

![image.png][]

# Put方法 #

hashMap.put("apple",0)，插入一个key为"apple"的元素。但是插入到哪呢？哈希函数来确定Entry的插入位置（index）；

index =  Hash("apple")

假如最后计算出的index是2，那么结果如下：

![image.png][image.png 1]

但是，HashMap的长度始终是有限的，当插入的Entry越来越多的时候会产生哈希冲突。如下：

![image.png][image.png 2]

经过hash函数可能index=3出可能有2个数组，那么此时应该怎么办呢？这时候就产生了链表。

HashMap数组的每一个元素是一个Entry对象同时也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可。

![image.png][image.png 3]

新来的Entry节点插入链表时，使用“头插法”。

Key可以为空吗？可以。

如果hash key重复了value会覆盖吗？不会

> map.put("apple",30)
> 
> map.put("apple",31)
> 
> 输出结果为31，但是entry.next.getvalue()的结果为30

put源码：如果返回值不为null说明key重复返回了新值。如果返回值为null，就说明key不重复。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pbmdtZW5nYmFieQ_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pbmdtZW5nYmFieQ_size_16_color_FFFFFF_t_70 1][]

# Get方法 #

get(key)

index = Hash("apple")

由于Hash冲突，同一个位置匹配多个Entry，需要按照链表的头节点一个一个向下来查找。假如要查找的key是“apple”

![image.png][image.png 4]先根据Hash函数找到是index = 3，查看Entry3的key = grape不是我们想要的，查看Next节点Entry2的key = apple找到了。

# HashMap的初始长度？ #

默认初始长度是16，自动扩展或者手动初始化时，长度必须是2的幂。

## Hash算法 ##

位运算

index = Hash(Key) & (Length -1)

## 为什么长度必须是16或者2的幂？ ##

1.book的hashcode是二进制的101110001110101101001

2.HashMap长度是默认的16，Length-1 = 15，二进制1111

3.与运算。结果为1001,结果index = 9

## 如果长度是10会怎么样？ ##

![image.png][image.png 5]

换一个新的HashCode

![image.png][image.png 6]

结果index = 9没变化

换一个新的HashCode

![image.png][image.png 7]

结果index = 9还是没变化

当HashMap的长度为10的时候，有些index出现的几率大，有的index出现的几率小可能导致有的位置上为null,这样显然不符合Hash算法均匀分布的原则。

但是长度16或者其他2的幂，Length-1的值所有二进制位全为1，index的结果跟HashCode后几位的值等同，只要输入的的HashCode本身是均匀的，Hash算法的结果就是均匀的。

# 扩容 #

## 原则 ##

HashMap.Size >= Capacity \* LoadFactor（默认长度 \* 加载因子）

## 步骤 ##

扩容和ReHash两个步骤，ReHash在并发情况下会出现死锁。

![image.png][image.png 8]

1线程先处理9，然后睡眠，2线程处理9之后指向5，这时候1线程继续执行发现9之后有key5然后继续执行5放到首部，这样5又指向9了出现了环形。即死锁。

[image.png]: /images/20220126/61e3f5e13c984929b01e80e0f5ce42bc.png
[image.png 1]: /images/20220126/502c609b75f741b9badc898ad9bba8b1.png
[image.png 2]: /images/20220126/b3d79546ba86416eac028b752b236c5a.png
[image.png 3]: /images/20220126/a5a0feaac3284b0197d0f32759d0f6c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pbmdtZW5nYmFieQ_size_16_color_FFFFFF_t_70]: /images/20220126/d62243b570e04f0b81ee0a4294595176.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pbmdtZW5nYmFieQ_size_16_color_FFFFFF_t_70 1]: /images/20220126/13070fa220124d0ba9729e7a73067ef9.png
[image.png 4]: /images/20220126/248834587fbd4acd8e64d1302657e122.png
[image.png 5]: /images/20220126/e8a81e9c5b7745f88d92b6916e198811.png
[image.png 6]: /images/20220126/3ba87aa5ec7b4473b2d322103cc8a889.png
[image.png 7]: /images/20220126/0a58294376b241f89431db9ba3e94be4.png
[image.png 8]: /images/20220126/58f27b80d20341ce9dbedc1fd6e891fc.png