美文网首页IT狗工作室数据结构和算法分析
第12篇:C++ 哈希表 -散列函数的构造方法

第12篇:C++ 哈希表 -散列函数的构造方法

作者: 铁甲万能狗 | 来源:发表于2020-04-09 20:38 被阅读0次

我们前面已经简单说过散列函数的相关概念,阅读了之前哈希表的系列随笔后,想必你对哈希表有个大概的了解。下面会基于前面的基础深入探讨一下散列函数常用的构造方法,因为一个设计良好的散列函数实现,必须满足以下几点指导原则

  • 计算尽可能地简化,因为我们希望尽可能达成O(1)的时间消耗
  • 键(key)对应的散列值(哈希表中元素的地址)分布均匀,尽可能减少冲突

数字关键字的散列函数构造

直接定址法

就是按照线性函数的表达式计算数字关键的散列值,如下表达式


例如:下面,我们需要将下表的以年份为键,将每年的销售额数据散列到哈系表中,那么直接情况就比较简单,我们可以取年份中的地一个年份作为一个常数,这里显然另常数A=1,B=-2010,可以让年份关键字转换为更小的整数,这样做有助于节省哈希表的内存空间

取模运算法

这这方法也叫除留余数法,一般表达式


其中N通常是哈希表的尺寸,并且N是素数,因为与数字关键字与取模会最大限度减少散列冲突的发生,取模运算后的值作为插入元素的地址,下面就是一个示例,通常在使用开放寻址方案实现的哈希表,经常使用到取模运算法
无标题.gif

反例演示

对于数字关键字,使用取模运算方法有个致命的弱点,考虑一下上面的示例,我们假设哈系表的尺寸N=11
那么h(k)=k mod 11,探测函数使用的是线性探测p(x)=x,那么要插入哈希表的集合中有某个数字关键字的散列值达到哈系表的最大索引值,并且还与集合中其他元素的散列数值冲突,若计算递增x,那么该数字关键字重算的散列已经发生哈系表溢出的情况,
例如下面这个示例,下表中数字关键字383的初始散列数值为9与关键字42冲突,按照线性探测的逻辑就是这么样:

  • x=0,i=h(383)+p(0)=(383 mod 11)+0=9 和关键字42冲突
  • x=1,i=h(383)+p(1)=(383 mod 11)+1=10 和关键字32冲突
  • x=2,i=h(383)+p(2)=(383 mod 11)+2=11,更糟糕的事情发生了哈希表溢出


    ss8.png

    然后,你可能会说,让哈希表重散列啊~不就有更多闲置空间吗?这种做法是得不尝失的,没有从根源上去解决问题。

  • 首先,哈希望左侧的索引为{1,2,3,4,5}的存储桶空间没有利用上。
  • 其次,过早重散列导致内存空间巨大浪费,而且导致哈系表中元素没必要深度拷贝

于是,在好些资料你甚至会发现有人对取莫运算的散列函数表达式,做了一些修改,例如这样:

h(x)=k mod N的修订版本
其实,这条表达式的思想是,假若k mod N计算的值达到了哈系表的最大索引(高地址的边界),用N减去k mod N令最终的散列函数的结果跳转到哈希表的低地址查找可用存储桶。但事实上做法仍然会导致哈系表溢出的情况,于事无补的。因为当k mod N=0时,h(k)=N,此时就是哈希表溢出。

通过上面的例子,我们看到取模运算法实现的散列函数的缺陷在于,当作为传入数据源的关键字集合的个数m和哈系表的初始尺寸N,但N-m这个绝对值不够大的话,会容易导致关键字插入哈希表溢出冲突次数的发生概率会增大。

数字分析法

当给定的数字关键字由很多位组成,有些位是相对固定,而有些位会随机变化,数字分析法的主要思想就是从这些关键字中提取随机变化的部分组合一起作为这些数字关键字的地址,从而达到映射均匀的目地。

例如:我们的身份证号18位,如下图特征

  • 索引0-4,索引6-8,索引10-12,索引14都是相对固定不会有太大的的变化
  • 索引5,索引9,索引13,索引15-17,这些是随机变动的

我们可以将随机变动的位提取出来组合成一个数字,例如下图,

  • Step1:从红色的随机位中提取数字字符出来组合成42321,最后一位是检验位要么是X或0-9,检验位最后一步处理
  • Step2:将随机数字字符串"42321"从ASCII码转换为实际的整数,对应如下图h2(k)散列函数
  • Step3:将带有特殊含义的随机位做特殊处理,在本例中若检验位是字符'X'(罗马数字X),若是k[17]等于字符'X'就新增一个10进位后+10,若出现0-9之间的ASCII字迹,就以k[17]-'0'转换为ASCII数字字符对应意义上的各位整数,最后和h2(k)的整数结果相加


    ss8.png

最终h1(k)是对应本示例中对应身份证号码的主散列函数(Primary Hash Function),而h2(k)我们称为辅助函数(Secondary Hash Function),一个主散列函数可以有多个解决子问题的辅助散列函数.

备注:数字分析法经常用到进制位以及ASCII转换为整数这两项基础知识,若不熟悉的读者,请自行恶补这方面的知识。

折叠法

更新中......

相关文章

  • 数据结构与算法系列 (4) Hash表 & Hash算法

    1.基本概念 1.1 散列表/哈希表(Hash table)& 散列函数 1.2 概念澄清 1.3 构造散列函数的...

  • 数据结构5:散列(哈希)

    16.散列(哈希): 16.1:定义16.2:构造散列函数的几种方法 16.3:哈希冲突的解决方法 16.3....

  • 第12篇:C++ 哈希表 -散列函数的构造方法

    我们前面已经简单说过散列函数的相关概念,阅读了之前哈希表的系列随笔后,想必你对哈希表有个大概的了解。下面会基于前面...

  • 漫谈散列函数

    说到散列,一般对应于散列表(哈希表)和散列函数。我们今天不谈哈希表,仅谈下散列函数。 定义 引一段百度百科关于散列...

  • 散列,哈希和杂凑

    说到散列,一般都会想到散列函数和哈希表。下面我就"瞎扯"一下散列函数,哈希表之后再扯; 定义 百度百科的定义 Ha...

  • 算法图解--散列表

    散列表 也叫哈希表,主要知识点为散列函数,冲突解决方案。 散列函数散列函数是这样的函数,无论你给它什么数据,它都会...

  • 散列、对称加密和非对称加密

    一、散列(哈希) 1.简介 散列函数,又称散列算法、哈希函数,是一种从任何一种数据中创建小的数字“指纹”的方法。散...

  • 《iOS面试题整理》 - 哈希表

    哈希表, 也叫散列表, 是数组的一种扩展把关键字或者键转换为数组下标的方法叫做散列函数散列函数计算得到的值也叫做散...

  • 哈希算法

    什么是哈希算法 了解哈希算法需要了解以下几个概念。 散列表(hash table) 与散列函数 散列表也叫哈希表是...

  • 散列表算法

    散列表算法又称为Hash list(哈希表)。散列表由散列函数和一个数组组成。通过像散列函数输入一个值,散列函数返...

网友评论

    本文标题:第12篇:C++ 哈希表 -散列函数的构造方法

    本文链接:https://www.haomeiwen.com/subject/wrmcmhtx.html