【Java】HashMap 实现原理

「爱情、让人受尽委屈。」 2022-05-13 04:44 134阅读 0赞

Java集合框架有两个顶级接口，一个是collection接口，另一个是map接口，hashmap便是map接口的重要实现类。首先看map接口。根据map键值对的特性，接口中必然有相关的方法，主要是：

![70][]

前三个与map的操作有关，后三个与map遍历相关。

在map接口中，还定义了一个entry接口，hashmap实现本质上是一个entry的数组的链表。所以entry可以看成是hashmap的基本单元。下面是entry接口的内容，其中最核心的其实就是这三个方法：

![70 1][]

是对一个entry的key和value的获取以及value的修改。

下面是hashmap的实现类：

首先看一下重要的成员变量，

![70 2][]

再看一下构造函数：

![70 3][]

initialCapacity是一个与hashmap大小相关的参数，但是呢，他并不是最终的大小，可以看到，数组的大小其实是capacity，capacity是一个大于等于initialCapacity的2的次方，这个是通过一个while循环计算得到的，为什么必须是2的次方后面会说。loadfactor是装载因子，衡量饱满度。threashold是一个阈值，如果大于这个值，就认为hashmap太满了，碰撞的概率就很大，这时会触发resize过程，让hashmap扩容。modcount与多线程的迭代相关。table是entry的数组。

与hash有关的方法：

![70 4][]

上述方法用于计算hash值，首先得到key的hashCode，然后再位运算，最终的hash值很均匀，原因不详。

![70 5][]  
这个函数用上面得到的hash值计算table的索引，为了让每一个位置都有可能容纳一个entry，我们第一个想到是的是除模运算，但是在计算机中除法的效率很低，这里使用位运算就大大提高了效率，这里也解释了为什么数组大小是2的次方，因为2的次方减去1以后就是一个全1的二进制数，做and操作就会保证索引的均匀性，否则加入某一位是0，那么这一位永远不会再索引中出现。这样就可以通过key定位table的索引了。

再看get方法

![70 6][]

如果key是null，就调用如下方法：

![70 7][]  
key为null的entry存放在索引为0的位置，但是位置0不一定只有key为null的value，所以需要遍历位置0的所有entry，返回key为null的value。如果key不是null，那么就调用getEntry方法：

![70 8][]  
使用key定位索引，然后遍历索引里面的所有entry，找到key相等的value，返回，为什么要遍历，因为可能有碰撞。如果没指定key的entry，返回null。  
  
下面是put方法：

![70 9][]  
如果插入key为null的值，会调用如下方法：

![70 10][]

从索引0的entry数组遍历，看是否已经存在，如果是就只是更改value，此时modecount不加，说明更新不会触发迭代异常，否则就调用addEntry方法，新增一个entry。

![70 11][]

增加一个entry需要看容量是否超过了阈值，如果超过，就需要resize扩容。然后调用createEntry新增一个entry。

![70 12][]

这里就是调用entry的构造函数，让新的entry成为这个table槽位的第一个entry，其next指针设置为原本的第一个entry，所以新的元素都是插入到队首的。

那如果key不是null，过程也类似，通过hash值定位索引，然后在对应的table槽位中遍历entry，更新或者添加。过程一样。

最后看下扩容：

![70 13][]

扩容会新建一个容量为原来2倍的table，然后调用下面的方法把原始的entry加入到新的table：

![70 14][]

这个transfer过程就是把原本的每一个entry重新计算索引，再添加到队首的过程。  
  
这边是hashmap的一些核心的实现。

最后，注意hashmap不是线程安全的，因为比方说某一时刻两个线程都要put相同的key和value，很可能在map里面存在两个一模一样的entry，两个都检测到没有key，就调用了addentry方法。

hashtable的实现基本上鱼hasnmap是一样的，只不过对一些方法加了synchroninzed锁，hashmap是一个hashtable的轻量级实现，在多线程环境下应该使用hashtable而非hashmap，当然也可以使用其他的线程安全级别的map，或者自己封装一下hashmap。hashtable还有一个却别就是不支持null的key和value。会报异常。

[70]: /images/20220513/4ef17c609e764941afd871f7ba02f570.png
[70 1]: /images/20220513/301e57c3aaf143cc8db08904a4f87f33.png
[70 2]: /images/20220513/6ffe62f9e370465997a9325d01403a76.png
[70 3]: /images/20220513/f19321124e594e77a848ab51aff02b4b.png
[70 4]: /images/20220513/dbd6fa4319794450bafe7531e00a187a.png
[70 5]: /images/20220513/7f382fa2e17d4432a0503c24ae145a2e.png
[70 6]: /images/20220513/915e4f8a5d4048a188f3cc3a2a01fd6b.png
[70 7]: /images/20220513/b898f5a934cf49f4a7f654d3c4207de9.png
[70 8]: /images/20220513/840c2a8e1b444867a1720f704559d172.png
[70 9]: /images/20220513/c630261a2aff4306b187ffea05b7f85a.png
[70 10]: /images/20220513/49db3b6b63d74d0da5c6cb53c8ddb974.png
[70 11]: /images/20220513/f44d4ba6130e46efac73c6c382ba237b.png
[70 12]: /images/20220513/ce3e6691e33444a5a285aa72bb9b5040.png
[70 13]: /images/20220513/dae2ca3da76a4457b8ad9f9c5ead18f6.png
[70 14]: /images/20220513/bf9c0c42bcc444a8805182e7aeabe7c8.png