哈希表总结

Hasb表又成散列表，用来实现立即查找数据的一种数据结构。
Hash函数：记录存放位置和数据项之间的对应关系。存储位置location = hash(key)

哈希函数要求

哈希函数有几个要求需要满足：

• 哈希函数的定义域必须包括需要存储的全部关键码，如果哈希表允许有n个地址时，其值域必须在0到n-1之间。
• 哈希函数计算出来的地址应该能均匀的分布在整个地址空间，即哈希函数应能以相同的概率取到0到n-1之间的每一个值。
• 哈希函数应该是简单能在较短时间内计算出结果。

Hash冲突

key值的取值范围比哈希表地址集合大得多，因此有可能经过哈希函数计算不同的key值映射到同一个哈希地址上，这就产生冲突。

从两个方向解决哈希冲突：

• 对应给定的key码集合，选择一个计算简单且能分补均匀的哈希函数，尽量减少哈希冲突
• 制定解决冲突的方案

哈希函数构造方法

• 直接定址法
  例如统计1到100岁的人口数量，以年龄作为key，哈希函数取key自身。
• 数字分析法
  例如同一个班级里面学生的出生日期，如2000.1.01，其中前5位重复的可能性非常高，取这5位的造成hash冲突的可能性极高，那就不选择前5位，可以选择后几位。
• 平方取中法
  取key值平方后中间几位作为哈希函数的地址，是一种常见的哈希函数构造方法。这是因为一个数平方后中间几位数和数的每一位都相关。
• 折叠法
  将key值分割成位数相同的几部分，最后一部分可以不同，然后将这几部分叠加取和(舍去进位)作为哈希地址。
• 除余法
  取一个最接近于n的质数p，利用以下公式把关键码转换成哈希地址：hash(key) = key % p;
• 随机数法
  选择一个随机函数，取key的随机函数值作为哈希地址，即：hash(key) = random(key);

哈希冲突解决方法

一、开放定址法

用开放地址法解决冲突的做法是：当冲突发生时，使用某种探查技术在散列表中形成一个探查序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存入该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。

开放地址法的一般形式：

/*
  h(key)为散列函数，di为增量序列，m为表长
  h(key)是初始的探查位置，后续的探查位置依次是hl，h2，…，hm-1，即h(key)，hl，h2，…，hm-1形成了一个探查序列。
*/
  hi=(h(key)+di)%m 1≤i≤m-1

装填因子：散列表中的元素个数与散列表大小的比值。
开放地址法堆装填因子的要求：
开放地址法要求散列表的装填因子α≤l，实用中取α为0.5到0.9之间的某个值为宜。

形成探测序列的方法：

• 1、线性探查法(Linear Probing)
  将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：
  d，d+l，d+2，…，m-1，0，1，…，d-1
  即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。

探查过程终止于三种情况：
(1)若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；
(2)若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；
(3)若探查到T[d-1]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败(此时表满)。

线性探查法的探查序列为：
hi=(h(key)+i)%m 0≤i≤m-1 //即di=i

• 2、二次探查法(Quadratic Probing)
  二次探查法的探查序列是：hi=(h(key)+i*i)%m 0≤i≤m-1 //即di=i2
  即探查序列为d=h(key)，d+12，d+22，…，等。该方法的缺陷是不易探查到整个散列空间。

• 3、双重散列法(Double Hashing)
  该方法是开放地址法中最好的方法之一，它的探查序列是：hi=(h(key)+ih1(key))%m 0≤i≤m-1 //即di=ih1(key)
  即探查序列为：d=h(key)，(d+h1(key))%m，(d+2h1(key))%m，…，等。
  该方法使用了两个散列函数h(key)和h1(key)，故也称为双散列函数探查法。

二、 拉链法

拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。即每个位置上存放的是一个单链表，相同的地址的元素依次是链表上的节点。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。

拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可；

拉链法的缺点是：指针需要额外的空间，当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

三、多哈希法

设计二种甚至多种哈希函数，可以避免冲突，但是冲突几率还是有的，函数设计的越好或越多都可以将几率降到最低（除非人品太差，否则几乎不可能冲突）。

参考文献：再散列法