.Net类库中实现的HashTable_[Asp.Net教程]
摘要:
这个HashTable用开放定址法解决冲突,用双散列法进行探测。装填因子过高之后使用再散列法扩充,涉及到的算法都不是很复杂,即使不使用数学工具,也可以简单的分析下:-) 。
本文以.net fx's HashTable为例,回顾HashTable的基础理论。
HashTable是一种能提供快速插入和查询的数据结构,无论其包含有多少Item,查询和插入操作的平均时间总是接近O(1)。HashTable理论上并不关心其所包含的item顺序,任何与顺序有关的操作例如:“find_min, find_max”,都不能有效的支持。
Hashing
假如我们把一本英汉字典的5000个单词, 从a到zyzzyva,存储到一个数组中。这样我们可以通过它们在数组中的序号,以固定的时间快速的访问每一个单词。但是给定一个单词比如:“COOL",如何才能知道它的序号呢?
Converting word to number
为了把每个单词同它们在数组中的位置一一对应起来,我们需要把每个单词都转化为一个唯一的一个整数(hash code)。下面是一种简单的算法:
英语只有26个字母,可以用1-26表示,用0表示空格.为了获得一个唯一的数字,我们把单词的每个字母都转化为其对应数字,然后乘以一个合适的权数。比如:
为了把"cats" 转化为数字,我们把它的每一个字符都转化为相应的数字,然后乘以27^n (n表示字符的位置),把它们相加:
3*273 + 1*272 + 20*271 + 19*270=60337
这个方法可以将单词都转化为一个唯一整数(hash code)。
.net framework中所实现的Hashtable ,虽然对键值的类型没有限制,但要求其键值(key)的类型必须实现GetHashCode()方法,用来获得全局唯一的hash code。事实上由于.net类型库定义的所有类型都直接或间接的继承自Object,所有都具有一个默认的GetHashCode()实现。
但是我们得到的整数(Hash Code)明显不是我们所需要的序号(index)。
Hash Function
我们从5000个单词得到范围非常大的一组数字(hash code),每个数字都可能描述数组中的一个序号(index),但是只有很少的数字与序号一一对应。为了可以以一个固定的时间访问每一个单词,我们需要一个方法将这些值域很大的数字映射到数组中的一个位置。
hash function 的作用就是将这些范围很大的数(domain of keys )转换成我们需要的序号(domain of location)。
.net framework采用Division Methed作为其散列算法,使用取模(modulo)操作将Hash code值域转换到合适的范围。即:
arrayIndex = hashcode % arraySize;
其中arrayIndex代表单词在数组中的位置,ArraySize代表数组长度,
Collisions
我们希望每一个Hash Code都唯一对应一个Index,然而这个算法并不能保证这一点。比如你想将"melioration"插入到数组,你将这个单词通过上述过程转换成index,然而你发现那个位置已经被"demystify"所占据,这种情况叫做Collisions(冲突)。
.net framework使用open address 的方式解决冲突,例如当进行插入操作时,根据键值生成的index已经被别的item占据时,它将自动搜索index+incr位置,直到找到一个空的位置。其中的incr由以下算法产生。
incr = (uint)(1 + (((hashcode >> 5) + 1) % ((uint)itemCount - 1)));
.net framework生成incr的这种算法,其结果与当前冲突位置无关,避免了好多问题。事实上它根据键值的hash code 进行了另一次散列,即所谓的Double Hash.
Expand
由于HashTable基于数组的,所以它的容量需要提前指定,并且最好在运行过程中不要改变。数组的大小是不能在运行时改变的,所以当HashTable太满时,就需要声明一个新的大数组。
我们记得Hash Function 根据数组的长度计算键值的序号的,所以不可以将旧数组的数据直接复制到新数组,必须对针对每一个键值重新计算其位置,非常的低效。
.net framework实现中HashTable最小的容量为11,当HashTable过满时,会新建立一个容量为当前俩倍的数组,然后将旧数组的值复制到新数组对应的位置。
来源:http://www.cnblogs.com/osamede