哈希表中元素冲突的三种常用探测方式
时间：2010-11-29 来源：Vagrant-Benz
“嘘…! 我正在看Hash呢！”
“好家伙，又在自我欣赏了！那也得用镜子啊，怎么想起用电脑屏幕当镜子了？ 这种癖好不会是遗传的吧？”
“哪的话啊！ 我是在看算法中 哈希这一节呢，只是有些问题想不明白，要不你给我讲讲？”
“那可不敢当。我对此也不是很懂，不过可以讨论讨论。”
“我们知道哈希表中的元素是由哈希函数Hash来确定的。也就是说 每个元素在哈希表中的位置可以通过哈希函数Hash(x)来确定，下面代码就是一个简单的哈希函数：它是将字符串中的每个字符的ASCII值进行相加，并对哈希表的大小进行求余”
int hash( const std::string &key, int tableSize )
{
int hashVal = 0;
for ( size_t i=0; i<key.length(); ++i )
{
hashVal += key.at(i);
}
return ( hashVal % tableSize );
}
“但是由于不同的元素x通过 Hash(x) 得到的值-即元素所存储在Hash表中的位置，可能会相同，以至于出现冲突。处理这种冲突常用的有 线性探测法(Linear Probing )， 二次探测法(Quadratic Probing)， 双重Hash (Double Hashing )。”
“其实这些形式都是相同的： 如 hi(x) = ( hash(x) + f(i) ) mod TableSize ,这里的f(i) 即为 线性函数 f(i) = i ， 二次函数 f(i) = i*i 和双重Hash函数 f(i) = i*hash2(x) 并且满足 f(0) = 0 特性”
“接下来我就以 二次探测举例说明 它是如何处理 哈希表中元素位置冲突问题。假如我现在要对长度为 10的哈希表中依次插入元素{ 33, 18, 49, 58, 69 } ”
二次探测 
进行二次探测后的Hash值 
|
元素 |
Hash函数值 |
位置 |
|
33 |
Hash(33) = 33%10 = 3 |
3 |
|
18 |
Hash(18) = 18%10 = 8 |
8 |
|
49 |
Hash(49) = 49%10 = 9 |
9 |
|
58 |
Hash(58) = 58%10 = 8 冲突
|
2 |
|
69 |
Hash(69) = 69%10 =9 冲突
|
0 |
依次插入 { 33, 18, 49, 58, 69 }
得到一个表：
|
位置 |
插入前 |
插入33后 |
插入18后 |
插入49后 |
插入58后 |
插入69后 |
|
0 |
|
|
|
|
69 |
|
|
1 |
|
|
|
|
|
|
|
2 |
|
|
|
58 |
58 |
|
|
3 |
33 |
33 |
33 |
33 |
33 |
|
|
4 |
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
8 |
|
18 |
18 |
18 |
18 |
|
|
9 |
|
|
49 |
49 |
49 |
注意：在处理冲突的时候，一般元素的个数最好不要超过TableSize(此处为10) 的一半，要不然会降低算法执行效率
当元素大于一半的时候，最好调用 rehash() 函数，用来扩大哈希表的大小
“我所能理解的都在这里了，到你了……”
相关阅读 更多 +
