介绍

散列表（Hash Table，Hash表，哈希表）包含key（键值）、hash function（散列函数）、table（以散列值为下标的数组）三部分，优点是可$O(1)$查找元素（前提是元素数不要太多，全部元素的空间不会超过内存）。

散列表支持插入、查找、删除操作。

散列表的查找：将key通过hash function转换成散列值（非负整数）作为数组下标，将key对应的value存储在数组对应的下标中，就可以通过数组可以通过下标随机访问的特性，实现在$O(1)$复杂度用key（->散列值作为下标->）找到value。

Word文档中单词拼写检查，就是将英文单词全部存到散列表里，通过查找散列表看能否查到，来实现的。

散列函数

基本要求

• 散列值是一个非负整数；
• 如果key1==key2，那hash(key1)==hash(key2)；
• 如果key1!=key2，那hash(key1)!=hash(key2)。

但实际应用中的哈希函数无论如何设计，也很难满足第三点，因此难以避免散列冲突。

设计方法

• 数据分析法：参赛编号后两位、手机号码后几位
• ASCII码进位相加：hash(“nice”)=((“n”-“a”)*26*26*26 + (“i”-“a”)*26*26 + (“c”-“a”)*26 + (“e”-“a”))
• 直接寻址法
• 平方取中法
• 折叠法
• 随机数法

好的散列函数

• 不能太复杂
• 哈希值尽可能随机并且均匀分布

散列冲突

装载因子

不管采用哪种解决散列冲突的方法，当散列表中空闲位置不多时，散列冲突的概率就会大大提高。一般用装载因子（load factor）来表示空位的多少。装载因子越大，空闲位置越少，冲突越多，性能会下降。

装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子大到一定程度之后，可以进行动态扩容：

• 一次性集中动态扩容：重新申请一个更大的散列表，将数据搬移到新散列表中，但这样会很耗时，如果有用户线上请求就会失败
• 有新数据插入时：将新数据插入新散列表，并从老的散列表中拿出一个数据放进新散列表，均摊开来

解决办法

1. 开放寻址法（open addressing）

核心思想是如果出现了散列冲突，就重新探测一个空闲位置，将其插入。

优缺点分析：

• 优点：数据都在数组中查询，速度快；序列化简单。
• 缺点：删除数据需要特殊标记；装载因子的上限不能太高导致内存空间浪费
• 总结：当数据量比较小、装载因子小的时候，适合用开放寻址法

探测方法

（1）线性探测（linear probing）

• 插入：如果散列值位置的存储已经被占用了，就从当前位置开始依次往后查找，看是否有空闲位置，知道找到为止。
• 查找：如果散列值位置的存储等于要找的元素，说明就是我们要找的元素；如果不想等，就顺序往后依次查找，如果遍历到空闲存储位置，就说明查找的元素不在散列表中。
• 删除：先查找到该元素所在的位置，特殊标记为deleted，这样当下次查找时，遇到deleted空间继续往下探测而非认为是空的。

问题：当散列表中插入的数据越来越多时，散列冲突的可能性就会越来越到，空闲位置会越来越少，线性探测的时间就会越来越久，最坏时间复杂度为$O(n)$。

（2）二次探测（Quadratic probing）

冲突后，探测步长是平方：hash(key)+0，hash(key)+$1^2$，，hash(key)+$2^2$，…

（3）双重散列（Double hashing）

冲突后，探测方法是继续散列：hash(key)冲突的话，看hash1(key)，不行再看hash2(key)…直到找到空闲的存储位置。

2. 链表法（chaining）

核心思想：散列表中的table不是数组了，而是桶+链表。哈希值决定了是哪个桶，桶决定了是哪个链表。

优缺点分析：

• 优点：对内存的利用率比开放寻址法要高，对大装载因子的容忍度更高
• 缺点：会出现拉链过长的情况
• 总结：适合存储大对象、大数据量的散列表；比开放寻址法更灵活，支持更多的优化策略，比如用红黑树代替链表。

操作复杂度：

• 插入：计算出哈希值，插入对应的链表（开头）即可，复杂度$O(1)$
• 查找：计算出哈希值，查找对应的链表中结点即可，复杂度$O(k)$，k表示链表长度，k=n/m
• 删除：计算出哈希值，删除对应的链表中结点即可，复杂度$O(k)$

延伸

1. 如果有10万条URL访问日志，如何按照访问次数给URL排序？（？？？没看懂）
   （1）遍历10万条数据，以URL为key，访问次数为value，存入散列表，同时记录下访问次数的最大值K，时间复杂度$O(n)$
   （2）对value进行排序，如果K不是很大，使用桶排序，时间复杂度$O(n)$；如果K比较大，使用快速排序，时间复杂度$O(nlogn)$

2. 有两个字符串数组，每个数组大约有10万条字符串，如何快速找出两个数组中相同的字符串？
   （1）以第一个字符串数组构建散列表，key为字符串，value为True，时间复杂度$O(n)$
   （2）遍历第二个字符串数组，以字符串为key再散列表中查找，如果有True则是相同的字符串，时间复杂度$O(n)$