数据结构--哈希表

在介绍哈希表之前，先介绍一下查找表

查找表(Search Table)

查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵活的数据结构

对表的操作

查询某个“特定的”的数据元素是否在查找表中。
检索某个“特定的”数据元素的各种属性。
在查找表中插入一个数据元素
从查找表中删去某个元素。

查找表根据其操作的不同又分为以下两种：

若对查找表只作前两种统称为“查找”的操作，则称此类查找表为静态查找表(Static Search Table)。
若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类表为动态查找表(Dynamic Search Table)

名词定义

为了解释“特定的”，引入了关键字:

关键字是数据元素(或记录)中某个数据项的值，用它可以标识一个数据元素(或记录)。

接着定义查找:

根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。

哈希表

查找的效率依赖于查找过程中所进行的比较次数。

哈希(Hash)函数

理想的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个对应关系$f$，使每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系$f$找到给定值$K$的像$f\left ( K \right )$。若结构中存在关键字和$K$相等的记录，则必定在$f\left ( K \right )$的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，我们称这个对应关系$f$为哈希函数，按这个思想建立的表为哈希表。

哈希函数的特征

哈希函数是一个映像，因此哈希函数的设定很灵活，只要是的任何关键字由此所得的哈希函数值都落在表长允许的范围内即可。
对不同的关键字可能得到同一哈希地址，即$key_{1}\neq key_{2}$，而$f\left ( key_{1} \right )= f\left ( key_{2} \right )$，这种现象称为冲突(collision)。

哈希表定义

综上，可如下描述哈希表：

根据设定的哈希函数$H\left ( key \right )$和处理冲突的方法将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表，这一映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。

哈希函数的构造方法

若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数为均匀的(Uniform)哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突

直接定址法：取关键字或关键字的某个线性函数值作为哈希地址。即：

$H\left ( key \right )= key$ $H\left ( key \right )= a\cdot key+b$

数字分析法：假设关键字是以$r$为基的数(如：以10为基的十进制数)，并且哈希表中可能出现的关键字都是事先知道的，则可以取关键字的若干数位组成哈希地址。
平方取中法：取关键字平方后的中间几位为哈希地址。
折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为哈希地址。
除留余数法：取关键字被某个不大于哈希表表长$m$的数$p$除后所得的余数为哈希地址。即:

$H\left ( key \right )= key\left ( MOD \right )p, p\leq m$

处理冲突(collision)

上文提到的均匀的哈希函数可以减少冲突，但不能避免，因此如何处理冲突时哈希造表不可缺少的另一方面。通常用的处理方法如下：

开放地址法其中：$H\left ( key \right )$为哈希函数；$m$为哈希表表长；$d_{i}$为增量序列，有下列三种取法：
1. $d_{i}=1,2,3,…,m-1$称线性探测再散列；
2. $d_{i}=1^{2},-1^{2},2^{2},-2^{2},3^{2},…,\pm k^{2},\left (k\leq m/2 \right)$称二次探测再散列；
3. $d_{i}=伪随机数序列$，称伪随机探测再散列。
再哈希法 $H_{i}=RH_{i}\left (key \right), i=1,2,...,k$ $RH_{i}$均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不在发生。这种方法不易产生“聚集”，但增加了计算的时间。
链地址法
将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间$\left [ 0,m-1 \right ]$上，则设立一个指针型向量 $ChainHash\left [m \right]$ 其每个分量的初始状态都是空指针。凡哈希地址为$i$的记录都插入到头指针为$ChainHash\left [i \right]$的链表中。在链表中的插入位置可以在表头或表尾；也可在中间，以保持同义词在同一线性链表中按关键字有序。
建立公共溢出区
假设哈希函数的值域为$\left [0,m-1 \right]$，则设向量$HashTable\left [0..m-1 \right]$为基本表，每个分量存放一个记录，另设立向量$OverTable\left [0..v \right]$为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。

哈希表应用算法案例

两数之和(2 Sum)

问题描述：

输入一个数组nums和一个数target，返回数组nums中两个数的和为target的这两个数的下标(index),下标从1开始。例子：
nums = [2, 7, 11, 15], target = [9]
返回[1, 2]

问题分析：
有两个输入：nums和target，一个输出：两个下标，目的是找到两个数之和等于target。显而易见的一种方法是写两个for循环嵌套：外部循环从数组的第一个元素开始向后遍历作为第一个数nums[i]，内部循环从第一个数的下一个数nums[i+1]开始向后遍历，判断两个数之和是否等于target，找到后返回两个下标即可。不过这样做有明显的缺点：两个循环的算法时间复杂度为$O\left (n*(n-1)\right)$，那么如果nums中有9个元素，最多会遍历9x8=72次，对于更大的nums遍历次数将更多。所以我们来“算算”怎么简化算法。

解决方案：
我们设找到的两个数中第一个为$x_{i}$，第二个数为$x_{j}$，进行运算：

$x_{i}+x_{j}=target\tag{1}$ $x_{j}=target-x_{i}\tag{2}$

进行上述的运算后可以发现等式(1)中的左边部分有两个未知数，而等式右边只有一个未知数，于是我们可以得到一个下标$i$到$j$的映射：$f\left (i\right)=j$，从而我们可以利用等式(2)来重新构造我们的for循环，即使用一次for循环。
程序实现：
用python来实现这个算法，其中python中的字典可以作为很好的哈希映射。代码如下：

def two_num(nums, target):
    """
    solve the problem 2 sum
    :param nums: the set of some numbers
    :param target: the sum of two numbers
    :return: the index of two numbers
    """
    hash_map = {}
    for ind, val in enumerate(nums):
        if (target - val) in hash_map:
            return hash_map[target - val]+1, ind+1
        hash_map[val] = ind


ans = two_num([2, 7, 11, 15], 9)
print(ans)

输出：(1, 2)
代码分析：
分析代码可知，首先创建一个空的字典，该字典用来实现哈希映射，接着我们对数组的每一个元素进行迭代，获取元素的下标和元素值，接着进行判断：如果另一个元素在字典中，则返回另一个元素在字典中的值和当前元素的下标。
否则，更新字典，把元素作为字典的键（这样就不必担心重复的元素），把元素的下标作为值，然后继续循环。回过头来可以发现我们最终返回的就是两个数的下标值。

结语

由上述案例可知哈希思想作为数据结构的应用带来的算法效能提升，在平时的算法编写中应考虑到时间和空间上的条件，利用数据结构的知识来不断优化算法。