温州市住房和城乡建设厅网站,长沙制作网页联系方式,wordpress屏蔽谷歌,seowhy什么意思转载#xff1a;http://blog.csdn.net/liufei_learning/article/details/19220391 理解Hash 哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。 映射是一种对应关系#xff0c;而且集合A的某个元素只能对应集合B中的一个元素。但反过来#xff0c;集合B中的一… 转载http://blog.csdn.net/liufei_learning/article/details/19220391 理解Hash 哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。 映射是一种对应关系而且集合A的某个元素只能对应集合B中的一个元素。但反过来集合B中的一个元素可能对应多个集合A中的元素。如果B中的元素只能对应A中的一个元素这样的映射被称为一一映射。这样的对应关系在现实生活中很常见比如 A - B 人 - 身份证号 日期 - 星座 上面两个映射中人 - 身份证号是一一映射的关系。在哈希表中上述对应过程称为hashing。A中元素a对应B中元素ba被称为键值(key)b被称为a的hash值(hash value)。 映射在数学上相当于一个函数f(x):A-B。比如 f(x) 3x 2。哈希表的核心是一个哈希函数(hash function)这个函数规定了集合A中的元素如何对应到集合B中的元素。比如 A: 三位整数 hash(x) x % 10 B: 一位整数 104 4 876 6 192 2 上述对应中哈希函数表示为hash(x) x % 10。也就是说给一个三位数我们取它的最后一位作为该三位数的hash值。 哈希表在计算机科学中应用广泛。比如在Git中文件内容为键值并用SHA算法作为hash function将文件内容对应为固定长度的字符串(hash值)。如果文件内容发生变化那么所对应的字符串就会发生变化。git通过比较较短的hash值就可以知道文件内容是否发生变动。 再比如计算机的登陆密码一般是一串字符。然而为了安全起见计算机不会直接保存该字符串而是保存该字符串的hash值(使用MD5、SHA或者其他算法作为hash函数)。当用户下次登陆的时候输入密码字符串。如果该密码字符串的hash值与保存的hash值一致那么就认为用户输入了正确的密码。这样就算黑客闯入了数据库中的密码记录他能看到的也只是密码的hash值。上面所使用的hash函数有很好的单向性很难从hash值去推测键值。因此黑客无法获知用户的密码。(之前有报道多家网站用户密码泄露的时间就是因为这些网站存储明文密码而不是hash值.) 注意hash只要求从A到B的对应为一个映射它并没有限定该对应关系为一一映射。因此会有这样的可能两个不同的键值对应同一个hash值。这种情况叫做hash碰撞(hash collision)或者hash 冲突。比如网络协议中的checksum就可能出现这种状况即所要校验的内容与原文并不同但与原文生成的checksum(hash值)相同。再比如MD5算法常用来计算密码的hash值。已经有实验表明MD5算法有可能发生碰撞也就是不同的明文密码生成相同的hash值这将给系统带来很大的安全漏洞。(参考hash collision Hash函数 Hash函数设计的好坏直接影响到对Hash表的操作效率。下面举例说明 假如对上述的联系人信息进行存储时采用的Hash函数为姓名的每个字的拼音开头大写字母的ASCII码之和。 address(张三)ASCII(Z)ASCII(S)9083173; address(李四)ASCII(L)ASCII(S)7683159; address(王五)ASCII(W)ASCII(W)8787174; address(张帅)ASCII(Z)ASCII(S)9083173; 假如只有这4个联系人信息需要进行存储这个Hash函数设计的很糟糕。首先它浪费了大量的存储空间假如采用char型数组存储联系人信息的话则至少需要开辟174*12字节的空间空间利用率只有4/174不到5%另外根据Hash函数计算结果之后address(张三)和address(李四)具有相同的地址这种现象称作冲突对于174个存储空间中只需要存储4条记录就发生了冲突这样的Hash函数设计是很不合理的。所以在构造Hash函数时应尽量考虑关键字的分布特点来设计函数使得Hash地址随机均匀地分布在整个地址空间当中。通常有以下几种构造Hash函数的方法 1.直接定址法 取关键字或者关键字的某个线性函数为Hash地址即address(key)a*keyb;如知道学生的学号从2000开始最大为4000则可以将address(key)key-2000作为Hash地址。 2.平方取中法 对关键字进行平方运算然后取结果的中间几位作为Hash地址。假如有以下关键字序列{421423436}平方之后的结果为{177241178929190096}那么可以取{728900}作为Hash地址。 3.折叠法 将关键字拆分成几部分然后将这几部分组合在一起以特定的方式进行转化形成Hash地址。假如知道图书的ISBN号为8903-241-23可以将address(key)890324123作为Hash地址。 4.除留取余法 如果知道Hash表的最大长度为m可以取不大于m的最大质数p然后对关键字进行取余运算address(key)key%p。在这里p的选取非常关键p选择的好的话能够最大程度地减少冲突p一般取不大于m的最大质数。 5.数字分析法 假设关键字是以r为基的数并且哈希表中可能出现的关键字都是事先知道的则可取关键字的若干数位组成哈希地址。 例如有某些人的生日数据如下 年. 月. 日 75.10.03 85.11.23 86.03.02 86.07.12 85.04.21 96.02.15 经分析,第一位第二位第三位重复的可能性大取这三位造成冲突的机会增加所以尽量不取前三位取后三位比较好 6.随机数法 选择一个随机函数取关键字的随机函数值为它的哈希地址即 H(key)random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。 Hash冲突 哈希表处理冲突主要有开放寻址法、再散列法、链地址法拉链法和建立一个公共溢出区四种方法。 通过构造性能良好的哈希函数可以减少冲突但一般不可能完全避免冲突因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突两种情况下解决冲突的方法应该一致。下面以创建哈希表为例说明解决冲突的方法。常用的解决冲突方法有以下四种 1.开放定址法 这种方法也称再散列法其基本思想是当关键字key的哈希地址pHkey出现冲突时以p为基础产生另一个哈希地址p1如果p1仍然冲突再以p为基础产生另一个哈希地址p2…直到找出一个不冲突的哈希地址pi 将相应元素存入其中。这种方法有一个通用的再散列函数形式Hi(H(key)di)%m i12…n,其中Hkey为哈希函数m 为表长di称为增量序列。增量序列的取值方式不同相应的再散列方式也不同。主要有以下三种 (1) 线性探测再散列 di123…m-1 这种方法的特点是冲突发生时顺序查看表中下一单元直到找出一个空单元或查遍全表。 (2) 二次探测再散列 di12-1222-22…k2-k2 ( km/2) 这种方法的特点是冲突发生时在表的左右进行跳跃式探测比较灵活。 (3) 伪随机探测再散列 di伪随机数序列。 具体实现时应建立一个伪随机数发生器如i(ip) % m并给定一个随机数做起点。 例如已知哈希表长度m11哈希函数为Hkey key % 11则H473H264H605假设下一个关键字为69则H693与47冲突。 如果用线性探测再散列处理冲突下一个哈希地址为H13 1% 11 4仍然冲突再找下一个哈希地址为H23 2% 11 5还是冲突继续找下一个哈希地址为H33 3% 11 6此时不再冲突将69填入5号单元。 如果用二次探测再散列处理冲突下一个哈希地址为H13 12% 11 4仍然冲突再找下一个哈希地址为H23 - 12% 11 2此时不再冲突将69填入2号单元。 如果用伪随机探测再散列处理冲突且伪随机数序列为259……..则下一个哈希地址为H13 2% 11 5仍然冲突再找下一个哈希地址为H23 5% 11 8此时不再冲突将69填入8号单元。 从上述例子可以看出线性探测再散列容易产生“二次聚集”即在处理同义词的冲突时又导致非同义词的冲突。例如当表中i, i1 ,i2三个单元已满时下一个哈希地址为i, 或i1 ,或i2或i3的元素都将填入i3这同一个单元而这四个元素并非同义词。线性探测再散列的优点是只要哈希表不满就一定能找到一个不冲突的哈希地址而二次探测再散列和伪随机探测再散列则不一定。 2.再哈希法 这种方法是同时构造多个不同的哈希函数 HiRH1keyi12,3…,n. 当哈希地址HiRH1key发生冲突时再计算HiRH2key……直到冲突不再产生。这种方法不易产生聚集但增加了计算时间。 3.链地址法 这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表并将单链表的头指针存在哈希表的第i个单元中因而查找、插入和删除主要在同义词链中进行。若选定的散列表长度为m则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。链地址法适用于经常进行插入和删除的情况。 拉链法的优点 与开放定址法相比拉链法有如下几个优点 (1)拉链法处理冲突简单且无堆积现象即非同义词决不会发生冲突因此平均查找长度较短(2)由于拉链法中各链表上的结点空间是动态申请的故它更适合于造表前无法确定表长的情况(3)开放定址法为减少冲突要求装填因子α(装填因子表中的记录数/哈希表的长度)较小故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1且结点较大时拉链法中增加的指针域可忽略不计因此节省空间(4)在用拉链法构造的散列表中删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表删除结点不能简单地将被删结点的空间置为空否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放地址法中空地址单元(即开放地址)都是查找失败的条件。 因此在用开放地址法处理冲突的散列表上执行删除操作只能在被删结点上做删除标记而不能真正删除结点。 拉链法的缺点 拉链法的缺点是指针需要额外的空间故当结点规模较小时开放定址法较为节省空间而若将节省的指针空间用来扩大散列表的规模可使装填因子变小这又减少了开放定址法中的冲突从而提高平均查找速度。 4.建立公共溢出区 这种方法的基本思想是将哈希表分为基本表和溢出表两部分凡是和基本表发生冲突的元素一律填入溢出表.(注意在这个方法里面是把元素分开两个表来存储) 冲突太多了怎么办? 当冲突太多的时候,我们一般采用的方法时拉链法,采用拉链法的原因是动态申请空间,至于优点在上面已经阐述了.冲突太多的时候会产生堆积状态,我们将H(key)相同的关键字都统一放到一个链里,当出现冲突的时候我们就把该元素接在链表后面,这样可以避免产生堆积现象,缩短平均查找长度. 当数据表太小,而数据太多的时候怎么办? 当数据表太小数据太多可以通过建立一个溢出表,专门用来存放哈希表中放不下的记录. Hash表的平均查找长度 Hash表的平均查找长度包括查找成功时的平均查找长度和查找失败时的平均查找长度。 查找成功时的平均查找长度表中每个元素查找成功时的比较次数之和/表中元素个数 查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数可以理解为向表中插入某个元素该元素在每个位置都有可能然后计算出在每个位置能够插入时需要比较的次数再除以表长即为查找不成功时的平均查找长度。 下面举个例子 有一组关键字{231214235}表长为14Hash函数为key%11则关键字在表中的存储如下 地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 关键字 23 12 14 2 3 5 比较次数 1 2 1 3 3 2 因此查找成功时的平均查找长度为(121332)/611/6 查找失败时的平均查找长度为(17654321111111)/1438/14 这里有一个概念装填因子表中的记录数/哈希表的长度如果装填因子越小表明表中还有很多的空单元则发生冲突的可能性越小而装填因子越大则发生冲突的可能性就越大在查找时所耗费的时间就越多。因此Hash表的平均查找长度和装填因子有关。有相关文献证明当装填因子在0.5左右的时候Hash的性能能够达到最优。因此一般情况下装填因子取经验值0.5。(也就是说所需的实际空间为元素数目的2倍) Hash表大小的确定也非常关键如果Hash表的空间远远大于最后实际存储的记录个数则造成了很大的空间浪费如果选取小了的话则容易造成冲突。在实际情况中一般需要根据最终记录存储个数和关键字的分布特点来确定Hash表的大小。还有一种情况时可能事先不知道最终需要存储的记录个数则需要动态维护Hash表的容量此时可能需要重新计算Hash地址。 参考 http://www.cnblogs.com/vamei/archive/2013/03/24/2970339.html http://www.cnblogs.com/dolphin0520/archive/2012/09/28/2700000.html http://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8 http://en.wikipedia.org/wiki/Hash_table http://blog.csdn.net/jirongzi_cs2011/article/details/9377779 http://blog.csdn.net/liangbopirates/article/details/9753599
