All articles| All Pictures| All Softwares| All Video| Go home page| Write articles| Upload pictures

Reading number is top 10 articles
ASP.NET实例:增强,GridView,控件的功能(二)_[Asp.Net教程]
10条PHP中用的mysql语句_[PHP教程]
深入Atlas系列之服务器端支持(上)_[Asp.Net教程]
详解:——如何将图片储存在数据库里_php资料_编程技术
asp.net身份验证(登录控件),基于标准的sqlserver_[Asp.Net教程]
visual c++类中的友元函数
安装SQL,Server,2005的AdventureWorks_[SQL,Server教程]
如何制作圆角表格_[Html教程]
PHP经典的给图片加水印程序_[PHP教程]
制作WEB在线编辑器-插入HTML标签_.net资料_编程技术
Reading number is top 10 pictures
NeedWallpaper6
含苞欲放的素颜美少女2
Azusa Yamamoto2
囚犯暴乱了咋办?
XuYing poker perspective garment debut
Hunan province aizhai super-large suspension bridge open to traffic and 4 world first2
Go to the national museum2
超级大兔子
日本小萝莉1
美丽的风景--让你目瞪口呆
Download software ranking
Visual C++界面编程技术
虚拟机5.5.3版
电车之狼R
仙剑奇侠传98硬盘WINXP版
天龙八部最新服务端
致我们终将逝去的青春
1400篇各类破解文章
打鸟视频
塘西风月痕
Macromedia Dreamweaver 8
归海一刀 published in(发表于) 2014/1/30 0:50:57 Edit(编辑)
.Net类库中实现的HashTable_[Asp.Net教程]

.Net类库中实现的HashTable_[Asp.Net教程]

.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







添加到del.icio.us 添加到新浪ViVi 添加到百度搜藏 添加到POCO网摘 添加到天天网摘365Key 添加到和讯网摘 添加到天极网摘 添加到黑米书签 添加到QQ书签 添加到雅虎收藏 添加到奇客发现 diigo it 添加到饭否 添加到飞豆订阅 添加到抓虾收藏 添加到鲜果订阅 digg it 貼到funP 添加到有道阅读 Live Favorites 添加到Newsvine 打印本页 用Email发送本页 在Facebook上分享


Disclaimer Privacy Policy About us Site Map

If you have any requirements, please contact webmaster。(如果有什么要求,请联系站长)
Copyright ©2011-
uuhomepage.com, Inc. All rights reserved.