这是数据结构类重新复习笔记的第 四 篇，同专题的其他文章可以移步：https://www.jianshu.com/nb/39256701

哈希（hashing）又称散列，是实现散列表的技术。散列是一种用于以常数平均时间执行插入、删除和查找的技术，因此涉及到元素间排序信息的操作不会得到支持，如树的findMin、findMax以及按照顺序打印列表这些操作散列是不支持的。

散列的基本思想

散列是一个固定大小的数组，存储的是键值对（Key--Value），键一般是好操作的数据，值一般存储比较大的实际意义强的数据，键的存在是便于使用键进行数据的查找。

散列的基本思想是使用一个对应关系（映射关系），这里称之为散列函数（hashing function），将哈希表的存储位置（0到TableSize-1）与键做一个对应，理想情况下是得到一个一一映射。但是这是不可能的，从而还需要确定一个方案来解决当两个键都被对应到同一个存储位置上时的情况，这个过程叫做解决冲突（collision）

散列函数

• 如果键时整数，一般使用 Key mod TableSize 作为对应的索引。通常，为了使哈希的分布均匀，通常采取素数大小的哈希表，当输入的键是随机整数的时候，散列函数不仅运算简单而且键的分配也很均匀
• 如果键时字符串
  • 一种策略是将字符串中字符的ASCLL码值求和，然后使用整数策略，这种方式不够均匀
  • 一种策略是取字符串的前几位的ASCLL码值求和，然后使用整数策略，这种方式不够均匀
  • 一种较好的策略是递归地求 h = k0+37 k1+37^2 k2 作为键，或者对一些选取的字符（而不是整个字符串）采用如上的策略

解决冲突的方法

无论如何设计散列函数，都能保证对于任何一个键都可以找到唯一的存储索引而不发生冲突，所以解决冲突是哈希实现的关键

分离链接法

分离链接法（separate chaining）将散列到同一个值的所有元素保存到一个链表中

分离链接法

这种方式的缺点是使用了一些链表，所以给新单元分配地址需要较多的时间开销。

探测散列表

一般为了减少使用链表带来的较大的时间开销，通常避免使用链表，而将所有的数据都放入表内，所以这种方式需要散列表要比较大才行。一般要求装填的数据和总数据含量之比小于0.5，这样的表成为探测散列表（probing hash tables）。

探测散列表的散列函数为 h(x)=(hash(x)+f(i)) mod TableSize 且 f(0)=0，说白了就是如果应该在的位置冲突了，就按照一定的规律去找下一个空位置，以此类推。根据寻找下一个空位置的方式不同可以分为如下的几种探测方式。

线性探测（Linear Probing）

f(i)=i，当一个位置出现冲突时，顺序查找下一个位置，直到找到一个空位置为止

线性探测

平方探测（Quadratic Probing）

f(i)=i^2，即冲突函数为二次函数的探测方法

二次探测

关于二次探测，这里有一个定理：如果表的大小是素数，那么当表至少有一半是空的时候，总能够插入一个新的元素

双散列（Double Hashing）

双散列（Double Hashing）也是一种解决冲突的方式，对于双散列，一种流行的方式是选择 f(i)=i*hash'(x), hash'(x)=R-(x mod R), 其中R通常选取一个素数。

双散列

再散列（Rehashing）

再散列（Rehashing）的思想是当一个散列表将要被耗尽时，建立一个新的比原来的表大约两倍的表并且使用新的散列函数，将原表中的数据通过新的散列函数安排到新表中。例如下边的例子：

首先有一个大小为7的散列表：

再散列例子

向这个表中插入数据23，得到了如下的表，由于此时数据已占用超过70%，从而创建一个新的大小为17的散列表。新的表的选取，是按照原来的散列表的二倍的后边第一个素数来规定。

再散列例子

将原来哈希表中的五个数据根据 key mod 17 再重新计算位置，添加到新的散列中去

再散列例子

---

转载请注明出处，本文永久更新链接：https://blogs.littlegenius.xin/2019/08/19/【数据结构】四散列/