多语言展示
当前在线:1158今日阅读:112今日分享:19

C#与数据结构--哈希表(2)

其中,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  8.4 剖析System.Collections.Hashtable  万物之母object类中定义了一个GetHashCode()方法,这个方法默认的实现是返回一个唯一的整数值以保证在object的生命期中不被修改。既然每种类型都是直接或间接从object派生的,因此所有对象都可以访问该方法。自然,字符串或其他类型都能以唯一的数字值来表示。也就是说,GetHashCode()方法使得所有对象的哈希函数构造方法都趋于统一。当然,由于GetHashCode()方法是一个虚方法,你也可以通过重写这个方法来构造自己的哈希函数。  8.4.1  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
推荐信息