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

核心提示： 其中，m为哈希表长，C#与数据结构－－哈希表（Hashtable）(3)，由此可知，双重散列法探测下一个开放地址的公式为：(h1(key) + i * h2(key)) % m (1≤i≤m-1)定义h2的方法较多，主要是为了提高哈希表的运行效率，关于这一点，但无采用什么方法都

其中，m为哈希表长。由此可知，双重散列法探测下一个开放地址的公式为：

(h1(key) + i * h2(key)) % m　　　　 (1≤i≤m-1)

定义h2的方法较多，但无采用什么方法都必须使h2(key)的值和m互素（又称互质，表示两数的最大公约数为1，或者说是两数没有共同的因子，1除外）才能使发生冲突的同义词地址均匀地分布在整个哈希表中，否则可能造成同义词地址的循环计算。若m为素数，则h2取1至m-1之间的任何数均与m互素，因此可以简单地将h2定义为：

h2(key) = key % (m - 2) + 1

8.4 剖析System.Collections.Hashtable

万物之母object类中定义了一个GetHashCode()方法，这个方法默认的实现是返回一个唯一的整数值以保证在object的生命期中不被修改。既然每种类型都是直接或间接从object派生的，因此所有对象都可以访问该方法。自然，字符串或其他类型都能以唯一的数字值来表示。也就是说，GetHashCode()方法使得所有对象的哈希函数构造方法都趋于统一。当然，由于GetHashCode()方法是一个虚方法，你也可以通过重写这个方法来构造自己的哈希函数。

8.4.1　 Hashtable的实现原理

Hashtable使用了闭散列法来解决冲突，它通过一个结构体bucket来表示哈希表中的单个元素，这个结构体中有三个成员：

（1）　　　　　　 key ：表示键，即哈希表中的关键字。

（2）　　　　　　 val ：表示值，即跟关键字所对应值。

（3）　　　　　　 hash_coll ：它是一个int类型，用于表示键所对应的哈希码。

int类型占据32个位的存储空间，它的最高位是符号位，为“0”时，表示这是一个正整数；为“1”时表示负整数。hash_coll使用最高位表示当前位置是否发生冲突，为“0”时，也就是为正数时，表示未发生冲突；为“1”时，表示当前位置存在冲突。之所以专门使用一个位用于存放哈希码并标注是否发生冲突，主要是为了提高哈希表的运行效率。关于这一点，稍后会提到。