2.4 哈希表
线性表结构+哈希函数，解决哈希碰撞
Last updated
线性表结构+哈希函数，解决哈希碰撞
Last updated
哈希表，Hash Table，又称 Hash 表或散列表。
哈希表能通过关键码或关键字 key 来进行直接访问 hash_table[key]，它由两部分构成：
一个数据结构：通常是数组（或者链表）
哈希函数：输入关键码 key，会返回数据结构的索引
哈希函数，Hash Function，又称 Hash 函数或散列函数。
哈希函数计算出来的值 hash(key) ，通常叫哈希值或 Hash 值或散列值。举个最简单的例子，关键码 key 是整数，哈希函数是 hash(key) = key。此时哈希表就退化成了一个数组，key 就是数组下标。
其实，哈希表就是数组的一种扩展，它很好地利用了数组支持按照下标随机访问数据的特性。哈希表对外表现为一个更强大的数组，其核心就在于哈希函数让“索引”变得更强大了。 hash_table[key] = value，实际上数据是存储在“数据结构”的 hash(key) 位置上，即 data_structure[hash(key)] = value。
一般情况下，关键码 key 是一个比较复杂的信息，比如字符串或很大的数。此时，就需要设计一个哈希函数 hash(key)，将复杂信息 key 映射到一个较小的值域内，然后再以此作为索引去访问与之对应的数据结构。举个例子，hash_table["lies"] = 233，如下图：
它在执行赋值操作的时候，实际上操作了两步：
第一步，计算哈希函数 hash("lies") = 9。示例中用的算法是将字符串中的每个字符的 ASCII 码相加，再模 20，通过取模的方式，将下标限定在了 [0, n-1] 范围内。
第二步，再通过哈希值 9 来访问对应的数据结构——数组，即 array[9] = 233
哈希碰撞，Hash Collisions，又称哈希冲突或散列冲突或散列碰撞。
哈希碰撞是指两个不同的 key 计算出了相同的 hash 结果。把复杂信息映射到小的值域，发生碰撞是不可避免的。
但是，无论多好的哈希函数，发生碰撞都是不可避免的，所以，我们还是需要一种终极的解决方案。
常用的解决哈希碰撞的方法有两类：
开放寻址法（open addressing）。思想是如果出现了哈希碰撞，就重新探测一个空闲位置，将其插入。探测方法有线性探测（linear probing）、二次探测（quadratic probing）、双重散列（double hashing）。
链表法（chaining），也称开散列法。它是一种更常用的哈希冲突解决办法。
开散列法也称“挂链法”，它在表头数组的每个位置上“挂”着一个链表，如下图所示：
开散列法的 hash 函数依然用于计算数组下标，然后数组的每个位置存储一个链表的表头指针，每个链表保存着具有同样 hash 值的数据（同时也会存 key）。
开散列结合了数组和链表，可以解决哈希碰撞的问题，从而实现一个哈希表。在工程上也有广泛的应用，比如电话号码簙（姓名-电话）、用户信息表（用户名-信息）、缓存（LRU Cache）、键值对存储（Redis 数据库）、Java 的 LinkedHashMap 容器等。
我们知道，数组的优点是支持随机访问，缺点是需要连续内存。链表的优点是内存可以不连续，缺点是访问/查找是线性的。这里的哈希表将数组和链表混合使用，便同时利用了二者的优势，也规避了它们的不足。
开散列法（数组挂链法）的效率取决于 hash 函数写得怎么样。
期望：O(1)
插入 查询 删除
数据分布比较均匀
最坏：O(n)
插入 查询 删除
数据全被映射到了 相同的 hash 值
当然，我们一般不会针对字符串写一个 hash 函数，因为编程语言已经帮我们写好了一些非常好的字符串的哈希函数，我们可以直接使用，比如集合和映射这样的库/数据类型。
集合（set）：存储不重复元素（的一个容器）
映射（map）：存储关键码 key 不重复的键值对
它们又分别分为两类：
无序集合/映射：一般用哈希表来实现，O(1)
有序集合/映射：遍历时按照元素/key 的大小进行排列，一般用平衡二叉搜索树（即平衡树）来实现，O(logN)
对于语言的内置类型（int, string）都已经有默认的非常好的 hash 函数，不需要我们自己写，我们可以直接在集合和映射里使用。比如：
C++
set, map 是有序的，使用红黑树实现
unordered_set, unordered_map 是无序的， 使用哈希表实现的
multiset, multimap 多重集合/映射（允许 key 重复）
Java 里的 Set 和 Map 不重复
HashSet, HashMap 无序的
TreeSet, TreeMap 有序的
Python
集合 {'aa', 'bb', 'cc'}, set(['aa', 'bb', 'cc'])
字典 dict ~ JSON 对象
这部分重点介绍了哈希表，它的两个核心是哈希函数和哈希碰撞。哈希碰撞有两种常用的解决方法，即开放寻址法和链表法。哈希函数的好坏决定了哈希碰撞的概率大小，也直接决定了哈希表的性能。
哈希表来源于数组，它借助哈希函数对“索引”进行了扩展，以利用数组支持按照下标随机访问元素的特性。无序集合和无序映射一般都是用哈希表来实现的，大部分编程语言都提供了这两种数据类型，我们可以直接使用。
严格来说，无序集合和无序映射是一个容器/接口，它们可以用哈希表来实现，而哈希表是一个实现方法/数据结构。然后，哈希表的底层又是通过数组或者链表这两种最基本的数据结构来实现的。
一个好的哈希函数，可以减少碰撞发生的几率，让数据尽可能地均衡分布。碰撞少了，均匀分布了，容器的效率也会越高。哈希函数通常不会太复杂，因为复杂了会消耗较多的计算时间，进而影响哈希表的性能。哈希函数多种多样，比如直接寻址法、平方取中法、折叠法、随机数法，比如将每个字母的 ASCll 码值"进位"相加再取模，即 。
