HashMap原理摘要

HashMap介绍

HashMap是我们编程时经常会使用到的数据结构。这个数据结构的最大好处是能够帮助我们快速定位在内存中的某一个内容。

例如在Java中，我们快速取得Key所对应的值

//假设 map 是一个HashMap<String, Integer>
map.get("Key"); 

原理

HashMap就是使用哈希函数将一个键映射到一个桶中，这个桶中就可能包含该键对应的值。

哈希函数

HashMap的关键就在于哈希函数的选择。哈希函数就将一个Key映射成一个序列的Index的操作。在Java中，哈希函数将Key这个对象，转换成一个数组的下标。

image.png

因为Key的集合往往远远大于我们保存数据的序列，所以哈希函数的的难度就在于需要将Key生成的这个Index尽量平均的分布在序列中。这个算法也叫做散列算法

结构

在Java中，我们使用一个数组作为我们的序列，这样Key经过哈希函数后会得到数组的Index. 因为多个Key可能会得到同一个Index，所以引入了链表来保存相同Index的K-V对象。如下图：

image.png

在Java中可以看到如下的结构，使用数组作来保存链表。

image.png

存取

HashMap的读取是根据给定的Key计算出Index，根据这个Index找到相应的位置（golang中也叫做bucket），然后再进行查找。

image.png

扩容

HashMap会根据容量而采取扩容动作

image.png

因为扩容动作需要新建表，也可能存在重新Hash，所以HashMap其实并非线程安全。Java中，多线程使用的情况下，需要使用ConcurrentHashMap。

在Java1.8以后，如果链表的长度大于8，则使用红黑树进行存储。

image.png

总结

• HashMap的关键在于哈希函数，哈希函数采用散列算法来实现Key到Index的映射
• 根据下标定位到桶（bucket，或者是链表），然后再对桶（bucket，或者是链表）中的元素进行操作。
• 如果序列中的元素过多，可能需要扩容。扩容的算法很耗时。