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

核心提示：C#中实现了哈希表数据结构的集合类有：（1） System.Collections.Hashtable（2） System.Collections.Generic.Dictionary<TKey,TValue>前者为一般类型的哈希表，后者是泛型版本的哈希表，C#与数据结构－－哈希表（Hashtable），D

C#中实现了哈希表数据结构的集合类有：

（1） System.Collections.Hashtable

（2） System.Collections.Generic.Dictionary<TKey,TValue>

前者为一般类型的哈希表，后者是泛型版本的哈希表。Dictionary和Hashtable之间并非只是简单的泛型和非泛型的区别，两者使用了完全不同的哈希冲突解决办法。Dictionary我已经做了动态演示程序，使用的是Window应用程序。虽然Dictionary相对于Hashtable来说，更优美、漂亮，但总觉得如果不给Hashtable也配上动态演示程序，也是一种遗憾。这次使用了Silverlight来制作，原因很简单，它可以挂在网上让大家很方便地观看。

先来看看效果，这里需要注意，必须安装Silverlight 2.0 RTW 才能正常运行游戏，下载地址：http://www.microsoft.com/silverlight/resources/install.aspx?v=2.0

程序中的键编辑框中只接受整数，因为整数的哈希码就是整数本身，这可以让大家更直观地查看哈希表的变化。如果输入了非法字符，则会从0至999中随机抽取一个整数进行添加或删除操作。

8.3 哈希冲突解决方法

哈希函数的目标是尽量减少冲突，但实际应用中冲突是无法避免的，所以在冲突发生时，必须有相应的解决方案。而发生冲突的可能性又跟以下两个因素有关：

（1）　　　　　　 装填因子α：所谓装填因子是指合希表中已存入的记录数n与哈希地址空间大小m的比值，即 α=n / m ，α越小，冲突发生的可能性就越小；α越大（最大可取1），冲突发生的可能性就越大。这很容易理解，因为α越小，哈希表中空闲单元的比例就越大，所以待插入记录同已插入的记录发生冲突的可能性就越小；反之，α越大，哈希表中空闲单元的比例就越小，所以待插入记录同已插入记录冲突的可能性就越大；另一方面，α越小，存储窨的利用率就越低；反之，存储窨的利用率就越高。为了既兼顾减少冲突的发生，又兼顾提高存储空间的利用率，通常把α控制在0.6～0.9的范围之内，C#的HashTable类把α的最大值定为0.72。