散列表查找

什么是哈希表？

根据关键码值（key value）直接进行访问的数据结构，也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找速度，这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

简单的理解为，按照关键字为每一个元素『分类』，然后将这个元素存储在相应的『类』所对应的地方。但是，不能够保证每一个元素与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了『冲突』。也就是把不同的元素分在了相同的『类』中。

综上，『直接定址』与『解决冲突』是哈希表的两大特点

什么是哈希函数？

哈希函数的规则是：通过某种转换关系，使关键字适度的分散到指定大小的顺序表结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高

算法思路：哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

算法流程：

1. 用给定的哈希函数构造哈希表
2. 根据选择的冲突处理方式解决地址冲突
3. 在哈希表的基础上执行哈希查找

常见的哈希函数构造方法

直接定址法

取关键字或关键字的某个线性函数值为散列地址 $$ hash(key) = key 或 hash(key) = a * key + b，其中 a 和 b 为常数 $$ 比如：以年龄作为关键字的散列表

除留余数法

取关键字被某个不大于散列表长度 m 的树 p 求余，得到的值作为散列地址。对除数 p 的选择很重要，若 p 选择的不好，则很容易产生冲突。

即：hash(key) = key % p, p<m

比如：取模为 1000

数字分析法

当关键字的位数大于地址的位数，对关键字的各位分别进行分析，选出分布解决的任意几位作为散列地址。适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突

比如：手机尾号后四位

平方取中法

先计算出关键字的平方，然后取平方值中间几位作为散列地址。

折叠法

将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址。适用于关键字位数较多，并且关键字中每一位上数字分布大致均匀

随机数法

选择一个随机函数，把关键字的随机函数值作为它的哈希值。一般当关键字的长度不等时采用这个方法

哈希冲突

若 key1 != key2，而 hash(key1) == hash(key2)，则这种现象称为冲突，且 key1 和 key2 对于哈希函数 hash 来说是同义词

哈希冲突的解决方法

开放定址法

当冲突发生时，使用某种探查技术在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。

按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。

• 线性探查法：hi = (hash(key)+i) ％ m ，0 ≤ i ≤ m-1

  思想：探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1]，…，直到 T[m-1]，此后又循环到 T[0]，T[1]，…，直到探查到 有空余地址 或者到 T[d-1]为止。

• 二次探查法：hi = (hash(key)+i*i) ％ m，0 ≤ i ≤ m-1

  思想：探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1^2]，T[d+2^2]，T[d+3^2],…，等，直到探查到 有空余地址 或者到 T[d-1]为止。

• 双重散列法：hi = (hash(key)+i*hash1(key)) ％ m，0 ≤ i ≤ m-1

  思想：探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+h1(d)], T[d + 2*h1(d)]，…，等。该方法使用了两个散列函数 h(key) 和 h1(key)，故也称为双散列函数探查法。

  定义 hash1(key) 的方法较多，但无论采用什么方法定义，都必须使 hash1(key) 的值和 m 互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。

再哈希法

这种方法是同时构造多个不同的哈希函数： Hi = RH1（key） i=1，2，…，k 当哈希地址 Hi = RH1（key）发生冲突时，再计算 Hi = RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

链地址法（拉链法）

将所有关键字为同义词的结点链接在同一个单链表中。

若选定的散列表长度为 m，则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1] 。

凡是散列地址为 i 的结点，均插入到以 T[i] 为头指针的单链表中。

公共溢出法

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。