哈希函数构造以及解决哈希冲突之开散列和闭散列

Dear 丶 2023-06-24 11:23 147阅读 0赞

哈希 可以不经过任何比较，一次直接从表中得到搜索的元素，像那些 vecotor ，list ，AVL 呀，都是必须经过比较之后才能找到元素的，所以哈希在查找元素方面时间复杂度是O(1)

那它是怎么做到的呢？其实是通过某种函数使元素的存储位置与它的关键码之间建立一种映射关系

哈希表的实现主要是 **构造哈希** 和 **处理哈希冲突** 两方面

我们先讨论如何构造，最后讨论如何处理哈希冲突

对于构造哈希来说，常见的哈希函数包括 **直接地址法**，**除留余数法**，平方取中法，折叠法，随机数法…

那么选择什么样的哈希函数主要取决于关键字的特点

(1) 如果事先知道关键字的分布情况，并且发现这些关键字很小，而且连续，那么就可以采用 直接地址法或者除留余数法

> **直接地址法**：取关键字的某个线性函数为散列地址：Hash（Key）= A \* key + B

> **除留余数法**：假如散列表中允许的地址数为 m ,取一个不大于 m 且最接近 m 的一个质数 p 作为除数 ，按照哈希函数 Hash(key) = key % p (p<=m),将关键码转换成哈希地址

(2) 如果不知道关键的分布，且这些关键字的位数也不大，就可以采用平方取中法。

> 平方取中法：对一个数平方后取出中间的数字作为哈希地址，这种方法适合于不知道关键字的分布且位数也不是很大的情况

(3) 如果不知道关键字的分布，且这些关键字的位数很大的情况，可以采用折叠法。

> 折叠法：是将关键字从左到右分割成位数相等的几部分，然后将这几部分跌加求和，并按散列表表长取出后几位作为散列地址，这种方法适用于不知道关键字分布且位数比较大的情况

(4) 如果关键字的长度层次不齐，那么可以选择随机数法

> 随机数法：选择一个随机函数，取关键字的随机函数为他|的哈希地址，即 H(key) = random(key) 其中 random 为随机函数，这种方法适用于关键字长度不相等的时候。

--------------------

检测哈希函数是否合理？

*  哈希函数的值域必须要在范围之内
 *  哈希函数产生的地址尽量的均匀
 *  哈希函数设置尽量简单

如果设置不合理，产生哈希冲突的概率就大

哈希冲突 就是不同的关键字通过哈希函数得出相同的哈希地址

判断是否哈希冲突，可以在插入的时候给位置做一个 EXIST 标记，如果该位置是 EMPTY 时，表示没有冲突，否则就发生了冲突

对于处理哈希冲突，最常用的方法有 闭散列 ，开散列 ，再哈希法，建立公共溢出区…

**(1)闭散列**(开放定址法): 当发生哈希冲突时，且哈希表未满，可以通过探测方法把 key 存放到冲突位置的下一个空位置中

方法一：线性探测  
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。当然这种方法比较简单，也有很大的缺陷，就是容易造成数据的堆积，使得关键字需要多次比较，这样一来就导致搜索效率低…

方法二：二次探测  
二次探测也可以理解为再哈希法，如果遇到哈希冲突，不需要依次向后探测，而是通过另一个哈希函数找寻空位置，这种方法不易产生数据堆积问题，但是增加了计算时间.

方法三：伪随机探测  
建立一个伪随机数发生器（如i=(i+p) % m），生成一个位随机序列，并给定一个随机数做起点，每次加上这个伪随机数，++就可以了

**(2) 开散列** (链地址法)：首先计算出所有关键码对应的散列地址，具有相同地址的关键码放到同一个集合中，每个集合称为一个桶，每个桶中元素通过单链表连接起来，所有链表的头结点存储在哈希表中

所以桶中存放的其实都是哈希冲突的关键码

桶的大小是确定的，那如果随着数据的插入，桶的容量已经不够了，这时候就要对哈希表进行增容，其实开散列最好的情况就是每个哈希桶中正好放一个节点，那么每一次的插入就会冲突，所以当元素个数等于桶的个数时，就可以增容了

#### 如何增容 ####

不管是闭散列还是开散列都不可以直接使用 vector 序列那样的增容方法，因为那样会导致哈希函数不一致而无法找到元素，而且开散列的哈希冲突时通过指针挂在桶上的，因为 vector 增容底层是一个数据拷贝的过程，这样会有浅拷贝的风险

所以可以重新创建一个哈希表，将旧哈希表存在的元素插入到新哈希表中，然后交换新哈希表对象和旧哈希表对象，也可以直接将旧哈希表中的节点搬移到新哈希表中

问：开散列和闭散列哪个更节省存储空间？

使用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销，但是由于 开放定址法 必须保持大量的空闲空间以确保搜索效率，例如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间…

问：使用开散列处理哈希冲突的时候，桶的个数设置多少比较合适？

这个得根据关键码多少来判断，但是设置为质数比合数效率高，因为设置为质数可以最大程度上减小哈希碰撞(哈希冲突)，使哈希后的数据分布更加均匀，使用合数可能会造成很多数据集中在一起

## 哈希表的应用 ##

### 面试题1 ###

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中

方法一：遍历，时间复杂度O(N)  
方法二：排序(O(NlogN))  
方法三：利用二分查找: logN

方法四：由于数字比较多，占用内存大，无法一次性加载到内存中，所以我们可以利用位图解决

**位图法思想**：对于40亿个 unsigned int 的整数，每个数字用1个二进制数（一个二进制数占用1Bit，1Byte = 8Bit）来表示该数字是否存在，0为不存在，1为存在。从低位开始数：

第1个二进制数表示整数0是否存在，

第2个二进制数表示整数1是否存在，

第3个二进制数表示整数2是否存在，

依次类推 … …

第4294967296个二进制数用于表示整数4294967295是否存在。

unsigned int 在32&64位编译器的范围为 0～4294967295，4294967296个二进制数大约占用512M内存，是一个可以接受的范围，如下图…  
![在这里插入图片描述][20191223141352718.png]

--------------------

### 面试题2：哈希切割 ###

1.给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

由于 100G 大小的文件无法加载到一般的内存中，所以我们可以考虑将其分为 1000 个文件，将每一个文件中 IP 映射到哈希表中， 可以利用哈希函数将IP 转换为整数，这样我们就可以将相同的 IP 放到同一文件，将每个文件中出现次数最多的 IP 统计出来，比较1000份文件中，选出次数最多的 IP 就可以了

有一点需要注意的是，如果哈希冲突过多，那么就要考虑将其进行哈希切割，比如 IP地址为 192.168.0.1 的大小已经超过了一个文件存储的IP个数，可以将其存放在另外的文件中，然后合并的时候，再加回去.

与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

在统计出 1000 份文件中每个文件里出现次数最多的IP，任意选择 k 个 IP 建立 **小堆**，然后依次遍历和堆顶元素比较，如果大于堆顶元素则 覆盖它，并向下调整，如果比堆顶元素还小的话，就直接跳过继续遍历，遍历完之后，堆中的元素就是出现次数最多的 k 个 ip

### 面试题3：位图应用 ###

1. 给定100亿个整数，设计算法找到只出现一次的整数？

(1) 分桶法：将100亿个整数分别进行哈希计算，映射到不同的区间，在每个区间中找到只出现一次的数字，然后集合起来， 重复这样进行，直到找出来唯一的一个数字即可

(2) 我们可以把 100 亿整数分到100 个文件中去，找出每一份中只出现一次的数字，最后将100 份文件汇总起来，就这样重复进行，直到找到唯一的数字

(3) 位图法：首先看是否有无符号，如果有符号则使用两个 bitmap ，一个存储正数，一个存储负数，如果没有符号则使用一个 bitmap ，我们使用两位bit来判断一个数出现过几次，比如 00 出现了0次，01出现一次，10出现多次，比如存放了一个整数100，那么就看第100 \* 2 位 和 第100 \* 2+1 位的数字，如果是01就说明出现了一次；这样下来，大概需要 2\*\*31 \* 2 个bit位，8bit = 1字节 ，1024字节= 1kb ,这样算下来，大概100亿个整数需要 512 mb 的存储空间.

优缺点：采用位图最大的好处就是节省空间，但是哈希的效率更快，结果也比较精确。

[bitmap算法][bitmap]

2.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

我们知道，一个位图是500M，两个位图也才1G,这里采用位图比较合适

求文件的交集,可将其两个文件分别建立位图1和位图2,将两个位图进行&(按位与运算),得到的结果就是两个文件的交集

### 面试题4：布隆过滤器 ###

1.给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

方法一：找交集，我们可以考虑使用哈希分割， 将两个文件分别分成1000份的小文件，将问题转化为求这两个小文件划分出来的每个小文件的交集 ，将每个小文件的交集求出，整合成两个文件的交集。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70]  
方法二：使用布隆进行过滤，将其中的某一个文件映射到位图当中，取另一文件的内容进行比对，如果不存在，那么就不是交集，如果存在，可视为交集

注意：虽然布隆在映射时会映射多个位置，但判断是否在位图中存在时还是可能出现误差，故此方法为近似算法

2. 如何扩展BloomFilter使得它支持删除元素的操作

布隆的删除和计数可归为一类问题，原本布隆是一个元素映射到多个位置上，这个位置上的值是一个Key,现在将其改为数据存在的个数，每当映射到相同的位置，该位置上的数进行加1，最后每个位置上的值表示出现某一元素映射到该位的次数

### 面试题5：倒排索引 ###

给上千个文件，每个文件大小为1K—100M。给n个词，设计算法对每个词找到所有包含它的文件，你只有100K内存

[20191223141352718.png]: https://img-blog.csdnimg.cn/20191223141352718.png
[bitmap]: https://www.sohu.com/a/300039010_114877
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191225150511424.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0,size_16,color_FFFFFF,t_70