什么是 HashMap？看漫画

众所周知，HashMap是一个用来存储键值对key-Value的集合。每个键值对也称为 Entry。这些键值对（Entry）分散存储在一个数组中，这个数组就是HashMap的主干。

HashMap数组的每个元素的初始值为Null。

对于HashMap来说，我们最常使用这两种方法：Get 和Insert。

1。 Put方法的原理

调用Put方法时会发生什么？

例如，通过调用hashMap.put("apple", 0)，插入一个键为"apple"的元素。此时，我们需要使用哈希函数来确定插入位置（索引） Entry：

index = Hash("apple")

假设最终计算出的索引为2，则结果如下：

但是，由于HashMap长度有限，随着插入的Entry越来越多，无论Hash函数多么完善，都不可避免地会出现索引冲突。例如：

这个时候我们该怎么办？为了解决这个问题，我们可以使用链表。

HashMap数组的每个元素不仅是一个Entry对象，同时也是一个链表的主节点。每个Entry对象通过另一个指针指向它的下一个Entry节点。当一个新的Entry节点被映射到冲突的数组位置时，将其插入到对应的链表中即可：

需要注意的是，当一个新的Entry节点插入到链表中时，采用“头插入法” “ 用来。为什么不插入链表末尾会在后面解释。

2。 Get 方法的原理

使用 Get 方法根据密钥找到 Value 会发生什么？

首先将输入的key进行哈希映射，得到对应的索引：

index = Hash("apple")

由于刚才提到的哈希冲突，同一个位置可能会匹配多个Entry，必须顺着主节点匹配链表，一一往下查找。假设我们要查找的键是“苹果”：

第一步，我们查看头节点“Entry 6”。键“Entry 6”是“香蕉”，这显然不是我们要查找的结果。

第二步，我们看下一个节点“Entry1”。“Entry1”的键是一个苹果，这正是我们要找的结果。

之所以将Entry6放在根节点，是因为HashMap的发明者认为在之后插入的Entry更有可能被搜索到。

———————————————

前面提到过，Hash函数用于将一个key映射到HashMap数组中对应的位置：

index = Hash(" apple" )

如何实现分布尽可能均匀的哈希函数？我们正在使用键的 HashCode 值进行某种操作。

index = HashCode (Key) % Length ?

如何进行位运算？有如下公式（Length为HashMap的长度）：

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

下面我们用key值为“book”来演示整个过程： 1。计算该书的hashcode，十进制结果为3029737，二进制结果为101110001110101110 1001。

2。假设HashMap的长度默认为16，则计算Length-1的结果十进制为15，二进制为1111。 ？

可以说，哈希算法得到的索引的最终结果完全取决于key的hashcode值的最后几位。

假设HashMap的长度为10，重复操作步骤：

单看这个结果，表面上没有问题。让我们尝试一个新的 HashCode 101110001110101110 1011 ：

让我们尝试另一个 HashCode 10111001110‸1110 尝试：

是的，虽然HashCode是倒数第二个，第三个Bit从0变成了1，但运算的结果始终是1001。也就是说，当HashMap的长度为10时，有些索引结果更容易出现，而有些索引结果永远不会出现（比如0111）！

这显然不符合哈希算法均匀分布的原则。

回顾一下长度16或其他2的幂，Length-1的值是这样的：所有二进制位都为1。此时，索引结果相当于HashCode的最后几位的值。只要输入的HashCode本身是均匀分布的，那么哈希算法的结果就是均匀的。

作者：程序员小辉
链接：https://juejin.im/post/5a215783f265da431d3c7bba
来源：掘金
。商业转载请联系作者获取授权。非商业转载请注明出处。