一致性哈希通过虚拟节点映射实现负载均衡，核心是用MurmurHash3生成均匀哈希值，结合std::map/跳表/sorted vector等结构构建有序环，支持环形回绕查找、权重缩放与高并发优化。
如果您需要在分布式系统中实现负载均衡，而目标是让数据或请求均匀分布到多个后端节点上，同时减少节点增减时的数据迁移量，则一致性哈希是一种被广泛采用的核心技术。以下是基于 C++ 实现高性能一致性哈希算法的具体方法，重点围绕虚拟节点映射机制展开：
一、使用 STL map + MurmurHash3 构建有序哈希环
该方法利用 std::map 的红黑树底层实现自动排序特性，将虚拟节点的哈希值作为 key 存储，value 指向真实节点指针；配合 MurmurHash3 高速非加密哈希函数确保分布均匀性与低碰撞率。
1、引入第三方 MurmurHash3 头文件或内联其实现代码，定义哈希计算函数 hash(const std::string& key) → uint32_t。
2、为每个物理节点生成 100~200 个虚拟节点，命名格式为 "node_id#i"，其中 i 为序号，调用 hash() 计算其哈希值。
立即学习“C++免费学习笔记（深入）”；
3、将每个虚拟节点哈希值作为 key、对应物理节点指针作为 value 插入 std::map
4、当需查找 key 对应节点时，计算 key 的哈希值，调用 map.lower_bound() 获取第一个不小于该值的迭代器，若到达 end() 则取 begin()（环形回绕）。
二、采用跳表（SkipList）替代平衡树提升并发性能
在高并发读写场景下，std::map 的互斥锁粒度较粗，跳表可提供更细粒度的锁控制和更高的平均查询吞吐量，同时保持 O(log n) 时间复杂度与有序性。
1、实现一个线程安全的跳表类 SkipList
2、初始化阶段对每个物理节点循环生成虚拟节点字符串并哈希，调用 insert 插入跳表，key 为哈希值，value 为 Node*。
3、路由查找时调用 findGreaterOrEqual(key_hash)，返回首个 ≥ key_hash 的节点；若无则取 head->next[0]（即最小哈希值节点）。
4、所有插入与查找操作均需保证 哈希值不重复，可通过在冲突时追加随机后缀重试解决。
三、内存优化：使用 sorted vector + 二分查找替代动态结构
适用于节点集合相对静态、查询远多于更新的场景。通过预排序的 std::vector 存储哈希值与节点映射对，并利用 std::lower_bound 进行二分查找，消除指针跳转开销，提高 CPU 缓存命中率。
1、定义结构体 HashEntry { uint32_t hash; Node* node; }，构建 std::vector
2、调用 std::sort 对 vector 排序，确保后续二分查找有效性；排序仅在初始化或节点变更后执行一次。
3、查找时构造临时 HashEntry{hash_val, nullptr}，调用 std::lower_bound(v.begin(), v.end(), temp, cmp) 获取迭代器。
4、若迭代器为 v.end()，则返回 v.front()；否则返回 *iter；比较函数 cmp 必须仅依据 hash 成员进行判断。
四、无锁环形数组 + 双散列定位虚拟节点索引
面向极致性能要求，放弃通用容器，采用固定大小环形数组（如大小为 2^20）配合双散列策略直接定位，避免内存分配与树/跳表遍历开销，适合嵌入式或高频交易系统。
1、分配一块连续内存作为 ring[1
2、对每个物理节点 node，使用主哈希函数 h1(key) = MurmurHash3(key) % ring_size 得到基础槽位；若已被占用，则用次哈希 h2(key) = (MurmurHash3(key + "salt") >> 16) % (ring_size - 1) + 1 计算步长，线性探测直至空位。
3、插入全部虚拟节点后，查找时对请求 key 执行相同双散列流程，直到命中非空 slot 或探测轮数超限（此时触发 fallback 到备用环）。
4、必须保证 环大小为 2 的幂且探测步长与环大小互质，以确保全覆盖所有槽位。
五、支持权重的虚拟节点数量动态缩放
当各物理节点处理能力差异显著时，需按权重比例分配虚拟节点数量，使哈希环上覆盖密度与权重正相关，从而实现加权一致性哈希。
1、为每个 Node 设置 weight 成员（如 CPU 核心数 × 内存 GB 数），归一化为 total_weight 后计算 quota = (weight * virtual_node_base) / total_weight。
2、virtual_node_base 默认设为 100，但最低不少于 10，最高不超过 500，防止极端权重导致节点数溢出或过少。
3、生成虚拟节点时，循环次数由 quota 决定，每轮构造字符串 node_id + "#" + std::to_string(i)，再哈希入环。
4、每次节点增删后必须重新计算 total_weight 并重分配全部虚拟节点，因此该策略仅适用于 低频变更配置 场景。
