注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

回首望星辰

See you in the next world

 
 
 

日志

 
 

散列表hashtable  

2009-11-12 08:57:16|  分类: 软件开发 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

散列表更像是一个大池子(但是不是所有的大池子都可以认为是散列表). 这个特殊的大池子有这样的特点, 它的容量总是要比你想要存储的元素数量大, 它能利用大出一部分容量的特点, 让你能更加快速的查找定位某一元素.

牺牲一点点内存,换取更高效的表现, 有人问值不值得?  大哥,现在1G的内存都100多块钱了...

第一部分: 散列表的基本知识

散列表是这样一种数据结构: 它利用散列函数(通常称为函数h(k))计算元素关键字(标记k)的散列值, 并根据该散列值, 直接确定(或者通过简单数学计算)该元素在散列表中的存储位置(散列表中的存储位置我们称为槽Slot). 如果两个元素关键字通过散列函数的计算获得了同样的散列值, 从而指向散列表中的同一个槽, 我们称这种现象为"碰撞(Collision)".由于元素关键字域U的容量大于散列表T的容量m, 所以完全避免碰撞是不可能的. 这就引申出了散列表最为重要的两个问题:

  • 如何最大可能的减少碰撞? - 选择好的散列函数
  • 发生碰撞以后应该怎么办? - 碰撞解决技术

 

  • 1. 选择好的散列函数

散列函数优劣的评价标准是, 它能否将每个关键字独立地等可能地散列到散列表T的任何一个槽当中. 独立意味着每个元素的散列结果都不受其他元素的影响,等可能是说散列后,每个槽存储的元素数量尽可能均匀.

我们将现在常见的散列算法归类,可以归结为大概3类: 除法散列法, 乘法散列法, 全域散列.

实际上,我们在进行散列之前,要做点准备工作 - 将关键字解释为自然数. 比如字符串我们常按照它的ASCII码值解释等.这个算法你可以自己任意去玩, 不过我们知道C#默认的解释方法是Object.GetHashCode().你可以接受这个方法的默认实现,当然你如果觉得它不爽也可以重写它.前提是你的Object要实现IEqualityComparer接口.

好吧,现在开始, 由关键字获得的自然数我们用k来表示, 哈希表的容量我们用m来表示

除法散列法的散列函数是: h(k) = k mod m,算法相当简单因而也是最常用的算法. 唯一的问题在于m的选择(注意, 这里是根据想要存储的元素数量来决定散列表的容量m). 好吧, 选择m也有两个诀窍, 第一,不要选择2的幂(因为mod 2的幂相当于只根据元素的高位散列, 更加容易碰撞); 第二, 尽量选择比2的幂差得比较远的质数.例如C#的Hashtable的实现就是选择比元素数量大一点点的质数.

乘法散列法的散列函数是: h(k) = ∟m(kA mod 1) ∟,(请原谅我不知道怎么用Live Writer 打出求底符号)  A是介于0和1之间的小数. kA mod 1 即 kA的小数部分,  一般选择m为2的幂.  A值的选择, Kurth认为它最好的值是(散列表hashtable - 辉 - 回首望星辰 - 1)/2, 即大约0.618.

全域散列法用得很少,此处略过.

  • 2.碰撞解决技术

在发生碰撞以后, 后来元素该怎么处理? 思路大概上就有了2种: 重新散列和链表保存.

 

先说链表保存. 散列表保存不再是元素本身, 而是元素的关键字值, 并且该关键字值结构作为一个链表头,指向一个链表,这个链表保存的元素其关键字值等于链表头里面的关键字值.

这种方法的插入过程是: 计算散列值 -> 找到链表头 -> 找到链表尾部 ->将元素连缀在尾部

这种方法的搜索过程是: 计算散列值 -> 找到链表头 -> 遍历链表

由此看出这种算法的时间复杂度主要由链表操作决定, 所以链表的长度, 或者精确地说, 链表的平均长度, 决定了这个算法的效率. 如果散列函数足够坏, 将所有的元素都散列到了一个链表中,那这种情况下就是最坏的时间复杂度, 为O(n), 而不是一般散列表所预期的O(1).

好吧,如果你愿意承受着个算法,那他给你带来的好处事你可以在散列表里面存储远远多于散列表槽数的元素, 即使那样的散列表已经没有了什么意义.

 

另外一种我们常见的碰撞解决技术就是开放开放寻址法了. 基本上, 它采用的事重新散列的思想.

当发生碰撞时, 新进入的元素标记碰撞次数并且按照散列函数(这个散列函数包含了对碰撞次数的计算)重新计算,获取新的散列值, 然后如果遇到新的碰撞, 重复执行这一过程,直到没有碰撞情况发生.

重新散列的方式, 根据散列函数的不同, 又大体分为3类: 线性散列, 二次散列, 双重散列.

线性散列主要强调的是线性步进, 这个步进可以由你控制, 比如1, 比如2, 比如4等.

二次散列主要强调的是探查按照某常数的二次方步进, 比如第一次是2, 第二次是4, 第三次是8....., 这种方法的效果要比线性探查好得多.

双重散列事开放寻址法的最好方法. 它的散列函数大体如下:

h(k,i) = ( h1(k) + i*h2(k) ) mod m, 其中 i是发生碰撞的次数, k是关键字值, m是散列表的容量, h1, h2是两个散列函数称为辅助散列函数,

 

为了能查找整个散列表, 值h2(k)要与表大小m互质!!! 一般设计为h2(k)是一个总是产生质数的函数, 或者m是一个质数并且h2总是产生比m小的正整数.比如, 我们可以去m为质数, h1(k) = k mod m, h2(k) = 1+ ( k mod (m-1) ) -------m-1比m略小.

双重散列的探查序列是m的平方级别的, 而线性和二次都是m级别的, 因此双重散列的效果要好得多, 实际上, C#的Hashtable应用的就是双重散列,

.NET Framework 中的哈希表, 使用了双重散列的方式来计算散列值. 那么到底精确的来说, 是采用了什么关系式呢? 实际上很简单, 这个关系式就是:

h(key, n) = h1(key) + n*h2(key)

 

其中

h1(key) = GetHash(key);

h2(key) = 1 + ((h1(key) >> 5) + 1) % (hashsize - 1);

 

key - 待散列的关键字值,

n - 发生碰撞的次数,

hashsize - 哈希表的容量,是一个素数.大牛Knuth同学在他那本<Art of Computer Programming>说过为什么要使用素数. .NET Framwork 兼顾效率和范围, 给出了这样一个实现:

internal static readonly int[] primes = {

3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,

1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,

17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,

187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,

1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};

 

 

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]

internal static int GetPrime(int min)

{

if (min < 0)

throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));

for (int i = 0; i < primes.Length; i++)

{

int prime = primes[i];

if (prime >= min) return prime;

}

 

//outside of our predefined table.

//compute the hard way.

for (int i = (min | 1); i < Int32.MaxValue;i+=2)

{

if (IsPrime(i))

return i;

}

return min;

}

 

这段代码就是说,你要的容量如果在7199369之内,就从这个表里面给你返回一个最接近的素数; 否则, 给你找一个比想要容量大一点点的素数返回.

GetHash( Object )  - 是返回参数对象哈希值的函数, 它默认等于每个对象的GetHashCode()函数, 除非你制定了特定的IComparer对象,那么它会返回该Comparer的哈希值.哦? 原来GetHashCode()是用在这里啊... 我们知道每一个起源于Object的类,都会给IEqualityComparer接口一个默认的实现,这个接口的两个方法就是Equals()和GetHashCode().你当然可以重写GetHashCode()函数的实现, 但是这个函数直接关系到了这个类的对象放入HashTable以后, HashTable的效率表现. 默认的类方法GetHashCode()不至于太差, 如果你要实现自己的GetHashCode方法, 那么一定要考虑一下会不会和别的类生成的HashCode容不容易落入同一个值区间内. <Effective C#>这本书的第十个条目就解释了这样一个规律:

对于引用类型自带的GetHashCode函数来说,基本上是正确的,但是效率不高;而对于值类型自带的GetHashCode函数而言,基本上是不正确的,即使正确也是效率不高。如果重写类型的GetHashCode函数,想要达到既正确又高效是不可能的。

当然, 还有一条建议:

不建议重写此函数,而且在使用这个函数也需要先注意它的实现

 

每个哈希表都有装载率,装载率越高,空间越节省, 装载率越低, 查找越快.  .NET Framework的HashTable默认装载率是0.72, 但是表面上看来是1.0 . .NET的开发人员似乎为了引导我们使用他认为效率最为平衡的装载率, 偷偷的做了一下弊, 呵呵

public Hashtable(int capacity, float loadFactor) {

if (capacity < 0)

throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));

if (!(loadFactor >= 0.1f && loadFactor <= 1.0f))

throw new ArgumentOutOfRangeException("loadFactor", Environment.GetResourceString("ArgumentOutOfRange_HashtableLoadFactor", .1, 1.0));

 

// Based on perf work, .72 is the optimal load factor for this table.

this.loadFactor = 0.72f * loadFactor;

double rawsize = capacity / this.loadFactor;

if (rawsize > Int32.MaxValue)

throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));

 

// Avoid awfully small sizes

int hashsize = (rawsize > 11) ? HashHelpers.GetPrime((int)rawsize) : 11;

buckets = new bucket[hashsize];

 

loadsize = (int)(this.loadFactor * hashsize);

isWriterInProgress = false;

// Based on the current algorithm, loadsize must be less than hashsize.

BCLDebug.Assert( loadsize < hashsize, "Invalid hashtable loadsize!");

}

 

接下来的问题是, 我能计算出h(key, n)的值了, 然后这个元素会被放到哪里?  哈希表内部维护了一个key-value-hash code结构数组buckets, 每一个元素根据计算出的h(key, 1)值seed通过关系式(int) (seed % (uint)buckets.Length) 得到对应的数组索引, 如果发生碰撞则计算h(key, 2), 不碰撞就存入,依次类推.

 

针对容量不足和多次添加删除之后表内结构混乱, HashTable还提供了 expand() 和 rehash() 方法

  评论这张
 
阅读(1317)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017