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。
(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,…
其中,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