Consistent Hashing

一致性哈希在节点增减时仅迁移 1/n 的键，最小化重新映射，用于分布式缓存与分片。

用途

使节点增删时数据迁移最小化，是分布式存储与缓存的核心技术。

机制

将节点与键都映射到 0-2^32 哈希环上，键顺时针找到第一个节点。节点增删仅影响相邻区间的键。虚拟节点（每节点多哈希点）改善均衡。负载约均匀分布。

用例

分布式缓存（Memcached）
CDN 节点分片
数据库分片（Cassandra）
负载均衡

示例

输入

Node C joins

输出

Only keys in C's adjacent arc migrate

Minimal migration

常见错误

Too few virtual nodes causes uneven load: Use 150+ virtual nodes per node

相关词条

哈希表用哈希函数将键映射到桶数组，平均 O(1) 查找/插入/删除，是最常用的数据结构之一。

布隆过滤器用 k 个哈希函数与位图近似集合成员查询，空间高效但有假阳性率。

Merkle 树是叶为数据哈希、内部节点为子节点哈希的树，可高效验证大数据完整性，用于 Git 与区块链。

参考链接