链接：
C#中实现了哈希表数据结构的集合类有：
（1） System.Collections.Hashtable
（2） System.Collections.Generic.Dictionary<tkey,tvalue>
前者为一般类型的哈希表，后者是泛型版本的哈希表。Dictionary和Hashtable之间并非只是简单的泛型和非泛型的区别，两者使用了完全不同的哈希冲突解决办法。Dictionary我已经做了动态演示程序，使用的是Window应用程序。虽然Dictionary相对于Hashtable来说，更优美、漂亮，但总觉得如果不给Hashtable也配上动态演示程序，也是一种遗憾。这次使用了Silverlight来制作，原因很简单，它可以挂在网上让大家很方便地观看。
先来看看效果，这里需要注意，必须安装Silverlight 2.0 RTW 才能正常运行游戏，下载地址：
程序中的键编辑框中只接受整数，因为整数的哈希码就是整数本身，这可以让大家更直观地查看哈希表的变化。如果输入了非法字符，则会从0至999中随机抽取一个整数进行添加或删除操作。
哈希冲突解决方法
哈希函数的目标是尽量减少冲突，但实际应用中冲突是无法避免的，所以在冲突发生时，必须有相应的解决方案。而发生冲突的可能性又跟以下两个因素有关：
（1） 装填因子α：所谓装填因子是指合希表中已存入的记录数n与哈希地址空间大小m的比值，即 α=n / m ，α越小，冲突发生的可能性就越小；α越大（最大可取1），冲突发生的可能性就越大。这很容易理解，因为α越小，哈希表中空闲单元的比例就越大，所以待插入记录同已插入的记录发生冲突的可能性就越小；反之，α越大，哈希表中空闲单元的比例就越小，所以待插入记录同已插入记录冲突的可能性就越大；另一方面，α越小，存储窨的利用率就越低；反之，存储窨的利用率就越高。为了既兼顾减少冲突的发生，又兼顾提高存储空间的利用率，通常把α控制在0.6～0.9的范围之内，C#的HashTable类把α的最大值定为0.72。
（2） 与所采用的哈希函数有关。若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生；否则，就可能使哈希地址集中于某些区域，从而加大冲突发生的可能性。
冲突解决技术可分为两大类：开散列法（又称为链地址法）和闭散列法（又称为开放地址法）。哈希表是用数组实现的一片连续的地址空间，两种冲突解决技术的区别在于发生冲突的元素是存储在这片数组的空间之外还是空间之内：
（1） 开散列法发生冲突的元素存储于数组空间之外。可以把“开”字理解为需要另外“开辟”空间存储发生冲突的元素。
（2） 闭散列法发生冲突的元素存储于数组空间之内。可以把“闭”字理解为所有元素，不管是否有冲突，都“关闭”于数组之中。闭散列法又称开放地址法，意指数组空间对所有元素，不管是否冲突都是开放的。
闭散列法（开放地址法）
闭散列法是把所有的元素存储在哈希表数组中。当发生冲突时，在冲突位置的附近寻找可存放记录的空单元。寻找“下一个”空位的过程称为探测。上述方法可用如下公式表示：
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，…
其中，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
剖析System.Collections.Hashtable
万物之母object类中定义了一个GetHashCode()方法，这个方法默认的实现是返回一个唯一的整数值以保证在object的生命期中不被修改。既然每种类型都是直接或间接从object派生的，因此所有对象都可以访问该方法。自然，字符串或其他类型都能以唯一的数字值来表示。也就是说，GetHashCode()方法使得所有对象的哈希函数构造方法都趋于统一。当然，由于GetHashCode()方法是一个虚方法，你也可以通过重写这个方法来构造自己的哈希函数。
Hashtable的实现原理
Hashtable使用了闭散列法来解决冲突，它通过一个结构体bucket来表示哈希表中的单个元素，这个结构体中有三个成员：
（1） key ：表示键，即哈希表中的关键字。
（2） val ：表示值，即跟关键字所对应值。
（3） hash_coll ：它是一个int类型，用于表示键所对应的哈希码。
int类型占据32个位的存储空间，它的最高位是符号位，为“0”时，表示这是一个正整数；为“1”时表示负整数。hash_coll使用最高位表示当前位置是否发生冲突，为“0”时，也就是为正数时，表示未发生冲突；为“1”时，表示当前位置存在冲突。之所以专门使用一个位用于存放哈希码并标注是否发生冲突，主要是为了提高哈希表的运行效率。关于这一点，稍后会提到。
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
新的哈希地址为 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所示。