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

核心提示： 新的哈希地址为 h1(key) + i * h2(key) = 1 + 1 * 2 = 3，所以k3插入到索引3处，C#与数据结构－－哈希表（Hashtable）(5)，而由于索引1处存在冲突，所以需要置其最高位为“1”，如图8.8所示，当k1被删除后，(10000

新的哈希地址为 h1(key) + i * h2(key) = 1 + 1 * 2 = 3，所以k3插入到索引3处。而由于索引1处存在冲突，所以需要置其最高位为“1”。

(10000000000000000000000000000001)2 = (-2147483647)10

最终效果如图8.7所示。

（3）　　　　　　 插入元素（k4，v4，14）

k4的哈希码为14，14 % 11 = 3，而索引3处已被k3占据，所以使用二度哈希重新计算地址，得到新地址为14。索引3处存在冲突，所以需要置高位为“1”。

(12)10 = (00000000000000000000000000001100)2　　 高位置“1”后

(10000000000000000000000000001100)2 = (-2147483636)10

最终效果如图8.8所示。

（4）　　　　　　 删除元素k1和k2

Hashtable在删除一个存在冲突的元素时（hash_coll为负数），会把这个元素的key指向数组buckets，同时将该元素的hash_coll的低31位全部置“0”而保留最高位，由于原hash_coll为负数，所以最高位为“1”。

(10000000000000000000000000000000)2 = (-2147483648)10

单凭判断hash_coll的值是否为-2147483648无法判断某个索引处是否为空，因为当索引0处存在冲突时，它的hash_coll的值同样也为-2147483648，这也是为什么要把key指向buckets的原因。这里把key指向buckets并且hash_coll值为-2147483648的空位称为“有冲突空位”。如图8.8所示，当k1被删除后，索引1处的空位就是有冲突空位。