数据结构基础--哈希表

---

哈希函数

哈希函数

1. 输入域无穷大
2. 输出域有边界(1<<64)
3. 输入相同的样本，一定得到相同的输出结果
4. 不同的样本，有可能发生碰撞(结果相同)
5. 在输入源样本量足够大的情况下，结果将在输出域上均匀分布。

哈希函数的离散性,能够打乱样本规律。

哈希函数实现的方式

通过大量的异或，交换。打乱原本的样本结构，放大样本差异。

生成不相关的hash函数

正常一个hash函数的结果h为16字节，每个字节为一个16进制(0_9,af中的)的任意值。将前8为作为h1，后8位作为h2。

通过h1 + k * h2生成一个新的结果。并且他将于原本的h无关。

哈希函数特性的使用

大任务(hash % n)分流成N个小任务。

---

经典哈希表

经典的哈希表结构通过数组+链表的结构实现

哈希表的结构

哈希表的本质是一个数组，数组中每一个元素称为一个箱子(bin)，箱子中存放的是链表，链表节点中存放的键值对。

哈希表存储的过程

1. 根据 key 计算出它的哈希值 h。
2. 假设箱子的个数为 n，那么这个键值对应该放在第 (h % n) 个箱子中。
3. 哈希值h相同，通过链表存储在同一个箱子中。

自动扩容

当哈希表的效率因数组量过大造成损耗，进行扩容并重新简历哈希表

1. 当某一个链表上的节点个数超过某个系数(负载因子)，将进行扩容。
2. 扩容可以是离线的(在非活跃状态下进行扩容，重建哈希表，重建结束后再使用新的哈希表)

增删改查的时间复杂度

对key进行hash，通过下标寻址，查找一个短链表均为常数时间操作。

时间复杂度===》O(1)

---

设计RandomPool结构

【题目】 设计一种结构，在该结构中有如下三个功能：

1. insert(key)：将某个key加入到该结构，做到不重复加入。

2. delete(key)：将原本在结构中的某个key移除。

3. getRandom()： 等概率随机返回结构中的任何一个key。

【要求】 Insert、delete和getRandom方法的时间复杂度都是 O(1)

需要的结构：

两个哈希表，一个size变量计数

每次添加一个新的key23：

1. 令size+1
2. 将key23作为key，size作为value，记录在第一个hashMap中
3. 将size作为key，key23作为value，记录在第二个haskMap中

读取随机key时，在第二个hashMap中用(1~size)作为key进行查询返回

image

删除key时，将末尾元素与删除元素的index互换，删除该元素。并将size-1。

image

---

布隆过滤器BloomFilter

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

可以解决爬虫去重，黑名单问题。

实现一个bit类型数组，将数据容量扩容

1. 建立一个[基础类型]类型的数组
2. 一个Int类型可以表示成32bit的二进制数据，long类型则是64bit
3. 一个[Int]数组将是普通数组的32倍容量

以一个100长度的Int数组([bit]长度为3200)arr为例，当我们想修改第3000个bit：

1. 3000/32获得arr组的indexI

2. 3000%32获得arr[indexI]下，[bit]想要修改的indexB

3. 通过arr[indexI] = (arr[IndexI] | (1 << indexB))进行修改

   1左移indexB个位置，将会变成00000010000这种形式。然后与原本的arr[IndexI]相交，对应位置将会被修改为1

可以用矩阵，将数据容量继续扩容

以Int数组为例

[1000]的数组可以代表3200个bit位

[1000][1000]的矩阵则可以代表3200*1000个bit位

布隆过滤器的实现

1. 准备一个长度为m的数组，通常是bit数组
2. 将指定的key用一个hash函数求出hash值
3. 将hash % m 确定一个位置，并将该位置从0修改成1
4. 重复用k不相关个hash函数，确定多个位置并修改成1

经过这个处理之后的数组，就是布隆过滤器。

5. 当一个新的key进行查询时，也通过多次hash计算，确定是否存在于布隆过滤器

布隆过滤器的误差

由于数组长度的限制，有可能导致描黑位置过多，导致失误命中概率过高。

通过调整hash函数个个数k，以及数组长度m。可以得到不同的失误率。

布隆过滤器的优势

由于内部通过hash函数定位，最终过滤器所占内存的大小与单样本的内存大小无关。

比如一个长度为1000000的字符串，也并不需要存进数组。只需要在数组中修改k个位置即可。

布隆过滤器长度公式

[bit]的长度m，样本量n，预期失误率p，ln是自然对数

image

布隆过滤器hash函数个数公式

image

布隆过滤器真是失误率

当m和k确定之后的失误率

image

---

经典服务器抗压结构

通过对key进行hash % n 可以将读写的压力均匀的分布给三个服务器

image

而这种结构，当加入新的服务器或减少原有的服务器。我们需要像hashMap的自动扩容一样需要重建整个映射。

---

一致性哈希

经典抗压结构在扩容时，需要对数据做全量迁移，计算每一条数据的归属。

一致性哈希可以降低数据迁移的代价，同时保证负载均衡。

正常的工作流程

1. 根据关键信息计算出三个负载服务器的hashCode：h1,h2,h3。
2. 将三个值交由前方的前段服务器持有
3. 当进行读写操作时，对key进行hash，用二分的方式寻找顺时针方向最近的负载服务器并交付。

image

数据迁移的流程

只需要将黑色部分数据从1号服务器迁移给4号服务器即可。

image

虚拟节点技术

通过将每个服务器分配N个虚拟节点映射，让整个环上的分割区域约等于平均。

---

参考资料

左神牛课网算法课