当前位置：首页 > news >正文

从红黑树到哈希表：原理对比与典型场景应用解析（分布式以及布隆过滤器）

news 来源：原创 2025/9/9 14:29:09

在数据结构的世界里，红黑树一直以「自平衡二叉查找树」的身份备受赞誉。凭借红黑节点的精妙设计，它能将插入、删除、查找的时间复杂度稳定控制在 $(\log n)$ ，成为处理有序数据的经典方案。然而，当业务场景对「快速查找」提出极致要求时，红黑树的局限性逐渐显现 ——我们是否需要一种更直接的数据访问方式？哈希表正是为突破这一困境而生，它用独特的映射机制颠覆了传统树结构的查找逻辑

1 红黑树的优势与潜在短板
2.哈希表：以空间换时间的终极方案
- 2.1 hash 函数
- 2.2 哈希冲突
- 2.3 哈希冲突解决
- - 2.3.1 扩容
  - 2.3.2 链表法
  - 2.3.3开放寻址法
3 布隆过滤器（哈希升级）
- 3.1 背景
- 3.2 位图
- 3.3 布隆操作
- 3.4 应用分析
4 分布式一致性 hash
- 4.1 背景
- 4.2 hash 偏移
- 4.3虚拟节点
- 4.4 数据迁移

1 红黑树的优势与潜在短板

红黑树的核心优势:红黑树通过五条严格规则（如根黑、叶黑、红节点无子红、黑高平衡）维持树的平衡，确保最坏情况下的操作效率。在需要维护数据有序性的场景（如数据库索引、任务调度优先级队列）中，它能高效完成范围查询（例如：查找价格在 100-200 元之间的商品）。
红黑树的性能瓶颈:尽管 $(O(\log n)$ 的复杂度已足够优秀，但当业务聚焦于 「单键快速查找」 时，红黑树的比较式搜索显得冗余：
- 路径依赖：每次查找需从根节点沿比较路径逐层遍历，即便树高度可控，仍存在对数级的比较开销。
- 有序性代价：为维持树的平衡与有序，插入 / 删除时需频繁调整节点颜色与结构（旋转操作），额外消耗计算资源。
- 范围无关场景：若应用仅需「根据 ID 获取用户信息」这类单键操作，红黑树的有序性反而成了负担。

2.哈希表：以空间换时间的终极方案

哈希表借助哈希函数（如 MD5、FNV 哈希）将数据键值映射为数组索引，实现「键→值」的直接访问。例如，将用户 ID 通过哈希函数计算后，直接定位到对应数组槽位获取用户信息，理论上可将查找复杂度降至 $(O (1))$

2.1 hash 函数

定义：给定一个输入数据（可以是字符串、数字、文件内容等各种形式的数据），哈希函数会对其进行一系列的计算和转换，最终生成一个固定长度的输出值，这个输出值就是哈希值。例如，对于字符串 “hello”，经过某个哈希函数计算后，可能得到一个 32 位的十六进制数作为哈希值。
特性：

确定性：对于相同的输入数据，哈希函数必须始终返回相同的哈希值。也就是说，无论何时对同一个数据调用哈希函数，得到的结果都是一致的。例如，多次对字符串 “world” 使用同一个哈希函数计算，得到的哈希值应该完全相同。
强随机性 (高效性和均匀分布性):在处理海量文件的哈希计算时，快速的哈希函数可以显著提高处理速度。理想情况下，哈希函数应该能够将输入数据均匀地映射到哈希值的取值范围内。这样可以减少哈希冲突（不同的输入数据得到相同的哈希值的情况）的发生概率
单向性：哈希函数是一种单向函数，即从哈希值很难（甚至不可能）反向推导出原始的输入数据。这一特性在数据存储和安全领域非常重要，比如存储用户密码时，通常存储的是密码的哈希值，而不是原始密码，这样即使哈希值被获取，也无法轻易得到原始密码。

常用的哈希函数（非密码学无需了解实现只需选择就行）

MurmurHash2：计算速度比较快，且质量较好，在众多非加密哈希算法中是使用较为广泛的一种。其内部循环使用了乘法和旋转操作。不过，即使使用随机化种子实施 MurmurHash2，也容易受到 Hash DoS 攻击，通过差分密码分析能生成导致哈希碰撞的输入。
CityHash：计算速度非常快，在处理大规模数据时表现出色。能够产生高质量的哈希值，哈希冲突的概率较低。它针对不同的平台和数据类型进行了优化，具有较好的适应性
SipHash：要解决相近字符串的强随机分布性问题，能够抵抗各种形式的哈希冲突攻击，尤其是对恶意构造的输入具有很强的抵抗力，安全性较高。计算过程相对复杂，不过在现代硬件上仍然具有较好的性能

2.2 哈希冲突

定义:
哈希函数的作用是把任意长度的输入数据转化为固定长度的哈希值。哈希冲突指的是当两个或多个不同的输入数据，经过同一个哈希函数计算后，得到了相同的哈希值。可以用数学公式来表示：若有输入数据 $x_1$ 和 $x_2$ ，且 $x_1 \neq x_2$ ，但经过哈希函数 H 计算后， $H(x_1) = H(x_2))$ ，这种情况就属于哈希冲突。
负载因子：数组存储元素的个数 / 数据长度；用来形容散列表的存储密度；负载因子越小，冲突越小，负载因子越大，冲突越大；

2.3 哈希冲突解决

2.3.1 扩容

负载因子达到阈值：负载因子是指哈希表中已存储元素的数量与哈希表大小的比值。当负载因子超过预先设定的阈值（通常为 0.75 或 0.8）时，说明哈希表中元素已经比较密集，哈希冲突的概率增加，此时需要进行扩容。例如，一个哈希表初始大小为 16，当存储的元素达到 12 个时（负载因子达到 0.75），就可能触发扩容操作。
扩容操作

创建新的哈希表：按照一定的扩容策略，比如将哈希表的大小扩大为原来的两倍，创建一个新的更大的哈希表。这个新哈希表具有更多的槽位，能够容纳更多的元素，从而降低哈希冲突的概率。
重新计算哈希值并复制数据：遍历原哈希表中的每个元素，使用相同的哈希函数重新计算每个元素在新哈希表中的哈希值，并将其插入到新哈希表的相应位置。由于哈希表大小发生了变化，元素的哈希值在新哈希表中的分布也会不同，所以需要重新计算和分配位置。

和string以及vector扩容差不多

2.3.2 链表法

引用链表来处理哈希冲突；也就是将冲突元素用链表链接起来；这也是常用的处理冲突的⽅式；但是可能出现一种极端情况，冲突元素比较多，该冲突链表过长，这个时候可以将这个链表转换为红黑树；由原来链表时间复杂度转换为红黑树时间复杂度；
普通：
在这里插入图片描述
STL中hashmap

将链表连起来，方便实现迭代器

2.3.3开放寻址法

定义：当向哈希表中插入一个元素时，通过哈希函数计算出该元素的哈希值，若该位置已被占用（即发生哈希冲突），则按照一定的探测策略在哈希表中寻找下一个空闲的位置来插入该元素。查找元素时，也按照同样的探测策略在哈希表中进行搜索，直到找到目标元素或确定元素不存在。

操作：

线性探测：当发生哈希冲突时，从冲突位置开始，依次向后探测下一个位置，直到找到空闲位置为止
二次探测：探测的步长是探测次数的平方。即第一次探测的步长为 1²，第二次为 2²，第三次为 3²，以此类推。例如，发生冲突后，第一次探测的位置是冲突位置 + 1²，第二次是冲突位置 + 2²，第三次是冲突位置 + 3²，若超出哈希表范围，则对哈希表大小取模。

哈希聚集（这上面都会造成哈希聚集）：当多个元素的哈希值相近时，它们会在哈希表中连续占据相邻的位置。->增加探测次数和降低插入效率
双重哈希：：使用两个哈希函数，第一个哈希函数用于计算初始哈希值，当发生冲突时，使用第二个哈希函数计算一个步长，然后按照这个步长进行探测。(可以解决)

步长随机性：第二个哈希函数 $h_2(key)$ 计算出的步长是基于元素的键值生成的，不同元素的步长可能不同。这使得在发生冲突时，元素不会像线性探测那样总是依次向后或按照固定模式探测，而是以不同的步长跳跃式地寻找空闲位置，从而避免了元素在某个区域过度聚集。
均匀分布：通过合理设计两个哈希函数，可以使元素在哈希表中更均匀地分布。

3 布隆过滤器（哈希升级）

3.1 背景

在计算机科学和信息技术领域，特别是在处理大规模数据集合时，经常需要快速判断一个元素是否属于某个集合。例如，在网络爬虫中，需要判断一个 URL 是否已经被访问过；在数据库系统中，要快速确定一个记录是否存在。传统的数据结构如哈希表，虽然可以实现快速查询，但在处理大规模数据时，需要消耗大量的内存空间来存储元素及其相关信息，空间成本较高。

总结：

布隆过滤器是一种概率型数据结构，它的特点是高效地插入和查询，能确定某个字符串一定不存在或者可能存在；
布隆过滤器不存储具体数据，所以占用空间小，查询结果存在误差，但是误差可控，同时不支持删除操作；

3.2 位图

位图（Bit - map），又称为位向量（Bit - vector）或比特数组（Bit - array），是一种用二进制位来表示和存储数据的数据结构

原理：位图中的每个二进制位（bit）都可以表示一个特定元素的某种状态，通常用 0 表示该元素不存在或不具有某种属性，用 1 表示该元素存在或具有某种属性。例如，要表示一个包含 10 个元素的集合，就可以创建一个长度为 10 的位图，初始时所有位都设置为 0。当集合中添加元素 3 时，就将位图的第 3 位设置为 1；如果要删除元素 3，就将第 3 位重新设置为 0。
在这里插入图片描述
图中展示了在 C++ 中利用 byte buf[8] 构建 64bit 位图的原理
你可以读一下这个链接->内存知识

3.3 布隆操作

在这里插入图片描述

插入过程：当插入 str1 时，h1(str1)、h2(str1)、h3(str1) 三个哈希函数分别计算出不同的哈希值，这些哈希值对应到位图中的位置，将这些位置的值从 0 置为 1（图中蓝色箭头指向的位置）。插入 str2 时同理，h1(str2)、h2(str2)、h3(str2) 计算的位置（图中红色箭头指向）也被置为 1 。
查询过程：当查询某个元素是否在集合中时，用相同的哈希函数计算该元素对应的位图位置。若这些位置的值都为 1 ，则该元素可能在集合中；只要有一个位置为 0 ，则该元素一定不在集合中。不过由于不同元素哈希值可能重叠（像图中部分箭头指向同一位置），存在误判情况，即元素实际不在集合中，但位图对应位置都为 1 。

哈希函数特性与位图存储：布隆过滤器使用多个哈希函数将元素映射到位图的不同位置。位图大小固定，当插入元素增多，不同元素经哈希函数计算后，映射位置可能重叠。比如有元素 A 和 B，A 先插入，其通过哈希函数计算的位图位置被标记为 1 ；之后插入 B，若 B 的部分哈希位置与 A 重叠，这些位置早已被标记为 1 。

3.4 应用分析

n – 预期布隆过滤器中元素的个数，如上图只有str1和str2 两个元素那么 n=2
p – 假阳率，在0-1之间 0.0000001也可以这个错判率
m – 位图所占空间
k – hash函数的个数

n = ceil(m / (-k / log(1 - exp(log§ / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log§) / log(1 / pow(2, log(2))));
k = round((m / n) * log(2));

网站操作
可以快速算出m k

4 分布式一致性 hash

4.1 背景

在这里插入图片描述

哈希环构建：将整个哈希值空间组织成一个虚拟的圆环，比如哈希函数取值范围为 0 - 2^32 - 1 ，这就构成了哈希环。节点（如服务器）和数据都通过哈希函数映射到这个环上。例如，以服务器的 IP 地址或主机名作为关键字进行哈希，确定其在环上的位置；对数据的键进行哈希，也能定位到环上位置。
数据映射：当需要定位数据时，使用哈希函数对数据的键进行哈希，然后在哈希环上沿顺时针方向找到第一个遇到的节点，该数据就由这个节点负责处理。

4.2 hash 偏移

hash 算法得到的结果是随机的，不能保证服务器节点均匀分布在哈希环上；分布不均匀造成请求访问不均匀，服务器承受的压力不均匀
在这里插入图片描述

4.3虚拟节点

为了解决哈希偏移的问题，增加了虚拟节点的概念；理论上，哈希环上节点数越多，数据分布越均衡。
假设一个分布式存储系统中有三个物理节点，其 IP 地址分别为：
Node A：192.168.1.100
Node B：192.168.1.101
Node C：192.168.1.102
为每个物理节点创建多个虚拟节点，例如为每个节点创建三个虚拟节点，通过对 IP 地址和虚拟节点编号进行组合来标识虚拟节点，如下所示：
对于 Node A：

虚拟节点 A - 1：192.168.1.100 - 1
虚拟节点 A - 2：192.168.1.100 - 2
虚拟节点 A - 3：192.168.1.100 - 3

对于 Node B：

虚拟节点 B - 1：192.168.1.101 - 1
虚拟节点 B - 2：192.168.1.101 - 2
虚拟节点 B - 3：192.168.1.101 - 3

对于 Node C：

虚拟节点 C - 1：192.168.1.102 - 1
虚拟节点 C - 2：192.168.1.102 - 2
虚拟节点 C - 3：192.168.1.102 - 3

使用哈希函数对这些虚拟节点的标识（如上述组合的字符串）进行计算，将它们映射到哈希环上。例如，哈希函数可以是一个简单的取模运算，将虚拟节点的标识转换为一个在 0 到 2^32 - 1 之间的哈希值，从而确定其在哈希环上的位置。

4.4 数据迁移

增加节点

节点哈希计算与定位：对新增节点的标识（如 IP 地址等）进行哈希计算，确定其在哈希环上的位置。
数据迁移：从新增节点在哈希环上的位置开始，沿顺时针方向找到其前一个节点。将该前一个节点中，哈希值落在新增节点与该前一个节点之间的数据，迁移到新增节点上。

节点 A 的哈希值是 0。节点 B 的哈希值是 100。新节点 C 的哈希值是 50。新增节点 C（50）后，需要将节点 B（100）中哈希值落在 (50, 100] 范围内的数据迁移到 C（50）。
节点 A 的负责范围不变（仍负责回绕部分 (100, 0]），节点 B 的负责范围缩小为 (50, 100]，节点 C 负责 (0, 50]。
数据迁移的核心是：仅迁移新增节点与它顺时针下一个节点之间的区间数据，其他节点的负责范围不受影响，从而最小化迁移量。

虚拟节点处理：若系统采用了虚拟节点，为新增物理节点创建对应的虚拟节点，并将虚拟节点映射到哈希环上。虚拟节点的数据迁移方式与上述物理节点类似，即把相关虚拟节点顺时针方向前一虚拟节点到它之间的数据进行迁移。不过，由于虚拟节点数量较多，数据迁移会更分散，能使数据分布更均匀，减少对单个节点的影响。

删除节点

节点移除：将待删除节点从哈希环上移除。
数据迁移：把被删除节点上的数据，全部迁移到其在哈希环上顺时针方向的下一个节点上。例如，节点 B 被删除，那么节点 B 上的数据会被迁移到节点 B 顺时针方向的下一个节点（假设是节点 C）上。
虚拟节点处理：对于要删除的物理节点所对应的虚拟节点，先将这些虚拟节点从哈希环上删除。由于虚拟节点对应的数据可能分散在多个物理节点上，所以每个虚拟节点的数据会根据其在哈希环上的位置，迁移到各自顺时针方向的下一个虚拟节点对应的物理节点上。这样可以避免单个物理节点因数据迁移量过大而出现负载过高的情况，提高系统的稳定性。

目录