散列表-上

本文为数据结构与算法之美-王筝的学习笔记，如需查看完整版请参考链接。

散列表（Hash Table）的定义

散列表，又称“哈希表”或“Hash表”。散列表使用的是数组支持按照下标随机访问数据的特性，因而散列表就是数组的一种扩展，由数组演化而来。

假设有89位运动员，这些运动员的编号依次是0、1、2、…、87，希望通过运动员的编号快速查找对应运行员的信息。因为参赛编号和数组下标一一对应，因而我们可以将编号与数组的下标一一对应，编号为0的运动员的信息放在数组中下标为0的位置，以此类推。

因为参赛编号和数组下标一一对应，因而当我们需要创造编号为x的运动员的信息时，只需要将下标为x的数组元素取出来即可，时间复杂度为$O(1)$。

这就是典型的散列思想，参赛选手的编号被称为键（key）或者关键字，被用来标示一个选手；将参赛编号转换为数组下标的映射方法被称为散列函数（或“Hash函数”、“哈希函数”）；由散列函数计算得到的值被称作“散列值”（或“Hash值”、“哈希值”）。

因而，散列表主要利用的就是：

数组在利用下标进行访问的时候，时间复杂度为$O(1)$的特性。

通过使用散列函数把元素的键值映射为下标，并将元素的数据存储在数组中对应下标的位置。当按照键值查询元素时，使用同样的散列函数把键值转换为下标，从对应的数组下标的位置提取相应的数据即可。

因而散列表主要设计到两个核心问题：

可以将散列函数定义为$hash(key)$，其中key表示元素的键值，$hash(key)$的值表示经过散列函数计算得到的散列值。

对于上述运动员的例子，由散列函数计算得到的散列值就等于数组的下标。这样的例子中散列函数的构建比较简单，但是如果参赛选手的编号是随机生成的6位数字或者是a到z之间的字符串，那么该如何构建散列函数？在课程中，作者总结了三点散列函数设计的基本要求：

前两个要求很容易满足，但第三个要求在实际应用时比较难以满足，或者说是不可能的。将键值不同，散列值却相同的情况成为散列冲突。我们几乎无法找到一个完美的无冲突的散列函数。

正如上文中所述，我们无法完全解决散列冲突问题，那么应该如何缓解这一问题？常用的有以下两种解决方法：

核心思想是：

当出现散列冲突时，重新探测一个空闲位置，将其插入。

那么如何探测空闲位置？

方法之一是线性探测，原理是如果某个函数经过散列函数计算后，对应的存储位置已经被占用，则从当前位置开始，依次往后寻找，直到找到空闲位置。如下图所示，黄色位置为空闲，橙色为占用。

如上图所示，当查找到数组尾部仍旧未找到时，就从数组的头部开始。

在散列表中查找元素时，首先通过散列函数计算出要查找的元素的散列值，然后依据散列值找到对应位置的元素，如果对应位置处的元素和要查找的元素相等，则找到；否则继续向后查找，如果遇到数组中的空闲位置时仍旧没有找到，说明散列表中不存在要查找的元素。

除了插入、查找操作之外，散列表还支持删除操作。但是当插入元素时使用的是线性探测法时，就不能直接将待删除的元素对应的位置置空。在进行查找操作时，当遇到空闲位置时就认为不存在对应的元素，但如果空闲位置是由于删除操作导致的，查找操作便会失效。

解决方法是，使用特殊标记法，将被删除位置标记为deleted。

线性探测法存在的问题是，随着插入操作的进行，散列表中的元素越来越多，发生散列冲突的可能性将越来越大，空闲位置越来越少，线性探测的时间会越来越多。极端情况下，可能需要探测整个散列表。

在开放寻址冲突解决方法中，除了线性探测法之外，还有二次探测（Quadratic probing）和双重散列（Double hashing）方法。

二次探测是线性探测的变体，即每次探测的前进步长为前进次数的平方，即每次探测的下标为：$hash(key)+0,hash(key)+1^2,hash(key)+2^2$。

双重散列指的是使用多个散列函数，如果第一个散列函数计算得到的散列值位置不为空，则使用第二个散列函数计算散列值，以此类推。

除此之外还有一个概念，装载因子：

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

装载因子越大，空闲位置越少，发生散列冲突的可能性越大。

链表法是一种更常用的散列冲突解决方法，也更简单。在该方法中，散列表的每个“桶（bucket）”或者“槽（slot）”都会对应一个链表，散列值相同的元素存放在同一个链表中，如下图所示：

在进行元素插入时，只需要使用散列函数计算散列值，并将元素插入到对应的链表即可，插入的时间复杂度为$O(1)$。

而在进行元素查找和删除时，首先使用散列函数计算散列值，进而找到对应的链表，并从链表中找到或删除对应的元素。查找或删除的时间复杂度与链表的长度成正比，即$O(k)$，k为链表的长度。

在Word的单词拼写功能中就用到了散列表技术，将目前所有的单词组成散列表存在内存中，当用户输入某一个单词时，就使用散列函数计算散列值，并在散列表中进行查找，如果找到则说明拼写无误，否则就有可能出错。

假设有10万条URL访问日志，如何按照访问次数对URL排序？

使用URL作为键值，访问次数作为内容，将URL存储为散列表的形式，并记录下最大的访问次数k。这样一来一个散列值可能对应多个URL，如果k不打则使用桶排序，否则使用快排。
有两个字符串数组，每一个数组的长度都很长，如何找到两个数组中相同的字符串？

将第一个字符串数组存储为散列表的形式（使用链表法解决冲突），然后，对于第二个字符串数组中的每一个字符串都使用相同的散列函数计算散列值，然后对对应的链表进行查找，找到则存在，否则不存在。