Hash 函数之入土攻略

Myth丶恋晨 2022-05-15 09:51 140阅读 0赞

接上一篇《数据结构检索（查找）之入土攻略（一）》：[https://blog.csdn.net/wydyd110/article/details/82113893][https_blog.csdn.net_wydyd110_article_details_82113893]

![70][]

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

**目录**

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)。

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

此处需要

![70 1][]

![70 2][]

![70 3][]

## 4.1 散列函数的构造方法 ##

### 4.1.1 直接定址法 ###

取关键词的某个线性函数值为散列地址，即 h(key) = a \* key +b。

**例子**

再如下面的数组，直接把数据和数组的下标绑定，直接 array\[n\] 就能取出数据。

**优点：**速度快，一次查找就能得到结果，时间复杂度为 O(1)

**缺点：**

**1）**浪费空间，如下面的数组只存了零星的几个数据

**2）**下面的数组，想存 1，1，2，2，3，3，4，4，4，5，8，发现存不下啦！！！

###  ###

### 4.1.2 除留余数法 ###

![70 4][]

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

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

> **除留余数法的缺点**
> 
>  *  连续的关键码映射成连续的散列值
>  *  能保证连续的关键码不发生冲突，但要占据连续的数组单元

### 4.1.3 乘余取整法 ###

>  *  关键码key\*A（0<A<1），提取乘积的小数部分
>  *  用整数n\*乘积的小数部分，再向下取整，把它作为散列地址
> 
> ![70 5][]

> **取值参考：**
> 
> 若地址空间为 p 位，就取 n = 2p
> 
> ![70 6][]

![70 7][]

**例：**设关键码 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 平方取中法 ###

![70 8][]

### 4.1.5 数字分析法 ###

![70 9][]

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

![70 10][]

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

（来源于《大话数据结构》）

> **数字分析法应用场景：**
> 
> —— 数字分析法完全依赖于关键码集合，仅适用于事先明确知道表中所有关键码每一位数值的分布情况
> 
> —— 适用于处理关键字位数比较大的情况

### 4.1.6 基数转换法 ###

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

![70 11][]

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

![70 12][]

### 4.1.7 折叠法 ###

### ![70 13][] ###

> **两种叠加方法：**
> 
> **移位叠加** — 把各部分的最后一位对齐相加  
> **分界叠加** — 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址（类似于对一张进行折叠）

![70 14][]

### 4.1.8 ELFhash字符串散列函数 ###

快要学完了，稳住稳住

![70 15][]

**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函数的特征**
> 
> •长字符串和短字符串都很有效  
> •字符串中每个字符都有同样的作用  
> •对于散列表中的位置不可能产生不平均的分布

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

请阅读《数据结构检索（查找）之入土攻略（三）》：[https://blog.csdn.net/wydyd110/article/details/82179750][https_blog.csdn.net_wydyd110_article_details_82179750]

[https_blog.csdn.net_wydyd110_article_details_82113893]: https://blog.csdn.net/wydyd110/article/details/82113893
[70]: /images/20220515/927c8dcdf15c44e6b331df0f9d98bbca.png
[70 1]: /images/20220515/3c329080472b4b6782812820e0c154d7.png
[70 2]: /images/20220515/39bd60bbcd79427fbbeb51961ac2a397.png
[70 3]: /images/20220515/cfba6ddf2fe24eb29335f4b585572b10.png
[70 4]: /images/20220515/b8d864dedb3b4f9db7580a91058e65c4.png
[70 5]: /images/20220515/7ab1142eee7a4f82b1c96a1c0fed119c.png
[70 6]: /images/20220515/71aa875dd71b427c96a592d8aeedd20b.png
[70 7]: /images/20220515/710be846f17649799ebd2d69ef5220a3.png
[70 8]: /images/20220515/a1cd36dbf7ff442fbb5b288e12534825.png
[70 9]: /images/20220515/1d2dbbf27df2420eb3e8b00c5a6cb4af.png
[70 10]: /images/20220515/a5465169f98e43959a3f33431c4de38b.png
[70 11]: /images/20220515/02022df474f8435bb03d0e5ba73f1e1f.png
[70 12]: /images/20220515/2600f13089c344998836cd7b48234163.png
[70 13]: /images/20220515/376bc86224f04bdea28a5c983e123067.png
[70 14]: /images/20220515/c72427ee3e7747ccb8eab7f6b3618852.png
[70 15]: /images/20220515/eb4c2c3c32da45b5978bdbc08f2745c0.png
[https_blog.csdn.net_wydyd110_article_details_82179750]: https://blog.csdn.net/wydyd110/article/details/82179750