此文是转载，随便兜兜转载。

算法导论-散列表

散列表 - 常用的构造散列函数的方法

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位

1、直接寻址表

　　当关键字的的全域（范围）U比较小的时，直接寻址是简单有效的技术，一般可以采用数组实现直接寻址表，数组下标对应的就是关键字的值，即具有关键字k的元素被放在直接寻址表的槽k中。直接寻址表的字典操作实现比较简单，直接操作数组即可以，只需O(1)的时间。

2 、散列表
当全域U很大的时候，由于内存的限制，直接寻址表出现问题，因此可以用散列表解决。对于直接寻址表，具有关键字k的元素在槽k中，而该元素则在散列表的h(k)处，其中，h(k)是散列函数，这个函数将全域U映射到散列表T的[0...m-1]的槽位上。对于两个关键字映射到同一个槽位上的情况，我们称之为碰撞。
解决碰撞有：

• 链接法解决碰撞
• 开放寻址法

1.2.1 将关键字解释为自然数
比如：一个字符串关键字可以被解释为按适当的基数记号表示的整数。如pt表示为(112 * 128) + 116 = 14452。这将字符串看成是以128为基数的整数。
1.2.2 除法散列法
h(k) = k mod m，通过取k除以m的余数来将关键字k映射到m个槽的某一个中去。
注意除数m的选择，m不应该是2的幂，因为如果m = 2^p，则h(k)就是k的p个最低位数字。并且，当k是一个按基数2^p解释的字符串时，选m = 2^p - 1可能是个比较糟糕的选择，因为将k的各字符进行排列并不会改变h(k)的值，这个证明比较简单，略。一般选取m为与2的幂不太接近的素数。
1.2.3 乘法散列法
h(k) = ⌊m(kA - ⌊kA⌋)⌋。其中A为(0,
1)之间的常数。m一般选为2的某个幂次。Knuth认为A ≅(√5
- 1)/2 = 0.6180339887…是一个比较理想的值。

4、开放寻址法
在开放寻址法中，所有的元素都存放在散列表中，和连接法处理冲突时采用连接形式不同，开放寻址法的散列表每个表项或包含动态集合的一个元素，或包含NIL。
在开放寻址法中，当要插入一个元素时，可以连续地探查散列表的各项，直到找到一个空槽来放置待插入的关键字为止。
1.3.1 线性探查
h(k, i) = (h'(k) + i) mod m, i = 0, 1, ... ,m - 1
在线性探查方法中，初始探查位置确定了整个序列，因此只有m种不同的探查序列。且它存在一次群集现象。
1.3.2 二次探查

h(k, i) = (h'(k) + c * i + d * i^2) mod m
其中c和d为辅助常数。初始探查位置为T[h'(k)]，后续的探查位置要在此基础上加上一个偏移量，该偏移量以二次的方式依赖于探查号i。它比线性探查好的多。但是如果两个关键字初始探查位置相同，那么他们的探查序列也是相同的。因此它存在程度较一次群集轻的二次群集现象。
1.3.3 双重散列
h(k, i) = (f(k) + i * g(k)) mod m
其中f(k)和g(k)为辅助散列函数。与线性探查和二次探查不同的是，这里的探查序列以两种方式依赖于关键字k。为能查找整个散列表，值g(k)要与m互素。可以取m为2的幂，并设计g(k)为总产生奇数。或者取m为素数，设计g(k)总产生比m小的正整数。比如：可以取m为素数，并取f(k) = k mod m, g(k) = 1 + (k mod n) 其中n略小于m（比如为m - 1）。双重散列法用了θ(m^2)种探查序列。

每日一C

程序=数据结构+算法