数据结构之散列表_数据结构散列表

什么是散列表

散列表也叫哈希表（Hash Table），这种数据结构提供了键（Key）和值（Value）的映射关系。只要给出一个 Key，就可以高效找到它所匹配的 value，实际复杂度接近于。key 和 value 代表的范围就很广了，比如 key 可以表示一本英文书中的单词，value 表示这个单词在书中出现的次数；key 也可以表示这本书的页码，value 表示该页码中出现的单词的数量……一个哈希表可以有多个 key，一般来说，这多个 key 必须是同一种类型的，比如说只表示英文书中的单词，或者只表示英文书的页码，不建议在同一个哈希表中混合使用不同类型的 key。

那么，散列表是如何根据 key 去快速查找它匹配的 value 的呢？这就涉及到散列表的相关原理了。

哈希函数

我们知道，数组的查询效率最高，可以根据下标进行数组元素的随机访问。其实散列表在本质上也是一个数组。

数组只能根据下标去访问，如 a[0]、a[1]...这样的，但是散列表的 key 值多半是以 String 字符串为主的。那么如何把散列表的 String 类型的 key 值转换为数组的下标从而去进行快速的访问呢？这便是哈希函数的作用。哈希函数就等于是一个中转站，将 key 和数组下标进行转换或映射。哈希函数是怎么实现的呢？对于 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 = 3559070 % 8 = 6$

但是，HashCode() 方法是如何把字符串类型的"001121"转换为 1420036703 的呢？这个问题我们后续再加以描述说明。

散列表的读写操作

有了哈希函数之后，就可以在散列表中进行读写操作了。

写操作(put)

散列表的写操作就是在散列表中插入新的键值对(Entry)。如调用 HahMap.put("002931","王五")，意思就是插入一组 key 为 002931，value 为王五的键值对。具体的插入过程为：

1.通过哈希函数，将 key = "002931" 转换为数组下标 5。

2.如果数组下表为 5 的对应的位置没有元素，就把这个 Entry 填充到数组下标为 5 的位置上。

但是，由于数组的长度是有限的，当插入的 Entry 越来越多时，不同的 key 通过哈希函数获得的 index 是有可能相同的。例如，002936 和 002947 对应的数组下标都是 2，这种情况就称为哈希冲突。

解决哈希冲突的方法主要有两种，一种是开放寻址法，一种是链表法。

开放寻址法

开放寻址法的原理其实很简单，当一个 key 通过哈希函数获得的对应的数组下标已经被 Entry 占用时，我们可以“另谋高就”，去寻找下一个空位置。

以上面的情况为例，Entry6 通过哈希函数得到的下标为 2，但是该下标在数组中已经有了其他元素，那么就向后移动 1 位，看看下标为 3 的位置是否有空。但是很显然，下标为 3 的位置也已经被其他元素占用了，那么久继续向后移动 1 位。下标为 4 的位置没有元素，所以 Entry6 插入到下标为 4 的位置。

这就是开放寻址法的基本思路。当然，在遇到哈希冲突时，寻址方法有很多种，并不一定只是简单的寻找当前下标的下一个位置。在 Java 中，ThreadLocal 所使用的就是开放寻址法。

链表法

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

读操作(get)

读操作就是通过给定的 key，在散列表中查找对应的 value。例如调用 HashMap.get("002936")，意思是查找 key 为 002936 的 Entry 在散列表中所对应的值。具体的操作流程为：

1.通过哈希函数，把 key 转换为数组下表 2；

2.找到数组下标 2 所对应的元素，如果这个元素的 key 为 002936，那么就找到了；如果这个 key 不是 002936，那就顺着链表慢慢往下找，看看能否找到与 key 相匹配的节点。

如上图所示，首先查找到的节点是 Entry6，key 值是 002947，和待查找的 key 值不相等。接着定位到链表的下一个节点 Entry1，发现 Entry1 的 key 002936 正是我们要查找的，所以直接返回 Entry1 的 value 即可。

扩容(resize)

散列表是基于数组实现的，那么也涉及扩容的问题。那到底什么时候扩容合适呢？

当经过 多次元素的插入，散列表达到一定饱和度时，key 映射位置发生冲突的概率会逐渐提高。这样一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能都会有很大影响。这时，散列表就需要扩充它的长度，也就是进行扩容。对于 JDK 中的散列表实现类 HashMap 来说，影响其扩容的因素有两个：

Capacity：即 HashMap 的当前长度

LoadFactor：即 HashMap 的负载因子，默认值为 0.75f。

衡量 HashMap 是否需要进行扩容的条件为：

也就是如果当前 HashMap 已经有四分之三的位置都有元素了，那么就需要进行扩容操作。

扩容操作不是简单的把散列表的长度扩大，而是分两个步骤进行的。

1.扩容：创建一个新的 Entry 数组，长度是原数组的两倍；

2.重新 Hash：遍历原 Entry 数组，把所有的 Entry 重新 Hash 到新数组中。为什么要重新 Hash 呢？因为长度扩大之后，Hash 的规则也随之改变。经过扩容，原本拥挤的散列表重新变得稀疏，原有的 Entry 数组也重新得到了尽可能均匀的分配。