散列表也叫作哈希表（hash table），这种数据结构提供了键（Key）和值（Value）的映射关系。只要给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1)。
image.png
散列表是如何根据Key来快速找到它所匹配的Value呢？我们需要一个“中转站”，通过某种方式，把Key和数组下标进行转换。这个中转站就叫作哈希函数。
image.png
散列表的读写操作：
1. 写操作（put）
写操作就是在散列表中插入新的键值对（在JDK中叫作Entry）。如调用hashMap.put("002931", "王五")，意思是插入一组Key为002931、Value为王五的键值对。
具体该怎么做呢？
第1步，通过哈希函数，把Key转化成数组下标5。
第2步，如果数组下标5对应的位置没有元素，就把这个Entry填充到数组下标5
的位置。
image.png
但是，由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的。例如002936这个Key对应的数组下标是2；002947这个Key对应的数组下标也是2。
image.png
这种情况，就叫作哈希冲突。
解决哈希冲突的方法主要有两种，一种是开放寻址法，一种是链表法。
1.开发寻址法
Entry6通过哈希函数得到下标2，该下标在数组中已经有了其他元素，那么就向后移动1位，看看数组下标3的位置是否有空。
image.png
很不巧，下标3也已经被占用，那么就再向后移动1位，看看数组下标4的位置是否有空。
image.png
幸运的是，数组下标4的位置还没有被占用，因此把Entry6存入数组下标4的位置。
image.png
这就是开放寻址法的基本思路。当然，在遇到哈希冲突时，寻址方式有很多种，并不一定只是简单地寻找当前元素的后一个元素，这里只是举一个简单的示例而已。
2.链表法
HashMap数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可。
image.png
2.读操作
调用 hashMap.get("002936")，意思是查找Key为002936的Entry在散列表中所对应的值。
第1步，通过哈希函数，把Key转化成数组下标2。
第2步，找到数组下标2所对应的元素，如果这个元素的Key是002936，那么就找到了；如果这个Key不是002936也没关系，由于数组的每个元素都与一个链表对应，我们可以顺着链表慢慢往下找，看看能否找到与Key相匹配的节点。
image.png
在上图中，首先查到的节点Entry6的Key是002947，和待查找的Key 002936不符。接着定位到链表下一个节点Entry1，发现Entry1的Key 002936正是我们要寻找的，所以返回Entry1的Value即可。
3.扩容
首先，什么时候需要进行扩容呢？
当经过多次元素插入，散列表达到一定饱和度时，Key映射位置发生冲突的概率会逐渐提高。这样一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能都有很大影响。这时，散列表就需要扩展它的长度，也就是进行扩容。
image.png
扩容不是简单地把散列表的长度扩大，而是经历了下面两个步骤。
1．扩容，创建一个新的Entry空数组，长度是原数组的2倍。
2．重新Hash，遍历原Entry数组，把所有的Entry重新Hash到新数组中。为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。
经过扩容，原本拥挤的散列表重新变得稀疏，原有的Entry也重新得到了尽可能均匀的分配。
image.png
扩容后的HashMap
image.png
以上就是散列表各种基本操作的原理。由于HashMap的实现代码相对比较复杂，这里就不直接列出源码了，有兴趣的读者可以在JDK中直接阅读HashMap类的源码。
需要注意的是，关于HashMap的实现，JDK 8和以前的版本有着很大的不同。当多个Entry被Hash到同一个数组下标位置时，为了提升插入和查找的效率，HashMap会把Entry的链表转化为红黑树这种数据结构。
网友评论