哈希竞猜游戏系统开发　　

基本概念

　　哈希表（Hash Table）是一种根据关键字直接访问内存存储位置的数据结构。（I3I-掂Z6o5-微8883電）通过哈希表，数 据元素的存放位置和数据元素的关键字之间建立起某种对应关系，建立这种对应关系的函数称为哈希函数（如图）。

　　哈希函数构造方法

　　哈希表的构造方法是：假设要存储的数据元素个数为n，设置一个长度为m（m≥n）的连续存储单元，分别以每个数据元素的

关键字为自变量，通过哈希函数，把映射为内存单元的某个地址，并将该数据元素存储在该内存单元中。

　　从数学的角度来看，哈希函数实际上是关键字到内存单元的映射，因此我们希望通过哈希函数通过尽量简单的运算使得通过

哈希函数计算出的哈希地址尽量均匀地被映射到一系列的内存单元中。构造哈希函数有三个要点：第一，运算过程要尽量简单高

效，以提高哈希表的插入和检索效率；第二，哈希函数应该具有较好的散列性，以降低哈希冲突的概率；第三，哈希函数应具有

较大的压缩性，以节省内存。一般有以下几种常见的方法：

　　直接定址法，该方法是曲关键字的某个线性函数值为哈希地址。可以简单的表示为：，优点是不会产生冲突，但缺点空间复

杂度可能会很高，适用于元素较少的情况下；

　　除留余数法，它是用数据元素关键字除以某个常数所得的余数作为哈希地址，该方法计算简单，适用范围广，是最经常使用

的一种哈希函数，可以表示为：，该方法的关键是常数的选取，一般要求是接近或等于哈希表本身的长度，理论研究表明，该常

数取素数时效果最好。

　　数字分析法：该方法是取数据元素关键字中某些取值较均匀的数字位来作为哈希地址的方法，这样可以尽量避免冲突，但是

该方法只适合于所有关键字已知的情况。对于想要设计出更加通用的哈希表并不适用。

　　哈希冲突解决办法

　　在构造哈希表时，存在这样的问题，对于两个不同的关键字，通过我们的哈希函数计算哈希地址时却得到了相同的哈希地址

，我们将这种现象称为哈希冲突（如图）:

　　哈希冲突主要与两个因素相关：第一，填装因子，所谓的填装因子是指哈希表中已存入的数据元素个数与哈希地址空间大小

的比值，即α=n/m，α越小，冲突的可能性就越小，相反则冲突可能性越大；但是α越小，哈希表的存储空间利用率也就很低，

α越大，存储空间的利用率也就越高，为了兼顾哈希冲突和存储空间利用率，通常将α控制在0.6-0.9之间，而.NET中的

Hashtable则直接将α的最大值定义为0.72（注：虽然微软官方MSDN中声明Hashtable默认填装因子为1.0，事实上所有的填装因子

都为0.72的倍数）；第二，与所用的哈希函数有关，如果哈希函数选择得当，就可以使哈希地址尽可能的均匀分布在哈希地址空

间上，从而减少冲突的产生，但一个良好的哈希函数的得来很大程度上取决于大量的实践，不过幸好前人已经总结实践了很多高

效的哈希函数，可以参考园子里大牛Lucifer的文章：数据结构:Hash Table<I>。

　　哈希冲突通常是很难避免的，解决哈希冲突有很多种方法，通常分为两大类：

　　开放定址法，它是一类以发生哈希冲突的哈希地址为自变量，通过某种哈希函数得到一个新的空闲内存单元地址的方法（如

图），开放定址法的哈希冲突函数通常是一组；

　　链表法，当未发生冲突时，则直接存放该数据元素；当冲突产生时，把产生冲突的数据元素另外存放在单链表中。

　　Hashtable和Dictionary

　　.NET中实现了哈希表的类分别是Hashtable和Dictionary<TKey,TValue>，Hashtable由包含集合元素的存储桶组成，存

储桶是Hashtable中各元素的虚拟子组，与大多数集合中进行的搜索相比，存储桶可使搜索更为便捷。Dictionary则是泛型版本的

哈希表，与Hashtable的功能相同，对于值类型，特定类型（不包括Object）的性能优先于Hashtable，这是因为Hashtable的元素

属于Object类型，所以在存储或者检索类型时通常发生装箱和拆箱操作；除此之外，虽然微软宣称Hashtable是线程安全的，可以

允许多个读线程或一个写线程访问，但是事实是它也并非线程安全，在.NET Framework 2.0新引入的Dictionary仍旧为解决这个

问题，其中限于公共静态方法是线程安全的，因此可以说Dictionary是非线程安全的，而且对整个集合的枚举过程对二者而言都

不是线程安全的，因为当出现枚举与写访问互相争用这种情况发生时，则必须在整个枚举过程中对整个集合加锁。如果我们在使

用.NET Framework 4.0以上版本，我们可以使用线程安全的ConcurrentDictionary；另一个比较重要的区别在于，虽然它们都实

现了哈希表，但是二者却使用了完全不同的哈希冲突解决方法，Hashtable解决冲突的方式是开放定址法，而Dictionary则采用了

链表法。

　　Hashtable的实现原理

　　Hashtable类中哈希函数的定义可以用如下递推公式来表示：