什么散列
散列是提供对任何有名项提供存取操作和删除操作的列表。这种结构的目的是提供常数时间的基本操作。
举个例子：如果所有元素都是16-bits且不带正负号的整数，范围是0-65535。那么简单运用一个 array 就可以满足上面的期望。首先配置一个arrayA.，拥有65536个元素，初值全部为0，每个元素值代表相应元素出现的次数。如果插入元素i，就执行A[i]++，如果删除元素i，就执行A[i]--，如果搜素元素就检查A[i]是否为0。以上的每一个操作都是常数时间。这种解法的额外负担是array的空间和初始化时间。
绘图1.jpg
但是这种解法存在2个现实的问题：
- 如果元素很多，那么要准备的数组大小就很大，空间占用太大。
- 如果元素是其他的类型（非整型），那么就不能作为数组索引。
第一个问题：
我们是可以采用一个映射函数，将大数转换为小数，比如给定整数x，那么
x % array.size()，那么就会得到一个范围在 [ 0，array.size() - 1 ] 之间的数，也可以作为数组索引，但这会引入新的问题：如何解决碰撞冲突的问题。
第二个问题：
我们可以将一个非整数类型的转换为整型，比如字符串"string"，转换为ASCII编码。
线性探测
当用散列函数计算出元素的插入位置，而该位置已经不能使用时，最简单的办法就是循序往下一一寻找，直到找到一个可用的位置为止。
元素的删除则可以采用"惰性删除"，也就是标记删除记号，实际删除则待散列表重新整理时再进行。
线性探测.jpg
但线性探测会有一个不好的现象是：如图最后状态中，除非元素进过散列函数计算之后直接得出位置在#4 ~ #7，否则#4 ~ #7永远不可能会被优先考虑，因为(8 9 0 1 2已被占，遇到冲突会线性巡访整个表格) #3一直会被优先考虑。
这样会暴露出一个问题：主集团(primary clustering)陷阱。散列表中是一大团被用过的方格，插入操作极有可能在主集团所形成的泥泞中奋力爬行，不断解决碰撞问题，最后再找到空位置。然而插入之后又助长了主集团的长度。
public class LinearProbingHashST<Key, Value> {
private int n; // 当前key-value元素对数
private int m; // 线性表（key-value）的总长度
private Key[] keys; // the keys
private Value[] vals; // the values
public void put(Key key, Value val) {
.....省略参数的有效性判断
// 如果已经用掉50%，则扩容，减小主集团的影响
if (n >= m / 2)
resize(2 * m); // resize里面会重新计算散列值，插入元素
// 线性探测过程
for (int i = hash(key); keys[i] != null; i = (i + 1) % m) {
// 如果已经存在key，则更新value
if (keys[i].equals(key)) {
vals[i] = val;
return;
}
}
keys[i] = key;
vals[i] = val;
n++;
}
public void delete(Key key) {
...... 省略参数有效性判断
// find position i of key
int i = hash(key);
while (!key.equals(keys[i]))
i = (i + 1) % m;
// delete key and associated value
keys[i] = null;
vals[i] = null;
// rehash all keys in same cluster
i = (i + 1) % m;
while (keys[i] != null) {
// delete keys[i] an vals[i] and reinsert
Key keyToRehash = keys[i];
Value valToRehash = vals[i];
keys[i] = null;
vals[i] = null;
n--;
put(keyToRehash, valToRehash);
i = (i + 1) % m;
}
n--;
// halves size of array if it's 12.5% full or less
if (n > 0 && n <= m / 8)
resize(m / 2);
}
}
二次探测
二次探测主要用于解决主集团的问题。
其命名由来是因为解决碰撞的方程式：F(i) = i^2是一个二次方程式。更明确的说，如果散列函数计算出新元素位置H，而该位置实际上已经被使用，那么我们就依次尝试H+12，H+22，H+3^2......而不是像线性探测一样依序尝试：H+1，H+2，H+3.......
二次探测.jpg
二次探测可以消除主集团，但却可能造成次集团：两个元素经散列函数计算出来的位置若相同，那么插入时所探测的位置也相同，形成某种浪费。
但总体来说，还是二次探测相比于线性探测，仍然值得选择。
开链法
开链法是在每一个表格元素中维护一个list，散列函数分配某一个list，然后再那个list身上执行元素的插入，搜寻，删除等操作。虽然针对list是一种线性搜索，但list够短。速度还是很快。
开链法jpg
散列函数
参考资料
[1] 《STL源码剖析》侯捷
[2] 《算法》4th [美] Robert Sedgewick，Kevin Wayne
网友评论