哈希表及处理冲突的方法

短命女 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位十进制整数d1d2d3d7d8,如哈希表长取100,则哈希表的地址空间为:00~99
  3. 假设经过分析,各关键字中 d4d7的取值分布较均匀,则哈希函数为:h(key)=h(d1d2d3d7d8)=d4d7。例如,h(81346532)=43h(81301367)=06
  4. 相反,假设经过分析,各关键字中 d1d8的取值分布极不均匀, d1 都等于5d8 都等于2,此时,如果哈希函数为:h(key)=h(d1d2d3d7d8)=d1d8
  5. 则所有关键字的地址码都是52,显然不可取。

2.平方取中法:

  1. 当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。
  2. 这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。
  3. 例:我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11E的内部编码为05Y的内部编码为25
  4. 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,分别进行移位叠加和折叠叠加,求得哈希地址为105907
  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. 假设哈希表长为mp为小于等于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=Hkey)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…, 直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。
  2. 这种方法有一个通用的再散列函数形式:
  3. Hi=(Hkey)+di)% m i=12,…,n
  4. 其中Hkey)为哈希函数,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,哈希函数为:Hkey)= key % 11,则H47)=3H26)=4H60)=5,假设下一个关键字为69,则H69)=3,与47冲突。

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

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

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

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

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

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

2.再哈希法:

  1. 这种方法是同时构造多个不同的哈希函数:
  2. Hi=RH1key i=12,…,k
  3. 当哈希地址Hi=RH1key)发生冲突时,再计算Hi=RH2key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

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

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

4.建立公共溢出区:

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

发表评论

表情:
评论列表 (有 0 条评论,375人围观)

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

相关阅读

    相关 冲突解决方法

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

    相关 冲突四种解决方法

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

    相关 处理冲突方法

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