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

核心提示： （2） 与所采用的哈希函数有关，若哈希函数选择得当，C#与数据结构－－哈希表（Hashtable）(2)，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生；否则，则得到的探测序列为：(h1(key)+h2(key))%m，(h1(key)+2h2(key))%m，就可能使

（2）　　　　　　 与所采用的哈希函数有关。若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生；否则，就可能使哈希地址集中于某些区域，从而加大冲突发生的可能性。

冲突解决技术可分为两大类：开散列法（又称为链地址法）和闭散列法（又称为开放地址法）。哈希表是用数组实现的一片连续的地址空间，两种冲突解决技术的区别在于发生冲突的元素是存储在这片数组的空间之外还是空间之内：

（1）　　　　　　 开散列法发生冲突的元素存储于数组空间之外。可以把“开”字理解为需要另外“开辟”空间存储发生冲突的元素。

（2）　　　　　　 闭散列法发生冲突的元素存储于数组空间之内。可以把“闭”字理解为所有元素，不管是否有冲突，都“关闭”于数组之中。闭散列法又称开放地址法，意指数组空间对所有元素，不管是否冲突都是开放的。

8.3.1　 闭散列法（开放地址法）

闭散列法是把所有的元素存储在哈希表数组中。当发生冲突时，在冲突位置的附近寻找可存放记录的空单元。寻找“下一个”空位的过程称为探测。上述方法可用如下公式表示：

hi=(h(key)+di)%m　　　　　 i=1，2，…，k (k≤m-1)

其中h(key)为哈希函数；m为哈希表长；di为增量的序列。根据di取值的不同，可以分成几种探测方法，下面只介绍Hashtable所使用到的双重散列法。

双重散列法

双重散列法又称二度哈希，是闭散列法中较好的一种方法，它是以关键字的另一个散列函数值作为增量。设两个哈希函数为：h1和h2，则得到的探测序列为：

(h1(key)+h2(key))%m，(h1(key)+2h2(key))%m，(h1(key)+3h2(key))%m，…