大家好，今天来为大家解答哈希 *** 这个问题的一些问题点，包括哈希官网也一样很多人还不知道，因此呢，今天就来为大家分析分析，现在让我们一起来看看吧！如果解决了您的问题，还望您关注下本站哦，谢谢~
本文目录
一、哈希表的常用 ***
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地 *** 。
实际工作中需视不同的情况采用不同的哈希函数，通常考虑的因素有：
1.直接寻址法：取关键字或关键字的某个线 *** 函数值为散列 *** 。即H(key)=key或H(key)= a·key+ b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。
2.数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列 *** ，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列 *** 。
3.平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希 *** 。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希 *** 。
例：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11，E的内部编码为05，Y的内部编码为25，A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为1105 *** 1，同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后，取出第7到第9位作为该关键字哈希 *** ，如下图所示关键字内部编码内部编码的平方值 H(k)关键字的哈希 *** KEYA 11050201 122157778355001 778 KYAB 11 *** 102 1265 *** 795010404 795 AKEY 01110525 001233265775625 265 BKEY 02110525 004454315775625 315
4.折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列 *** 。数位叠加可以有移位叠加和间界叠加两种 *** 。移位叠加是将分割后的每一部分的更低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。
5.随机数法：选择一随机函数，取关键字的随机值作为散列 *** ，通常用于关键字长度不同的场合。
6.除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列 *** 。即 H(key)= key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
二、哈希函数怎么求 ***
1、进行哈希计算得到哈希 *** ，再将其存储到指定 *** 。如果该 *** 已有元素，称之为存在“冲突”，再采用冲突检测法处理冲突，如线 *** 探测再散列法。
2、如元素的值为95时，采用哈希函数h(k)=k mod 11时，得到的哈希 *** 为7，即h(95)= 95% 11= 7。
3、（1）构造哈希表，有11个 *** 空间（0~10）；
4、（2）计算各个元素的哈希 *** ，若没有冲突，则直接存储到相应 *** 的哈希表中：
5、 h(82)= 82% 11= 5有冲突（因为 *** 5已经被值为27的元素占用了）
6、（3）对于有冲突的元素，发生冲突后必须马上处理(采用线 *** 探查法)，不能到最后一起处理：
7、（4）最后哈希表0~10的11个 *** 空间依次存储的元素为：
8、另外,虚机团上产品团购,超级便宜
三、哈希表详解
散列法存储的基本思想：建立记录关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储 *** 。
这样，不经过比较，一次存取就能得到所查元素的查找 ***
优点：查找速度极快（O(1)）,查找效率与元素个数n无关！
选取某个函数，依该函数按关键字计算元素的存储位置并按此存放；查找时也由同一个函数对给定值k计算 *** ，将k与 *** 中内容进行比较，确定查找是否成功。
哈希 *** 中使用的转换函数称为哈希函数(杂凑函数).在记录的关键码与记录的存储 *** 之间建立的一种对应关系
有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储 *** H（k）＝k， H(k)称为散列函数,画出存储结构图。
根据散列函数H（k）＝k，可知元素14应当存入 *** 为14的单元，元素23应当存入 *** 为23的单元，……，
根据存储时用到的散列函数H(k)表达式，迅即可查到结果！
例如，查找key=9,则访问H(9)=9号 *** ，若内容为9则成功；
若查不到，应当设法返回一个特殊值，例如空指针或空记录。
很显然这种搜索方式空间效率过低。
哈希函数可写成：addr(ai)=H(ki)
选取某个函数，依该函数按关键字计算元素的存储位置并按此存放；查找时也由同一个函数对给定值k计算 *** ，将k与 *** 中内容进行比较，确定查找是否成功。哈希 *** 中使用的转换函数称为哈希函数(杂凑函数).在记录的关键码与记录的存储 *** 之间建立的一种对应关系。
通常关键码的 *** 比哈希 *** *** 大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希 *** 上，这种现象称为冲突。
有6个元素的关键码分别为：（14，23，39，9，25，11）。
选取关键码与元素位置间的函数为H(k)=k mod 7
根据哈希函数算出来发现同一个 *** 放了多个关键码，也就是冲突了。
在哈希查找 *** 中，冲突是不可能避免的，只能尽可能减少。
所以，哈希 *** 必须解决以下两个问题：
（a）所选函数尽可能简单，以便提高转换速度；
（b）所选函数对关键码计算出的 *** ，应在哈希 *** 内集中并大致均匀分布，以减少空间浪费。
2）制定一个好的解决冲突的方案
查找时，如果从哈希函数计算出的 *** 中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。
从上面两个例子可以得出如下结论：
哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键码的哈希函数值都落在表长允许的范围之内即可
冲突：key1≠key2，但H(key1)=H(key2)
同义词：具有相同函数值的两个关键码
哈希函数冲突不可避免，只能尽量减少。所以，哈希 *** 解决两个问题：
要求一：n个数据原仅占用n个 *** ，虽然散列查找是以空间换时间，但仍希望散列的 *** 空间尽量小。
要求二：无论用什么 *** 存储，目的都是尽量均匀地存放元素，以避免冲突。
Hash(key)= a·key+ b(a、b为常数)
优点：以关键码key的某个线 *** 函数值为哈希 *** ，不会产生冲突.
缺点：要占用连续 *** 空间，空间效率低。
例.关键码 *** 为{100，300，500，700，800，900}，
选取哈希函数为Hash(key)=key/100，
Hash(key)=key mod p(p是一个整数)
特点：以关键码除以p的余数作为哈希 *** 。
关键：如何选取合适的p？p选的不好，容易产生同义词
技巧：若设计的哈希表长为m，则一般取p≤m且为质数
（也可以是合数，但不能包含小于20的质因子）。
Hash(key)=⎣ B( A key mod 1)⎦
(A、B均为常数，且0<A<1，B为整数)
特点：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希 *** 。
例：欲以学号最后两位作为 *** ，则哈希函数应为：
其实也可以用法2实现： H(k)=k% 100
特点：选用关键字的某几位组合成哈希 *** 。选用原则应当是：各种符号在该位上出现的频率大致相同。
例：有一组（例如80个）关键码，其样式如下：
①第1、2位均是“3和4”，第3位也只有“ 7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希 *** 选用。
②若哈希 *** 取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希 *** ，也可以取其中两位与其它两位叠加求和后，取低两位作哈希 *** 。
特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希 *** 。(适于不知道全部关键码情况)
理由：因为中间几位与数据的每一位都相关。
例：25 *** 的平方值为6702 *** 1，可以取中间的029为 *** 。
特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希 *** 。
适用于：关键码位数很多,且每一位上各符号出现概率大致相同的情况。
法1：移位法──将各部分的最后一位对齐相加。
法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。
用法2： 427 518 96—> 724+518+69=1311
Hash(key)= random( key)(random为伪随机函数)
适用于：关键字长度不等的情况。造表和查找都很方便。
①执行速度（即计算哈希函数所需时间）；
设计思路：有冲突时就去寻找下一个空的哈希 *** ，只要哈希表足够大，空的哈希 *** 总能找到，并将数据元素存入。
Hi=(Hash(key)+di) mod m( 1≤i< m)
di为增量序列 1，2，…m-1，且di=i
关键码集为{47，7，29，11，16， *** ，22，8，3}，
哈希函数为Hash(key)=key mod 11；
拟用线 *** 探测法处理冲突。建哈希表如下：
① 47、7是由哈希函数得到的没有冲突的哈希 *** ；
② Hash(29)=7，哈希 *** 有冲突，需寻找下一个空的哈希 *** ：由H1=(Hash(29)+1) mod 11=8，哈希 *** 8为空，因此将29存入。
③另外，22、8、3同样在哈希 *** 上有冲突，也是由H1找到空的哈希 *** 的。
线 *** 探测法的优点：只要哈希表未被填满，保证能找到一个空 *** 单元存放有冲突的元素；
线 *** 探测法的缺点：可能使第i个哈希 *** 的同义词存入第i+1个哈希 *** ，这样本应存入第i+1个哈希 *** 的元素变成了第i+2个哈希 *** 的同义词，……，
因此，可能出现很多元素在相邻的哈希 *** 上“堆积”起来，大大降低了查找效率。
解决方案：可采用二次探测法或伪随机探测法，以改善“堆积”问题。
仍举上例，改用二次探测法处理冲突，建表如下：
m为哈希表长度，m要求是某个4k+3的质数；
di为增量序列 1^2，-1 ^2，2 ^2，-2 ^2，…，q ^2
注：只有3这个关键码的冲突处理与上例不同，
Hash(3)=3，哈希 *** 上冲突，由
H1=(Hash(3)+1 ^2) mod 11=4，仍然冲突；
H2=(Hash(3)-1 ^2) mod 11=2，找到空的哈希 *** ，存入。
3）若di＝伪随机序列，就称为伪随机探测法
基本思想：将具有相同哈希 *** 的记录(所有关键码为同义词)链成一个单链表，m个哈希 *** 就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。
设{ 47, 7, 29, 11, 16, *** , 22, 8, 3, 50, 37, *** }的哈希函数为：
用拉链法处理冲突，则建表如图所示。
RHi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。
思路：除设立哈希基本表外，另设立一个溢出向量表。
所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的 *** 是什么，一旦发生冲突，都填入溢出表。
明确：散列函数没有“万能”通式（杂凑法），要根据元素 *** 的特 *** 而分别构造。
讨论：哈希查找的速度是否为真正的O（1）？
不是。由于冲突的产生，使得哈希表的查找过程仍然要进行比较，仍然要以平均查找长度ASL来衡量。
一般地，ASL依赖于哈希表的装填因子α,它标志着哈希表的装满程度。
α越大，表中记录数越多，说明表装得越满，发生冲突的可能 *** 就越大，查找时比较次数就越多。
例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为：H(key)=key MOD 13,哈希表长为m=16，
(1)用线 *** 探测再散列处理冲突，即Hi=(H(key)+di) MOD m
(2)用二次探测再散列处理冲突，即Hi=(H(key)+di) MOD m
1）散列存储的查找效率到底是多少？
答：ASL与装填因子α有关！既不是严格的O(1)，也不是O(n)
答：不一定！正因为有冲突，使得文件加密后无法破译！（单向散列函数不可逆，常用于数字签名和间接加密）。
利用了哈希表 *** 质：源文件稍稍改动，会导致哈希表变动很大。
好了，文章到此结束，希望可以帮助到大家。
