C#与数据结构－－哈希表（Hashtable）

核心提示： Hashtable解决冲突使用了双重散列法，但又跟前面所讲的双重散列法稍有不同，C#与数据结构－－哈希表（Hashtable）(4)，它探测地址的方法如下：h(key, i) = h1(key) + i * h2(key)其中哈希函数h1和h2的公式如下：h1(key) = key.Get

Hashtable解决冲突使用了双重散列法，但又跟前面所讲的双重散列法稍有不同。它探测地址的方法如下：

h(key, i) = h1(key) + i * h2(key)

其中哈希函数h1和h2的公式如下：

h1(key) = key.GetHashCode()

h2(key) = 1 + (((h1(key) >> 5) + 1) % (hashsize - 1))

由于使用了二度哈希，最终的h(key, i)的值有可能会大于hashsize，所以需要对h(key, i)进行模运算，最终计算的哈希地址为：

哈希地址 = h(key, i) % hashsize

【注意】：bucket结构体的hash_coll字段所存储的是h(key, i)的值而不是哈希地址。

哈希表的所有元素存放于一个名称为buckets（又称为数据桶） 的bucket数组之中，下面演示一个哈希表的数据的插入和删除过程，其中数据元素使用（键，值，哈希码）来表示。注意，本例假设Hashtable的长度为11，即hashsize = 11，这里只显示其中的前5个元素。

（1）　　　　　　 插入元素（k1，v1，1）和（k2，v2，2）。

由于插入的两个元素不存在冲突，所以直接使用h1(key) % hashsize的值做为其哈希码而忽略了h2(key)。其效果如图8.6所示。

（2）　　　　　 插入元素（k3，v3，12）

新插入的元素的哈希码为12，由于哈希表长为11，12 % 11 = 1，所以新元素应该插入到索引1处，但由于索引1处已经被k1占据，所以需要使用h2(key)重新计算哈希码。

h2(key) = 1 + (((h1(key) >> 5) + 1) % (hashsize - 1))

h2(key) = 1 + ((12 >> 5) + 1) % (11 - 1)) = 2