高级数据结构——hash表与布隆过滤器

hash表与布隆过滤器

本文讲述了hash表的原理与实现、hash冲突及解决方法、基于位图和hash函数实现的布隆过滤器、以及用于负载均衡的分布式一致性hash等。

1. hash函数

用来求hash值的一种映射函数，hash函数可能会把两个或者两个以上的不同key映射到同一地址，这种情况称之为冲突（或者hash碰撞）；

与平衡二叉树比较：

• 平衡二叉树利用二分查找的思维，通过每次比较排除一半元素来达到快速查找的目的。时间复杂度为O(logn)。10万结点比较20次，10亿结点比较30次即可。
• 散列表，通过简历key值到索引位置的映射关系来实现快速查找，实现这种映射的函数叫做哈希函数（或者散列函数），平均时间复杂度为O(1)。

2. 选择hash函数

• 计算速度快
• 强随机分布（等概率、均匀地分布在整个地址空间）
• murmurhash1, murmurhash2, murmurhash3, siphash(redis6.0当中使用，也是rust等大多数语言选用的hash算法来实现hashmap)，cityhash都具备强随机分布性。
• siphash主要解决相近的字符串的随机分布性。
• murmurhash2是使用最频繁的hash算法。

测试地址：https://github.com/aappleby/smhasher

3. 散列冲突

不同的key可能会被映射到同一个地址，这种情况就叫做散列冲突。

3.1 负载因子

​ 负载因子：是指哈希表中已存储元素的数量与哈希表中桶（bucket）数量之间的比例，能够描述存储密度或者散列冲突的激烈程度。

3.2 冲突解决

如果负载因子在合理范围内

• 拉链法

  将冲突元素用一个链表链接起来，查找时在链表内进行线性查找。

  这样可能出现一种极端情况，当冲突的元素比较多，冲突链表过长时，会显著影响查询性能，这时可以将这个链表转换为红黑树、最小堆。可以采用超过256（经验值）个结点的时候将链表结构转换为红黑树或者堆结构。

• 开放寻址法

  • 线性探查法：有hash聚集（也叫主聚集）问题，即当多个元素发生hash冲突后，会被集中插入到hash表中的相邻位置，从而导致后续的冲突更容易发生在这些已占用的区域，形成聚集效应。这样新插入的元素需要花费更多的时间探查空闲位置，最终导致插入和查找的效率下降。
  • 二次探查法，使用非线性方式进行探查，次聚集问题，即由于探查模式相同而导致不同的键分布在相邻的位置上。
  • 再散列法，相比线性探查法就能够使插入的结点分布更加均匀，次聚集问题。

如果负载因子不在合理范围内

• 扩容：翻倍扩容
• 缩容

然后进行rehash

3. STL中的散列表

• unordered_map, unordered_set, unordered_multimap, unordered_multiset

• STL中的hash表采用类似拉链法的方法解决散列冲突。不同的是，为了实现迭代器，STL中会将每个桶对应的链表串连起来，这样所有的键值对就被组织成了一个单链表，方便迭代器的实现。这种情况下，为了实现头插法，每个桶中保存的是上一个拉链的尾结点。

以下是STL中插入一个结点时的代码实现，每个桶中的指针指向的的是另一个桶中的最后一个结点。

 if (_M_buckets[__bkt]){// Bucket is not empty, we just need to insert the new node// after the bucket before begin.__node->_M_nxt = _M_buckets[__bkt]->_M_nxt;_M_buckets[__bkt]->_M_nxt = __node;}
else
{// The bucket is empty, the new node is inserted at the// beginning of the singly-linked list and the bucket will// contain _M_before_begin pointer.__node->_M_nxt = _M_before_begin._M_nxt;_M_before_begin._M_nxt = __node;if (__node->_M_nxt)// We must update former begin bucket that is pointing to// _M_before_begin._M_buckets[_M_bucket_index(__node->_M_next())] = __node;_M_buckets[__bkt] = &_M_before_begin;
}

4. 布隆过滤器

布隆过滤器（Bloom Filter）是一种基于哈希函数和哈希表实现的空间效率非常高的概率型数据结构，用于测试一个元素是否是一个集合的成员。它有一个重要的特点：可以判断元素是否属于某个集合，但不能确定元素不属于该集合。简单来说，布隆过滤器允许有一定的误判率，但不会漏判。

4.1 背景

1. 应用场景

内存有限，只想确定某个key是否存在，不想知道具体内容。

布隆过滤器通常用于判断某个key一定不存在的场景，同时允许判断存在时由误差的情况。

过滤对不存在的值的查询

• 某个文件，如果要查询其中某条记录，可以先通过布隆过滤器判断该记录是否存在。
• 某个数据库，在执行查询之前可以先通过布隆过滤器判断目标是否存在。

2. 常见的处理场景：

1. 缓存穿透

缓存穿透的概念：

缓存穿透是指当查询的数据既不在缓存中也不在数据库中时，缓存系统没有对这些无效请求进行有效过滤，导致请求直接穿透缓存，频繁访问数据库，从而给数据库带来巨大的压力。这种情况通常出现在分布式系统中，特别是在使用缓存（如 Redis、Memcached）来优化数据访问的场景。

缓存穿透的成因：

1. 恶意攻击：攻击者通过大量查询不存在的数据，绕过缓存系统，直接将请求压向数据库。这种行为可能会使数据库负载过大，影响系统性能。
2. 自然请求：如果系统没有针对查询条件做有效过滤，用户可能请求不存在的数据（如查询一个从未有过的ID），也会直接穿透缓存，访问数据库。

缓存穿透的解决：

1. 缓存空值，当某个键查询不到数据时，可以将空结果也存入缓存，并设置一个较短的过期时间。这样即使再次查询同样不存在的键，也会直接返回缓存中的空值，避免穿透到数据库。
2. 布隆过滤器，使用布隆过滤器对所有可能存在的数据进行预先判断。在访问缓存之前，首先通过布隆过滤器判断查询的键是否可能存在。如果布隆过滤器判断该数据不可能存在，则直接返回空值，避免查询数据库。

总结：

缓存穿透是缓存系统中的一个常见问题，主要是由于缓存没有有效过滤无效请求，导致数据库承受过大的负载。通过缓存空值、使用布隆过滤器、参数校验等方法可以有效减少缓存穿透，提升系统整体性能。

2. 热key限流

热key：

热Key指的是在缓存中某些特定键被大量并发请求访问的现象。因为请求集中于少数几个Key，缓存服务器的负载会非常高，当缓存失效时，可能会导致大量请求穿透到数据库，从而引发更大的压力，甚至导致数据库宕机。

热Key的影响：

1. 缓存节点压力集中：缓存系统是分布式的，但由于热Key的访问量远超其他Key，某些缓存节点可能会成为性能瓶颈，导致这些节点比其他节点负载严重失衡。
2. 缓存失效冲击数据库：在缓存失效时，所有的请求瞬间落到数据库，数据库处理不过来，可能会导致整个系统崩溃。

热key限流策略：

1. 请求合并（Batching）：当大量请求访问某个热Key且缓存过期时，可以使用请求合并策略，只让第一个请求去加载数据，其他请求等待第一个请求的结果。这种方式可以有效避免瞬间大量请求同时去查询数据库。

2. 限流保护：对于访问量过高的Key，可以对其进行限流，控制每秒对该Key的最大请求次数令牌桶算法和漏桶算法常被用于限流实现。

3. 多副本缓存：在不同的缓存节点上放置同一个热Key的数据，这样可以将访问压力分散到多个缓存节点上。可以通过一致性哈希算法和副本策略来实现。

4. 数据预热：在某些特定场景中（如系统重启、缓存失效后），可以提前预加载一些热点数据到缓存中，避免缓存初始化时发生大量请求直接穿透到数据库。

5. 动态调整TTL：对于热Key，可以设置相对较长的缓存过期时间（TTL），这样可以避免频繁的缓存失效和更新。甚至可以根据热Key的访问频率动态调整其TTL，使得热Key在高峰期保持长时间不失效。

6. 降级策略：在极端情况下，可以采用降级策略，对于热Key的请求进行降级处理，例如返回默认值或静态页面，确保系统的可用性不受单个热Key的影响。当缓存和数据库压力都很大时，可以设置简单的降级逻辑，避免系统崩溃。

总结：

热Key限流是一种应对高频访问缓存键的策略，主要目的是为了避免缓存过载和缓存失效后对数据库的冲击。常见的限流措施包括请求合并、限流保护、多副本缓存、数据预热和分级缓存等，这些方法能够有效减轻系统负担，保证系统的稳定性和高可用性。

4.2 布隆过滤器构成

布隆过滤器由一个位示图和k个哈希函数构成。位图的大小m和哈希函数的个数k由预期存储的最大元素数和最大假阳率决定。

• 位图

• n个hash函数

4.3 原理

• 如何判断某个key不存在？

  bitmap[hash(key) % bit_size] == 0 ? 只要一个位置为0，就说明不存在。

• 如果判断某个key存在？

  无法判断某个key一定存在，只能判断某个key一定不存在。

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

  bitmap中的一个位可能对应多个key

• 假阳率？

  布隆过滤器判断一个key存在，但实际上不存在的情况。

4.4 应用分析

• n，预期存入的元素个数
• p，最大的假阳率，即判断hash值对应的位置都为1，判断为存在，而实际不存在的情况占比
• m，位图的大小
• k，hash函数的个数

从n和p计算m和k：https://hur.st/bloomfilter/

​

结论：当k=31时，假阳率（hash冲突率）是最低的。

4.5 要点

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

• 不能删除

• 先根据n和p算出m和k

5. 分布式一致性hash

一致性哈希的核心思想是通过将数据和节点映射到一个环形的哈希空间中。每个数据和节点都通过哈希函数映射到这个空间，然后通过哈希值来确定数据与节点的对应关系。

5.1 缓存失效问题

假设要对请求做负载均衡，原理是通过hash函数将请求的key值映射到一台缓存服务器中，因为hash值的分布是均匀的，所以每台服务器的负载应该也是均匀的。但是当服务器的数量发生变化时，就会导致所有请求的映射关系都被破坏，所有服务器中的缓存全部失效。

解决办法

引入哈希环，将数据和服务器结点都映射到该环上，距离数据顺时针方向上最近的服务器结点保存该节点的缓存。

• 固定算法 hash(key) % 2 ^ 32 = index
• hash迁移，改变节点的映射关系，解决大面积缓存失效，变为局部缓存失效
• 增加虚拟结点，使迁移数据量减少

如图所示，在哈希环上，每个数据被映射到顺时针方向距离其最近的服务器结点。

2. hash偏移

该问题是指当服务器结点较少时，可能服务器结点的间隔十分不均匀，导致服务器负载不均衡。

如图所示，s1服务器结点负载相对过大。

解决办法

增加虚拟结点，即一台服务器可以对应多个服务器结点，这样就增加了总的服务器结点数量，使各个服务器分布的更加均匀。

6. 大数据相关的面试题

题目
只用2G内存找到20亿个整数中出现次数最多的数

• 思路：将大文件用hash拆成小文件，确保相同得key值被放入同一个文件（映射），并且每个每个文件中得数据量大致相同（利用其强随机特性）。
• 单台机器通过hash分流到多台机器

学习参考

学习更多相关知识请参考零声 github。