哈希表及处理冲突的方法

短命女 2022-05-31 00:17 375阅读 0赞

一。哈希函数和哈希冲突的基本概念

1.哈希函数：

哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表成为哈希表。
基本思想： 首先在元素的关键字K和元素的位置P之间建立一个对应关系f，使得P=f(K),其中f成为哈希函数。
创建哈希表时，把关键字K的元素直接存入地址为f(K)的单元；查找关键字K的元素时利用哈希函数计算出该元素的存储位置P=f(K).
创建哈希表时，把关键字K的元素直接存入地址为f(K)的单元；查找关键字K的元素时利用哈希函数计算出该元素的存储位置P=f(K).

2.哈希冲突：

当关键字集合很大时，关键字值不同的元素可能会映像到哈希表的同一地址上，即K1!=K2，但f(K1)=f(K2),这种现象称为hash冲突，实际中冲突是
不可避免的，只能通过改进哈希函数的性能来减少冲突。

二。哈希函数的构造方法

哈希函数的构造原则是：函数本身便于计算、计算出来的地址分布均匀（即对任意K，f(K)对应不同地址的概率相等）。

1.数字分析法：

  1. 可以从关键如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。  
  2. 例如，有80个记录，关键字为8位十进制整数d1d2d3…d7d8，如哈希表长取100，则哈希表的地址空间为：00~99。  
  3. 假设经过分析，各关键字中 d4和d7的取值分布较均匀，则哈希函数为：h(key)=h(d1d2d3…d7d8)=d4d7。例如，h(81346532)=43，h(81301367)=06。  
  4. 相反，假设经过分析，各关键字中 d1和d8的取值分布极不均匀， d1 都等于5，d8 都等于2，此时，如果哈希函数为：h(key)=h(d1d2d3…d7d8)=d1d8，  
  5. 则所有关键字的地址码都是52，显然不可取。

2.平方取中法：

  1. 当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。  
  2. 这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。  
  5. 例：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11，E的内部编码为05，Y的内部编码为25，
  7.         A的内部编码为01, B的内部编码为02。

由此组成关键字“KEYA”的内部代码为11052501，同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。

  1.         之后对关键字进行平方运算后，取出第7到第9位作为该关键字哈希地址，如图8.23所示。

关键字 内部编码 内部编码的平方值 H(k)关键字的哈希地址
KEYA 11050201 122157778355001 778
KYAB 11250102 126564795010404 795
AKEY 01110525 001233265775625 265

BKEY 02110525 004454315775625 315

3.分段叠加法：

  1.     这种方法是按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。  
  2.     具体方法有折叠法与移位法。移位法是将分割后的每部分低位对齐相加，折叠法是从一端向另一端沿分割界来回折叠（奇数段为正序，偶数段为倒序），然后将各段相加。    
  3.     例如：key=12360324711202065,哈希表长度为1000，则应把关键字分成4位一段，在此舍去最低的两位65，分别进行移位叠加和折叠叠加，求得哈希地址为105和907   
  4. （a）移位叠加              (b) 折叠叠加  
  5.    1   2   3                    1   2   3  
  6.    6   0   3                    3   0   6  
  7.    2   4   7                    2   4   7  
  8.    1   1   2                    2   1   1  
  9.    0   2   0                    0   2   0

—————— ——————
1 1 0 5 9 0 7

4.除留余数法：

  1.  假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为

h（k）=k % p ，其中%为模p取余运算。
例如，已知待散列元素为（18，75，60，43，54，90，46），表长m=10，p=7，则有
h(18)=18 % 7=4 h(75)=75 % 7=5 h(60)=60 % 7=4
h(43)=43 % 7=1 h(54)=54 % 7=5 h(90)=90 % 7=6
h(46)=46 % 7=4
此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：
h(18)=18 % 13=5 h(75)=75 % 13=10 h(60)=60 % 13=8
h(43)=43 % 13=4 h(54)=54 % 13=2 h(90)=90 % 13=12
h(46)=46 % 13=7

三。处理冲突的方法：

1.开放定址法(再散列法)：

  1.  基本思想：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，                            直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。  
  2.  这种方法有一个通用的再散列函数形式：  
  3.            Hi=（H（key）+di）% m   i=1，2，…，n  
  4.  其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。

1.线性探测再散列：

dii=1，2，3，…，m-1
冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

2.二次探测再散列：

di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )
冲突发生时，在表的左右进行跳跃式探测，比较灵活。

3.伪随机探测再散列：

di=伪随机数序列。
具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。

4. 示例：

  1.       已知哈希表长度m=11，哈希函数为：H（key）= key  %  11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。

a): 如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，

  1.            继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元。
  3. 0     1     2     3     4     5     6     7     8     9     10  
  4.                     47   26   60   69

b): 如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，

  1.            将69填入2号单元。
  3.  0     1     2     3     4     5     6     7     8     9     10  
  4.               69   47   26  60

c): 如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址

  1.            为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。
  3.  0     1     2     3     4     5     6     7     8     9     10  
  4.                      47   26  60                  69

2.再哈希法：

  1.      这种方法是同时构造多个不同的哈希函数：  
  2.                Hi=RH1（key）  i=1，2，…，k  
  3.      当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

3.拉链法(HashMap的冲突处理方式):

  1.       基本思想: 将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要
  3.                         在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
  5.      例如:  已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为13，哈希函数为：H（key）= key % 13，
  7.                  则用链地址法处理冲突的结果如图8.27所示：
  9.    位置    Entry   
  10.     0  
  11.     1  -->  40 --> 27 --> 53  
  12.     2  
  13.     3  -->  16 --> 42  
  14.     4  
  15.     5  
  16.     6  -->  32 --> 71
  18.     7  
  19.     8  
  20.     9  
  21.     10 -->  36 --> 49  
  22.     11 -->  24  
  23.     12 -->  64  
  25.             本例的平均查找长度 ASL=(1\*7+2\*4+3\*1)/13=1.38

4.建立公共溢出区：

  1.       这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

发表评论

表情：
评论列表 （有 0 条评论，375人围观）

还没有评论，来说两句吧...

相关阅读

    相关 哈希冲突解决方法

    1. 开放地址方法 （1）线性探测：按顺序决定哈希值时，如果某数据的哈希值已经存在，则在原来哈希值的基础上往后加一个单位，直至不发生哈希冲突。 （2）再平方探测：按顺序决

    妖狐艹你老母妖狐艹你老母/ 0 赞/ 142 阅读

    相关 哈希冲突及四种解决方法

    哈希冲突的产生原因 哈希是通过对数据进行再压缩，提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的，而数据可能比较多，导致经过哈希函数处理后仍然有不同的数据对

    悠悠悠悠/ 0 赞/ 269 阅读

    相关 哈希表及处理冲突的方法

    一。哈希函数和哈希冲突的基本概念 > 1.哈希函数： >   哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表成为哈希表。 >    基本思想： 首先在

    短命女短命女/ 0 赞/ 376 阅读