大家好，我是讯享网，很高兴认识大家。



1.1 的介绍

是一个常用的关联式容器，它存储唯一的元素，这些元素默认情况下按照升序排序。其底层是一种自平衡的二叉搜索树(红黑树)。

• set元素的键值就是实值，实值就是键值。
• set的元素允许插入删除但是不允许修改(具有const属性)。

1.1.1 的模版参数列表

讯享网

• ： 中存储元素的类型。实际存储的是 这样的键值对，键和值相同。
• ：用于比较元素的函数对象，默认使用 进行升序排序。可以通过传入自定义比较器（如 ）改变排序方式。
• ：用于管理元素存储空间的分配器，通常使用 STL 提供的默认分配器 。

1.1.2 常用功能

构造函数：

• ：默认构造函数
• ：利用迭代器范围构造函数。
• ：初始化式列表构造函数。
• ：拷贝构造函数。

成员函数：

• 插入元素：

讯享网

• 删除元素：

• 查找元素：

讯享网

• 边界查找：

• 其他操作：

讯享网

• 遍历元素：

：和set基本相同，不同之处在于：容器中的元素可以重复(依然有序)。

1.2 的介绍

是另一个常用的关联式容器，它存储键值对，其中每个键都是唯一的，并且默认情况下键按升序排序。其底层实现通常是一种自平衡的二叉搜索树（通常是红黑树）。

1.2.1 的模板参数列表

讯享网

• ：键的类型，用于唯一标识一个元素。
• ：值的类型，与键相关联的数据。
• ：用于比较键的比较器，默认使用 进行升序排序(同样可以通过构造模版修改ps：)。
• ：管理元素存储空间的分配器，通常使用STL提供的默认分配器。.

1.2.2 常用功能

构造函数：

• ：默认构造函数。
• ：通过迭代器范围构造。
• ：使用初始化列表构造。
• ：拷贝构造函数。

成员函数：

• 插入函数：

• 原位构造元素：

讯享网

• 删除元素：

• 查找元素：

讯享网

• 其他操作：

• 元素访问：

讯享网

• 遍历元素：

1.3 和的基本区别

1.4 元素访问(重点)

1.4.1 的和

• ：通过键访问对应的值。如果键不存在，则会创建一个新的键值对，并对值进行默认初始化。

  讯享网

  • 插入修改：既可以用于插入新元素，也可以用于修改已有元素。
  • 效率问题：如果仅用于查找，且不希望插入新元素，应使用或，以避免不必要的插入操作。
• 方法：通过键访问对应的值。如果键不存在，则抛出异常。
  • 使用场景：适用于确保键存在的场景，避免隐式插入新元素。
  • 异常处理：使用时需要处理可能抛出的异常。

1.4.2 的元素访问

不支持通过下标运算符访问元素，因为它进存储唯一的键，不关联任何值。元素访问通常通过迭代器或查找函数实现。

讯享网

1.4.3 的底层实现

和set的另一个不同点是map支持/元素访问，的下下标运算符接受一个索引(即一个)，获取于此关键字相关联的值。但是与其他下标预算符不同的是，如果索引不在中，就会为它创建一个元素插入到中，并对值进行初始化。

的底层等价于一下操作：

1. 分析：

底层通过实现下面操作:

• 查找键：
  • 使用 方法尝试插入一个键值对。如果键 已存在，插入操作将失败，并返回指向已有元素的迭代器。
  • 如果键 不存在，则插入新的键值对，并返回指向新元素的迭代器。
• 返回引用：
• 返回一个 ，其中 是指向插入或找到的元素的迭代器。
• 解引用迭代器，得到 。
• 返回 成员的引用，即与键关联的值。

2. 注意：

• 返回值是与键关联的值的引用()，因此修改返回的引用将直接影响中对应的键的值。
• 对于对象，应使用或进行访问。

1.4.4 代码示例

讯享网

这里关键在于理解的含义。让我们来逐步分析：

1. ：方法返回一个，其中成员是一个迭代器，指向插入或找到的元素；成员是一个布尔值，指示是否成功插入了一个新元素。
2. ：这是一个迭代器，指向上面定义的中的一个节点。
3. ：这是通过迭代器访问到键值对中的键的部分。因为节点类型是，所以可以通过方式访问键。
4. ：这是通过迭代器访问到键值对中的值部分。同样的因为节点类型是，所以可以通过方式访问键。

同时在 实现中，迭代器类 中定义了返回指向的指针。因此当我们使用迭代器并调用是，实际上是在访问，而在中的类型是，但在map类中实例化为一个的键值对，因此也就访问到了值的部分。

1.5 完整代码（内含注释）

限于篇幅和笔记的简洁性考量，这里就不直接附上代码，而是给出自己写的相关代码地址：

另外补充：在自定义map类中，有个的内部结构体，定义如下：

讯享网

作用：

的主要目的是从类型的键值对中提取键。它通过重载函数调用运算符来实现这一点，它为提供了一种一致且高效的方法来访问和比较键。

这里作为第三个参数模版传递给了。需要知道如何从存储的元素中提取键，以便正确地比较和查找键。在 的实现中，当插入一个新的键值对时， 会使用 来提取键，并确保键的唯一性。

---

二叉搜索树又称二叉排序树，具有一下性质：

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
• 它的左右子树也都是二叉搜索树。

2.1 二叉搜索树的基本操作

• 插入操作：
  1. 从根节点开始，比较插入值与当前节点的值。
  2. 若插入值小于当前节点，移动到左子树；若大于，移动到右子树。
  3. 重复上述步骤，直到找到一个空的位置，将新节点插入。
• 查找操作：
  1. 从根节点开始，比较目标节点与当前节点的值。
  2. 若相等，查找成功。
  3. 若目标小于当前节点，移动到左子树；若大于，移动到右子树。
  4. 重复上述操作，直到找到目标值或遍历完整颗树。
• 删除操纵：
  1. 查找要删除的节点。
  2. 根据节点的子节点情况，执行不同的删除策略：
     • 节点无子节点：直接删除节点。
     • 节点有一个子节点：用子节点替代节点。
     • 节点有两个子节点：找到节点的中序后继(右子树的最小节点)，用后继节点的值替换当前节点，然后删除后继节点。

2.2 完整代码(内含注释)

---

是一个”加上了额外平衡条件“的二叉搜索树。通过引入额外的平衡条件，确保整颗树的高度为。要求任何节点的左右子树高度相差最多。

3.1 平衡因子

(Balance Factor，BF)：即在构建树的过程中用来记录节点左右子树节点高度差值的数，即。

因此为了使树平衡，平衡因子的取值范围应当是-1、0、1。

• 平衡因子 = 0： 左右子树高度相等。
• 平衡因子 = 1： 右子树比左子树高1；
• 平衡因子 = -1： 左子树比右子树高1；

3.2 不平衡的情况

然而实际使用过程中难免会存在下图情况导致整颗树的高度大于等于2，例如：

由于节点只有插入节点至根节点路径上的各个节点可能改变平衡状态，因此只要调整最深的不平衡节点即可使整颗树重新平衡。

假设这个左右子树不平衡的节点为，由于节点最多拥有两个子节点，而所谓的平衡被破坏意味着X的左右两颗子树的高度相差2，因此我们可以推断出有且仅有一下四种情况：

1. 左左（LL）：插入点在的左子节点的左子树上。
2. 右右（RR）：插入点在的右子节点的右子树上。
3. 左右（LR）：插入点在的左子节点的右子树上。
4. 右左（RL）：插入点在的右子节点的左子树上。

3.3 旋转操作

为了解决平衡被破坏的问题，需要引入旋转的概念，旋转的本质就是调节平衡因子使其在正确的取值范围。

3.3.1 单旋转

插入点所在位置总共有四种情况，但其实又是两两对称分为外侧和内侧，外侧也就是左左和右右的情况，解决方法如出一辙，下图以外侧插入(左左/LL)为例，为了调整平衡状态，我们希望将子树上升一层，子树下降一层。为了实现这一操作 我们可以想象一下将提起来(升为这个小群体的老大)，让低于(成为14的右白虎)，并根据左小右大原则把的右子树挂给到的左侧(这关键 但也很好理解，左小右大嘛)

3.3.2 示例代码

光说不练家把什，上代码！（左旋转，适用于右右情况，即插入点在不平衡子树的右子树的右节点上），右右会了，左左是对称关系如法炮制即可。

讯享网

3.3.3 图解

3.4 双旋转

实际应用场景中我们会发现有些问题一次单旋无法解决问题这就需要用到双旋的概念，有了对单旋的理解双旋就很容易理解了，下图的左右不平衡状态单旋转无法解决这种情况，因为会发现插入后不管对谁单旋转都还是不平衡，唯一的可能是以为新的跟节点 让成为的左节点，成为的有节点，因此我们可以先对做左旋，再对做右旋以此达到目的。

3.4.1 示例代码

先右旋转，再左旋转，适用于RL情况：

一个小技巧判断是单旋问题还是双旋问题：不平衡节点到插入点之前的连线->如果是直线就是单旋，如果是折线就是双旋。

3.5 完整代码(内含注释)

---

之外，另一个运用颇为广泛的的平衡二叉树是，满足二叉树的同时还有以下规则：

1. 满足平衡二叉树(左小右大)。
2. 根节点和叶子节点()是黑色。
3. 如果一个节点是红色的则它的两个孩子节点必须是黑色的，即不存在两个连续红色节点。
4. 任一节点到叶子节点()的任何路径，所含的黑色节点数必须相同。

由于红黑树的性质使得它最长的路径()绝不会超过最短路径()的两倍。

理论上来说红黑树性能不如，但是由于当今PC硬件的性能提升，这点性能上的差距已经非常小了，而之所以红黑树比应用更为广泛的原因是因为：同样的插入删除操作红黑树要比效率高，且旋转更少，控制实现相对简单。因为AVL-tree更严格的平衡其实是通过频繁的旋转达到的。其次就是红黑树在实现上更容易控制。由相较而言：AVL树查询更高效，维护严格平衡，频繁旋转而红黑树插入删除更高效。

4.1 插入

红黑树的插入默认是红色，然后再根据树的情况是否做调节。这是因为如果默认是黑色有极大概率会违反规则需要考虑的因素和影响更大，而默认红色会有概率无需调整。

插入节点使得红黑树的性质遭到破坏此时需要根据下面三种情况做调整：

• 插入点是根节点：
• 插入点的叔叔节点是红色：
• 插入点的叔叔节点是黑色：

4.2 插入流程图*

4.3 插入完整代码

为方便理解学习，下面代码是原始版本，之后链接中完整代码再做优化：

讯享网

4.4 完整代码(内含注释)

---

当向该结构中:

• 插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
• 搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable/散列表).

注意：例如在集合 {4, 2, 6, 9999} 这种数据分布不均匀的情况，那么给每个值的映射位置就可能会造成巨大的空间浪费。

5.1 哈希函数

哈希函数是一种将输入(字符或数字)转换为固定长度值的算法。这个固定长度值通常用来作为哈希表的索引，以便在数据存储和检索时实现高效的查找操作。

一个解决方法是除留余数法：不再给每个值映射一个位置，而是在限定大小的空间中将我们的值映射进去。

哈希函数表现为：

其中capacity默认设置为10，这样简单也方便取模运算。

然而这又会带来一个问题：不同的值可能会映射到相同的位置上去，导致哈希冲突，哈希冲突越多对整体而言效率就越低。

那么如何解决哈希冲突呢？

5.2 负载因子

负载因子：是哈希表中元素个数与表大小的比率，定义为：。

即闭散列表中的元素越接近满的状态，冲突的概率就越大，效率也就也低。因此提出负载因子的概念。负载因子越接近，表示哈希表越满，冲突的概率越高，效率越低。因此一般情况闭散列的哈希表中，负载因子到就开始增容是比较合理的。

一般情况下，负载因子越小，冲突概率就越低。但是如果负载因子控制的太小，会导致大量空间的浪费(如：负载因子设为0.3，那就意味着总是会有70%的空间空着)，因此可以看出负载因子就是一种空间换时间的思路。

5.3 哈希冲突的解决

哈希冲突是指多个关键码经过哈希函数计算后映射到同一个位置。常见的冲突解决方法包括：

5.3.1 闭散列(开放地址法)

在闭散列中，当冲突时就按照某种规则再找下一个空位置（抢占式）

• 线性探测：紧接着往后找（），直到找到下一个空位。线性探测有个弊端就是可能会导致连续的冲突(例如：只插入9、19、29、39…会导致冲突区域集中)，从而降低查找效率，平均插入成本的成长幅度远高于负载因子的成长幅度。
• 二次探测：主要是用来缓解冲突区域集中的问题，按照平方跳跃（）着往后找，直到找到空位置，即根据公式：。这种方法减少了冲突区域的集中，提升了插入和查找的均匀性。

示例：

ps.(i为插入值的索引位置)，下面文字方式对上图示例加以解释(暂时不考虑插入满的情况)：

分别以线性探测和二次探测的方式插入{89, 18, 49, 58, 9, 69}

线性探测：

• 插入18：h(18) = 18%10=8;
• 插入89：h(89) = 89%10=9;
• 插入49：取模后等于9，但9已经被占了就找到下一个没有被占领的地方;
• 后面插入的同上，没空就往后排。

二次探测：

• 插入18…;插入89…;
• 插入49：发现位置9被占用，进行二次探测：
  • i=(9+1^2)%10=0，0没被占 插入。
• 插入58：位置8被占了，进行二次探测：
  • i=(8+1^2)%10=9，被占了 继续。
  • i=(8+2^2)%10=2，2没被占 插入。
• 后面插入的同上，函数映射位置被占就进行二次探测。

下面介绍闭散列的插入查找删除操作，但再次之前还有引入元素状态概念

元素状态

哈希表中的元素状态（、、）的设计主要是为了处理插入、查找和删除操作中的特殊情况和冲突。这种状态管理是开放地址法（如二次探测法）的一部分，用于解决哈希冲突。下面解释每种状态的作用：

EMPTY：

• 表示哈希表中该位置从未被使用过。
• 当插入新元素时，如果找到一个状态为 的位置，就可以安全地插入新元素。
• 查找元素时，如果遇到一个状态为 的位置，表示该元素不存在于哈希表中，因为它从未被占用过。

EXISTS：

• 表示该位置当前存储着一个有效的元素。
• 插入新元素时，如果找到一个状态为 的位置，并且键相同，可以更新该位置的值；如果键不同，则需要继续探测下一个位置（解决冲突）。
• 查找元素时，如果找到一个状态为 的位置，并且键匹配，就找到了目标元素。

DELETE：

• 表示该位置之前存储过一个元素，但该元素已被删除。
• 插入新元素时，如果找到一个状态为 的位置，可以安全地插入新元素。
• 查找元素时，如果遇到一个状态为 的位置，表示这个位置曾经被使用过，但现在已被删除。查找不能停止，需要继续探测下一个位置。

ps.那为什么还要判断删除状态呢？那是因为hash采用惰性删除(只是对删除位置进行标记)，当您删除一个元素时，通常不会真正从哈希表中移除它，而是将其标记为已删除（例如，设置为 状态）。这是因为，如果一个位置被完全清空，它可能会影响到其他元素的探测路径。特别是当两个或多个元素的哈希值相同时，它们可能会被放置在同一位置附近，或者它们的探测路径可能重叠。

例如插入1和11，如在查找11之前把1删了，那么去找11的哈希值“1”时就发现找不到了，此时无法以更优的性能去知道11究竟是否存在，而将删除元素定义为就知道后面可能还会有哈希值相同的元素，也就方便继续探测。

5.2.2 开散列/拉链法(哈希桶)

我们可以发现上述的闭散列也并非是一个好的解决办法，因为当每次插入发现元素的哈希索引被占用都必然会抢占式的占用其他元素的索引位置，从而不断的冲突，没完没了，整体效率偏低，不能作为最终解决方案。

进而引出哈希桶的概念：

开散列法又称链地址池(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合成为一个桶，各个桶中的元素通过一个单链表链接起来，各个链表的头结点存储在哈希表中。

从上图可以看出，开散列每个桶放的都是发生哈希冲突的元素。

完整代码(基础版)：

5.4 完整代码(内含注释)

---

6.1 位图()

是在位图上的应用，主要用于在大规模数据中高效查找和统计。

位图的概念：位图是一中非常紧凑的数据结构，它使用二进制位来表示集合中的元素。每个元素对应一个位，如果该元素存在于集合中，则对应的位设置为；否则为。从而节省了大量的内存空间。一般用来解决在海量数据中查找统计。

注意：的下标编号与通常习惯恰好相反：下标法中最大的字符(最右字符)用来初始化中的地位(下标为的二进制位)。

6.1.1 代码实现

讯享网

应用场景：例如，【腾讯】面试题：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。此时使用位图存储只需要空间即可快速判断。

6.2 布隆过滤器()

一种紧凑型的比较巧妙的概率型数据结构，特点是高效的插入和查询，其主旨是采用一个很长的二进制数组，通过一系列的函数，将一个数据映射到位图结构中，从而达到确定该数据是否存在的目的。此方法不仅可以提升查询效率也可以节省大量的内存空间。

下面是位图与布隆过滤器的对比：

6.2.1 创建与使用

通过图文的方式介绍布隆过滤器的创建于使用：

假设场景：商城中有1000个商品，商品编号0~1000，针对这个场景模拟一个二进制数组，其每个位的初识值都是。那么这个数组该如何使用呢？布隆过滤器在初始化的时候，实际上就是对每个商品编号进行若干次的来确定它们的位置。

例如编号1：我们对其进行三次哈希(所谓哈希就是将数据通过特定的哈希函数转换确定一个具体的位置)，比如当对编号1进行哈希时，它会定位到二进制数组的第2位上，并将其数值从0改为1；那函数它定位到索引值为5的位置，并将0改为1；函数定位到索引为99的位置上，将其从0改为1。

之后是2号商品，经过三轮哈希后分别定位到索引为 1、3、98号位置上，原始数据中1号因为刚才已经变成了1，现在它不变，而3号位和98号位原始数据从0变为1。这里衍生出一个哈希新的规则：

如果在哈希后原始位它是0的话，将其从0变为1，如果本身这一位就是1的话，则保持不变。(这点很重要)

1号2号处理完成之后，3~1000号如法炮制。

全部处理完成之后作为布隆过滤器存储在我们的计算机中，那么该如何使用呢？

6.2.2 判断与使用

我们先看一个已存在的，比如此时某一个用户要查询858号商品数据，那么布隆过滤器按照原始的三个哈希分别定位到了1 5和98号位，当每一个哈希位的数值都是1的时候，则代表对应的编号它是存在的。

那下面我们再看一个不存在的情况，例如这里要查询8888。对于8888这个数值经过三次哈希以后，定位到了3、6和100这三个位置，此时索引为100的数值是0。在多次哈希时，有任何一个位为0，则代表这个数据是不存在的。

简单总结一下，如果布隆过滤器所有哈希位的值都是的话，则代表这个数据(注意我的用词它是可能存在)，但是如果某一位的数值是的话它是的。在布隆过滤器设计之初，它就不是一个精确的判断，因为布隆过滤器存在误判的情况。

那下面我们看一个误判情况，比如现在我要查询8889的情况，经过三次哈希，正好每一位上都是1。尽管在数据库中8889这个商品是不存在的，但是在布隆过滤器中，它会被判定为存在，这是这在布隆过滤器中会出现的小概率的误判情况。

那如何减少误判的产生呢？其实方法有两个，

1. 增加二进制位数，在原始情况下，我们设置索引位到达了100，但是如果我们把它放大1万倍，到达了100万，是不是哈希以后的数据会变得更加的分散，那出现重复的情况就会更小，这是第一种方式。
2. 增加哈希的次数，其实每一次哈希处理都是在增加这个数据的特征，特征越多，出现误判的概率就越小。现在我们是做了3次哈希，如果做10次哈希它出现的概率就会小非常非常多。但是在这个过程中，代价便是CPU需要进行更多的运算，会让布隆过滤器的性能有所降低。

一个延伸的小问题:假如布隆过滤器在初始化以后对应的商品被删除了该怎么办呢？

这是一个布隆过滤器的难点，因为布隆过滤器某一位的二进制数据可能被多个编号的哈希来进行引用，比如说布隆过滤器中二号位是1，但是它可能被3、5、100、1000这四个商品编号同时引用，这里是不允许直接对布隆过滤器某一位进行删除的，否则数据就乱了。那怎么办呢？在实际应用中有两种常见的解决方案：

第一种是定时异步重建布隆过滤器，比如说每过4个小时，在额外的一台服务器上异步的去执行一个任务调度，来重新生成布隆过滤器，替换掉已有的布隆过滤器。而另外一种做法叫做计数布隆过滤器，在标准的布隆过滤器下，是无法得知当前某一位它是被哪些具体数据进行了引用。但是计数布隆过。滤器，它是在这一位上额外了附加的计数信息，表达出该位被几个数据进行了引用。

6.2.3 代码实现

---

6.3 海量数据面试题

6.3.1 哈希切割

1. 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
   • 将log文件分割成多个小文件（如100M）。
   • 对每个小文件进行单独处理，使用哈希表记录每个IP的出现次数。
   • 合并所有小文件的结果，统计每个IP的总出现次数，找到出现次数最多的IP。
2. 与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？
   • 类似于上述步骤，先统计每个IP的出现次数，然后使用小顶堆（min-heap）维护Top K的IP。
   • 使用优先队列（priority_queue）实现小顶堆。
   • 每次统计时，若出现次数超过当前堆顶，则替换堆顶，保持堆的大小为K。

6.3.2 位图应用

1. 给定100亿个整数，设计算法找到只出现一次的整数？
   • 使用位图存储整数的出现情况，使用第二个位图记录重复的整数。
   • 遍历所有整数，设置对应的位，若再次出现则标记为重复。
   • 最后遍历位图，找出未标记的位即为只出现一次的整数。
2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
   • 读取第一个文件中的所有整数并建立位图。
   • 遍历第二个文件，检查位图中对应的位，记录交集。
3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。
   • 使用两个位图，一个用于记录出现次数为1的整数，另一个记录出现次数为2的整数。
   • 遍历文件，更新位图状态，最后取出两个位图中标记为1的整数

6.3.3 布隆过滤器

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
   • 精确算法：使用哈希表存储第一个文件的所有整数，然后遍历第二个文件，检查每个整数是否在哈希表中。
   • 近似算法：使用布隆过滤器存储第一个文件的所有整数，然后遍历第二个文件，检查每个整数在布隆过滤器中是否可能存在。
2. 如何扩展BloomFilter使得它支持删除元素的操作？
   • 使用计数布隆过滤器，每个哈希位置存储一个计数值，而不是一个位。
   • 插入时增加计数，删除时减少计数，当计数为0时认为该元素已被删除。

6.4 一致性哈希问题

一致性哈希是一种用于分布式系统中数据分配和负载均衡的方法。它的主要优点在于能有效减少节点变动时对已有数据的影响，降低系统的重分配成本。

6.4.1 一致性哈希的背景

在分布式系统中，数据往往被分散存储在多个节点上。随着系统的扩展（添加或移除节点），如何高效地管理数据的分布成为一个重要问题。传统的哈希方法在节点变化时可能导致大量数据重新分配，造成性能瓶颈。

6.4.2 基本概念

一致性哈希的核心思想是将整个哈希空间视为一个圆环（或环形哈希空间），而节点和数据都被映射到这个环上。其基本步骤如下：

• 哈希空间：定义一个哈希值的范围，通常是一个大整数（例如0到2^32-1）。
• 节点映射：将每个节点通过哈希函数映射到这个哈希空间的某个点。
• 数据映射：同样地，数据对象（如用户请求或存储的文件）也通过哈希函数映射到环上的某个点。
• 数据存储：每个数据对象存储在顺时针方向上第一个遇到的节点。

6.4.3 节点变动的影响

添加节点：当一个新节点加入时，它会接管顺时针方向上某些数据对象，这意味着只有这些对象需要重新分配，其他对象保持不变。

移除节点：当节点移除时，原本由该节点存储的数据会转移到顺时针方向上的下一个节点。

6.4.4 虚拟节点

为了进一步提高负载均衡，一致性哈希通常会引入虚拟节点的概念。每个实际节点在哈希环上对应多个虚拟节点。这样做的好处包括：

• 减少热点：通过增加虚拟节点，能够更均匀地分布数据，避免某些节点负载过重。
• 平滑数据分布：即使在节点数目较少时，虚拟节点也能帮助实现较为均匀的数据分布。

6.4.5 应用场景

一致性哈希广泛应用于分布式缓存系统（如Redis）、分布式存储（如Amazon DynamoDB）、CDN（内容分发网络）等场景，能够有效应对大规模数据存储和访问中的节点管理问题。