数据结构检索(查找)之入土攻略(二)

接上一篇《数据结构检索(查找)之入土攻略(一)》:https://blog.csdn.net/wydyd110/article/details/82113893

欢迎继续入坑数据结构之检索(查找),我保证这章将灰常“有趣”。

目录

4  散列表的检索

4.1 散列函数的构造方法

4.1.1 直接定址法

4.1.2 除留余数法

4.1.3 乘余取整法

4.1.4 平方取中法

4.1.5 数字分析法

4.1.6 基数转换法

4.1.7 折叠法

4.1.8 ELFhash字符串散列函数

4.2 散列函数的应用


4  散列表的检索

下面引用《大话数据结构》中的例子作为开场白:

散列:即哈希,就是把任意长度的输入key作为自变量,通过散列函数h(),变换成固定长度的输出,该输出就是散列值,作为数据对象的存储地址。

                                                                     存储地址 = h(关键字key)

冲突(Collision):可能不同的关键字会映射到同一个散列地址上,即h(key1)=h(key2)。

同义词:发生冲突的两个关键码。

此处需要

4.1 散列函数的构造方法

4.1.1 直接定址法

4.1.2 除留余数法

本方法的关键在于选择合适的p,p如果选得不好,会导致冲突增多,散列值分布不均匀。

若散列表表长为m,通常p为小于或等于m的最大质数。

除留余数法的缺点

  • 连续的关键码映射成连续的散列值
  • 能保证连续的关键码不发生冲突,但要占据连续的数组单元

4.1.3 乘余取整法

  • 关键码key*A(0<A<1),提取乘积的小数部分
  • 用整数n*乘积的小数部分,再向下取整,把它作为散列地址

          

取值参考:

若地址空间为 p 位,就取 n = 2p

  

例:设关键码 key = 123456, n = 10000且取 A = 0.6180339。

  解:123456 * 0.6180339 = 76300.0041151

          提取乘积的小数部分 0.0041151

          n * 0041151 = 41.131 = 41

          h(key) = 41

4.1.4 平方取中法

4.1.5 数字分析法

11位的手机号,前三位是接入号,一般对应不同运营商公司的子品牌,如130是联通如意通,136是移动神州行,153是电信等;中间四位是HLR识别号,表示用户的归属地;后四位才是真正的用户号。

                                                          

用手机号后四位来存储用户还是容易出现冲突,此时还可以对抽取出来的数字再进行反转(1234改成4321),右环位移(1234改成4123)等。

(来源于《大话数据结构》)

数字分析法应用场景:

—— 数字分析法完全依赖于关键码集合,仅适用于事先明确知道表中所有关键码每一位数值的分布情况

—— 适用于处理关键字位数比较大的情况

4.1.6 基数转换法

  1. 把关键码看成是另一进制上的数
  2. 再把它转换成原来进制上的数
  3. 取其中若干位作为散列地址
  4. 一般取大于原来基数的数作为转换的基数,并且两个基数要互素(公约数只有1的两个整数)

看例子看例子.......................................

4.1.7 折叠法

两种叠加方法:

移位叠加 — 把各部分的最后一位对齐相加
分界叠加 — 各部分不折断,沿各部分的分界来回折叠,然后对齐相加,将相加的结果当做散列地址(类似于对一张进行折叠)

4.1.8 ELFhash字符串散列函数

快要学完了,稳住稳住

ELF:Executable and Linking Format可执行链接格式

直接上ELFhash函数的程序实现:

int ELFhash(char* key) {
  unsigned long h = 0;
    while(*key) {
       //h左移4位,当前字符ASCII存入h的低四位
       h = (h << 4) + *key++;
       unsigned long g = h & 0xF0000000L;
       //如果最高位不为0,则说明字符多余7个,如果不处理,
       //再加第九个字符时,第一个字符会被移出,因此要有如下处理
       if (g) {
           h ^= g >> 24;
           //清空28~31位
           h &= ~g;
       }
           
    }
  return h % M;
}

ELFhash函数的特征

•长字符串和短字符串都很有效
•字符串中每个字符都有同样的作用
•对于散列表中的位置不可能产生不平均的分布

4.2 散列函数的应用

冲突是不可能完全避免的,小情侣间有争吵也是不可避免的,当冲突发生时,我们该如何去处理呢?

请阅读《数据结构检索(查找)之入土攻略(三)》:https://blog.csdn.net/wydyd110/article/details/82179750

原文链接:加载失败,请重新获取