本系列为数据结构学习笔记(待汇总)。
1 散列表
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。即:
存储位置=f(关键字)
采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表或哈希表，关键字对应的记录存储位置称为散列地址。
散列技术既是一种存储方法，也是一种查找方法。它也线性表、树、图等结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线图示表示出来，而散列技术的记录之间不存在什么逻辑关系，它只与关键字关联。因此，散列主要是面向查找的存储结构，适合求解的问题是查找与给定值相等的记录。
1.1 散列冲突
每个关键字 $key1 \not= key2$，但却有$f(key1) = f(key2)$，这种现象称为冲突，并把key1和key2称为这个散列函数的同义词。出现了冲突当然非常糟糕，那将造成数 据查找错误。
2 散列函数的构造方法
2.1 构造原则
- 计算简单。散列函数的计算时间不应该超过其他查找技术与关键字比较的时间。
- 散列地址分布均匀。尽量让散列地址均匀地分布在存储空间中，保证存储空间的有效利用，并减少为处理冲突而耗费的时间。
2.2 构造方法
2.2.1 直接定址法
取关键字的某个线性函数值为散列函数，即：
$f(key) = a * key + b$，（a、b为常数）
- 优点是简单、均匀、不会产生冲突
- 缺点是需要首先知道关键字的分布情况，适合查找表较小且连续的情况
2.2.2 数字分析法
基于抽取的方法，即使用关键字的一部分来计算散列存储位置的方法。
适合处理关键字位数比较大的情况，如果事先知道关键字的分布 且关键字的若干位分布较均匀，就可以考虑用这个方法。
2.2.3 平均取中法
先对关键字求平方，在抽取中间的k位作为散列地址。
比如关键字是 1234， 那么它的平方就是 1522756，再抽取中间的 3 位就是 227 ，用做散列地址。
适合于不知道关键字的分布，且位数不是很大的情况。
2.2.4 折叠法
将关键字从左到右分割成位数相等的几部分(注意最后一部分位数不够 时可以短些) ，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
比如我们的关键字是 9876543210 ，散列表表长为三位，我们将它分为四组， 9871654132110， 然后将它们叠加求和987+654+321+0=1962，再求后 3 位得到散列 地址为 962。
有时可能这还不能够保证分布均匀 ， 不妨从一端向另一端来回折叠后对齐相加。 比如我们将 987 和 321 反转，再与 654 和 0 相加， 变成 789+654+123+0=1566，此时散列地址为 566.
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。
2.2.5 除留余数法
对于散列表长为m的散列函数公式为：
$f(key) = key mod p, (p \leq m)$
不仅可以对关键字直接取模，还可在折叠、平方取中后再取模。
2.2.6 随机数法
选择一个随机数，取关键字的随机函数值为它的散列地址。即：
$f (key) =random (key)$
这里 random 是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。
3 散列冲突的处理方法
3.1 开放定址法 (线性探测法)
一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。公式为：
$f_i (key) = (f(key) + d_i) mod m, (d_i = 1,2,3,…,m-1)$
- 堆积：两个关键字同时争夺同一个地址。此时需要不断处理冲突，降低存入和查找的效率。
- 解决方法1：二次探测法，增加平方运算使关键字尽可能分散。即：
$f_i (key) = (f(key) + d_i) mod m, (d_i = 1^2, -1^2, 2^2, -2^2 ,…,q^2, -q^2, q \leq m/2)$ - 解决方法2：随机探测法，在冲突时，对于位移量 $d_i$，采用随机函数计算得到。即：
$f_i (key) = (f(key) + d_i) mod m, d_i )$是一个随机数列
3.2 再散列函数法
换一个不同的函数重新计算散列地址。
$f_i (key) = RH_i(key), i=1,2,…,ki )$
$RH_i$为不同的散列函数，如除留余数、折叠、平方取中等。
3.3 链地址法
不存在冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。但带来了查找时需要遍历单链装的性能损耗。
3.4 公共溢出区法
为所有冲突的关键字建立一个公共的溢出区来存放。
查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，
- 如果相等，则查找成功；
- 如果不相等，则到溢出表去进顺序查找；
- 如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。
4 散列表查找性能
时间复杂度为O(1)。
参考文献：
程杰. 大话数据结构
