本文创建于 2024-11-28；修改于 2024-11-28；

主要内容：

image

一、散列表

根据 key 计算 key 在表中的位置的数据结构；是key 和其所在存储地址的映射关系；

1. 构成

  • Hash 函数
  • 数组

2. 哈希函数

映射函数 Hash(Key) = addr；

选择哈希函数的原则

  • 计算速度快，性能高
  • 强随机分布（体现在数据被均匀、等概率的分布在整个地址空间）
  • 常用 hash函数：murmurhash1(速度快，质量差)、murmurhash2(速度快，质量也还行)、murmurhash3(速度慢，质量最好)、siphash（redis 6.0 中使用，rust 等大多数语言选择该hash算法来实现 hashmap），cityhash等都具备强随机分布性
  • siphash 主要解决字符串接近的强随机分布性

3. 哈希冲突

冲突的原因

哈希函数可能会把两个或两个以上的不同的 key 映射到同一个地址，这种情况称之为 hash冲突(或 hash碰撞)。

负载因子

  • 负载因子：数组中元素的个数/数组的容量；用来形容散列表的存储密度；负载因子越小，冲突越小，负载因子越大，冲突越大；

冲突处理

负载因子在合理范围内的处理方法：
链表法

使用链表将冲突元链接起来，但可能出现冲突元素过多，链表性能低的情况，此时，可以将链表转换为 红黑树，最小堆；时间复杂度由链表O(n) 转化为O(log2n)；通常在链表长度超过 256 个时将链表结构转换为红黑树或堆结构；

开放寻址法

将所有的元素都放在数组中，不使用额外的数据结构辅助；一般使用线性探测的思路解决：

  1. 当插入新元素时，使用哈希函数在哈希表中定位元素位置；
  2. 检查数组中该索引是否已经存在元素。如果该位置不存在元素，则插入；否则进行下一步：
  3. 对第2步得到的数组索引加上一定步长接着检查第2步：
    • i+1, i+2, i+3, i+4…
    • i-1^2, i+2^2, i-3^2, i+4^2…
    • 但是上面两种方法均会导致一个问题：同类hash会聚集，也就是近似key的hash值也接近，在数组中的存储位置也接近；可以使用 双重哈希来解决。
负载因子不在合理范围内的处理方法：

size 表示数组中有效元素的长度；capacity 表示数组的容量(最大能存储的元素个数)

扩容

当 size > capacity 时，我们应该对数组进行扩容操作；

缩容

当 size < 0.1 * capacity 时，我们应该对数组进行扩容操作；

rehash

哈希函数的形式：index = hash(key) % capacity；当对数组进行扩容或缩容操作后，数组的 capacity 发生改变，自然的，每个数组元素的index也应当重新计算。

4. STL 中 unordered_* 散列表实现

STL 中，unordered_map, unordered_set, unordered_multimap, unordered_multiset底层实现都是散列表；

STL 为了实现迭代器的操作，对发生哈希冲突时使用的链表做了优化，把各个 bucket 所使用的链表链接在了一起，形成一个全局链表(单链表)：

插入节点：

使用头插法。

image

二、布隆过滤器 BloomFilter

当我们只想判断某个键(key)在数据集中是否存在，而不需要拿到具体的值(value)，这时我们就可以使用 布隆过滤器 来实现；

能确定一个 key 一定不存在，可控假阳率的确定 key 存在；

1. 构成

  • 位图 BitMap
  • 多个 Hash函数

2. 原理

buf[8] 构成了一个 8x8 的位图，根据 hash(key) 得到 index 的值，之后再对index进行计算，得到 key 在位图中的坐标。

image

插入和查询流程：

插入：先使用n个hash函数对 key 进行计算，拿到 n 个 index，之后，在位图中，将对应 index 得索引位置为1；

查询：使用n个hash函数对 key 进行计算，拿到 n 个 index；与位图中的索引位为index的值进行比较:

  • 不存在：只有有一个索引位的值为0，则 key 不存在；
  • 如果所有 index 对应索引位的值都为 1，key 也不一定存在；

布隆过滤器 不支持删除操作：

  • 在位图中每个索引位只有两种状态（0或者 1），一个索引位被设置为1状态，但不确定它被设置了多少次；也就是不知道被多少个 key ，多少次 hash 映射而来以及是被具体哪个 hash 函数映射而来；
image

确定布隆过滤器的大小：

预估要在布隆过滤器中插入的 key 的个数为 n；

设定 假阳率 p 为需求值；

通过下面这个网站可以计算出对应需求的 位图大小m以及最低需要的 Hash函数个数k：

布隆过滤器在线计算: https://hur.st/bloomfilter

三、分布式一致性Hash算法

用来解决分布式缓存扩容的问题；

分布式缓存为了避免缓存失效，通常使用 固定算法 和 数据迁移 两种方法；

为了保证分布式缓存中的数据均衡，通常使用 增加虚拟节点 的方法；

1. 固定算法

固定算法是指在分布式缓存系统中，使用一种固定的算法来决定数据应该存储在哪个节点上。常见的固定算法包括哈希算法、一致性哈希算法等。

一致性 Hash 算法是一种常见的固定算法；它通过将缓存节点(k)和数据(192.168….)映射到一个逻辑圆上，来决定数据应该存储在哪个节点上。

image
  • 确定数据存储的节点，对于每个数据，找到逻辑圆上顺时针方向最近的节点。例如：
    • 192.168.1.100，顺时针方向最近的节点是 k1
    • 192.168.1.101，顺时针方向最近的节点是 k2
    • 192.168.1.102，顺时针方向最近的节点是 k4 (未插入 k3 节点前)

2. hash迁移

在分布式缓存系统中，当节点增减(会造成缓存实效)或数据分布不均衡时，将数据从一个节点迁移到另一个节点的过程称为数据迁移；

如上图，192.168.1.102 原来存储在 k4中，当我们插入新节点 k3 后会发现，192.168.1.102 顺时针方向的最近节点变成了 k3，所以就导致了 192.168.1.102 所映射的数据发生了缓存实效，我们无法再根据一致性hash函数来获取到 192.168.1.102 的值；

我们此时就需要将 192.168.1.102 从 k4 节点迁移到 k3 节点中，从而避免缓存实效。

3. hash 偏移

当样本数过少，造成算法不稳定，每个节点存储的数据量极其不均衡，这种现象称为 hash偏移；

通常使用 增加虚拟节点 的方法来解决hash偏移问题，增加虚拟节点 是指在分布式缓存系统中，为每个物理节点创建多个虚拟节点，并将这些虚拟节点映射到逻辑圆上。通过增加虚拟节点，可以进一步提高数据分布的均衡性。

image

增加虚拟节点达到的效果：

  • 提高均衡性 ：通过增加虚拟节点，可以进一步提高数据分布的均衡性，避免单个物理节点负载过重。
  • 简化数据迁移 ：虚拟节点的增加可以简化数据迁移的过程，减少迁移的数据量。

四、应用实例

如何只用 2GB 内存在 20亿个整数中找到出现次数最多的数？

image