哈希表

文章摘抄自《漫画算法》

1.基本概念

在我们手机电话簿查找某个人的电话号码时，我们只需要输入姓名，就可以查询出这个人的电话号码，在英语电子词典，我们输入英文单词，就可以查询到单词的中文。
我们开发一个学生管理系统，需要输入学号快速查出对应学生的姓名的功能，这里不必每次都去查询数据库，可以在内存中建立一个缓存表，可以做可以提高查询效率，不要每次去数据库查询进行IO操作。

image.png
再如我们需要统计一本英文书里面某些单词出现的频率，就需要遍历整本书的内容，把这些单词出现的次数记录在内存中。
image.png
因为这些需求，一个重要的数据结构诞生，这个数据结构就叫做散列表。

散列表也叫做_哈希表（hash table） _，这种数据结构提供了键(key) 和值(value)的映射关系，只要给出一个key,就可以高效查找到它所匹配的Value，时间复杂度接近于O(1)。

image.png

2.基本原理

2.1.哈希函数

在我们熟悉的几种数据结构中，查询效率最高的是数组，数组可以根据下标进行元素的随机访问。散列表其实也 是一个数组。

数组智能根据下标，像a[0]、a[1]、a[3]这样来访问，而散列表的key则是以字符串类型为主的，列如以学生的学号作为key，输入002123，查询到李四；或者以单词作为key，输入by，查询到数字46，所以我们需要一个“中转站”，通过某种方式，把key和数组下标进行转换。这个中转站 就叫做哈希函数。

image.png

那么哈希函数是怎么实现的呢？
在不同的语言中，哈希函数的实现方式是不一样的，这里以Java的常用集合HashMap为例，来看看哈希函数在Java中的实现。

在Java及大多数面向对象的语言中，每一个对象都有属于自己的hashCode，这个hashCode是区分不同对象的重要标识。无论对象自身的类型是什么，他们的hashcode都是一个整型变量。

既然都是整型变量，想要转换成数组的下标也就不难实现了。最简单的转化方式是什么呢？是按照数组的长度进行取模运算。
index = HashCode(key) % Array.length
实际上，JDK中的哈希函数并没有直接采取取模运算，而是利用了位运算的方式来优化性能。不过在这里可以简单理解为取模运算。

通过哈希函数，我们可以把字符串或者其它类型的key，转化成数组的下标index。
如给出长度为8的数组，则当 key=001121时，
index= HashCode("001121") % Array.length = 1420036703 % 8 = 7
而当key=this时，
index= HashCode("this") % Array.length = 3556070 %8 = 6
_

2.2.散列表的读写操作

有了哈希函数，就可以在散列表中进行读写操作了。
1.写操作（put）
写操作就是在散列表中插入新的键值对（在java 中叫Entry）
如调用hashMap.put("002931" , "王五")，意思是插入一组key=002931 、value=王五的键值对。

第一步，通过哈希函数，把key转化为数组下标5。
第二步，如果数组下标5对应的位置没有元素，就把这个Entry填充到下标5的位置。

image.png

但是由于数组长度有限，当插入的Entry越来越多时，不同的key通过哈希函数获得的下标有可能是相同的。例如00296这个key数组对应的数组下标是2；00297这个key对应的数组下标也是2。

image.png

这种情况叫做哈希冲突。哈希冲突是无法避免的，智能想办法来解决冲突。主要有两种方式：
一种是开放寻址法，一种是链表法。
开放寻址法就是当一个key通过哈希函数获得对应的数组下标已被占用时，我们就寻找下一个空档位置已上面的情况为例，Entry6通过哈希函数计算得到的下标是2，该下标在数组中已经有了其他元素，那么就向后移动一位，看看数组下标3的位置是否有空。

image.png

很不巧，下标3也已经被占用了，那么就再向后面移动一位，看看数组下标4的位置是否有空。

image.png
数组下标4的位置没有被占用，因此把Entry6存到数组下标4的位置。 image.png

这个就是开放寻址法的基本思路，当然在遇到哈希冲突时，寻址的方式有很多，并不一定只是简单的寻找当前元素的后一个元素，这里只是举一个简单的实例而已，在Java中ThreadLocal所使用的就是开放寻址法。

接下来，重点看一下哈希冲突的另一种解决办法--链表法。这种方法被应用再Java的集合类HashMap当中。

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

image.png

2.读操作get(key)
读操作就是通过key，在散列表中查找对应的value。
例如调用hashMap.get("002963")，意思是查找key为002936的Entery在散列表中所对应的值。
具体怎么做的呢？下面以链表法为例讲解。
第一步，通过哈希函数，把key转为数组的下标2.
第二步，找到数组下标2所对应的元素，如果这个元素的key是002936，那么就是找到了，如果这个key不是也没关系，由于数组的每个元素都与一个链表对应，我们可以顺着链表慢慢往下找，看看能否找到key相匹配的节点。

image.png
在上图中，首先查到的节点Entry6的key是002947，和待查的key002936不符，夹着定位到链表的下一个节点Entry1，发现Entry1的key正是我们要寻找的，所以返回Entery1的value值。

3.扩容（reSize）
散列表是基于数组实现的，所以也涉及到扩容的问题。
首先，什么时候需要进行扩容？
当经过多次元素的插入，散列表达到一定的饱和度时，key映射位置发生冲突的概率火逐渐提高，这样一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续操作和查询操作的性能有很大的影响。

image.png

这个时候，散列表就需要扩展他的长度，也就是进行扩容。
对于JDK中的散列表实现类HashMap来说，影响扩容的因素有两个。

• Capacity ，即HashMap当前的长度
• LoadFactor，即HashMap的负载因子，默认值是0.75f

衡量HashMap需要扩容的条件如下。
HashMap.size>=Capacity * LoadFactor

扩容不是简单的把散列表的长度扩大，需要经历两个步骤：
1.扩容，创建一个新的Entry空数组，长度是原数组的2倍。

2.重新Hash，遍历原来的Entry数组，把所有的Entry重新hash到新的数组中，为什么要重新hash呢？因为数组扩大后，Hash的规则也随之改变。

经过扩容后，原本拥挤的散列表重新变得稀疏，原有的Entry也重新得到了尽可能均匀的分配。
扩容前的HashMap：

image.png

扩容后的HashMap:

image.png

以上就是散列表的各种基本操作了，HashMap的实现源码比较复杂，后面写新的文章分析。