# 一致性哈希

> 一致哈希是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对K/n个关键字重新映射，其中K是关键字的数量，n是槽位的数量。也就是说，当槽位数量发生变化时，绝大多数关键字仍能映射到原来的位置，只有少数关键字需要重新分配。

- ID: m06187
- 分类: system
- 领域: 系统论

## 定义

一种特殊的哈希算法。当哈希表的大小（如服务器数量）发生变化时，只需要重映射极少部分的数据，而不需要重新洗牌所有数据。它解决了分布式系统扩容时的震荡问题。脚手架作用： 平滑扩展的架构。在设计组织架构或规则时，要考虑到未来的“扩容”。好的制度（如一致性哈希）在增加新人或新部门时，对现有系统的干扰是最小的，无需推倒重来。

## 机制

将节点与数据键都映射到一个环形哈希空间，仅当节点增减时，受影响的数据仅重新分配到相邻节点，使扩容/缩容的再平衡代价从 O(N) 降为 O(K/N)。

## 练习

1. 选哈希函数把节点与键映射到环上。2. 键归属到顺时针最近节点。3. 增删节点只迁移落在其区间的键。4. 用虚拟节点平滑负载。

## 脚手架用法

平滑扩展的架构。在设计组织架构或规则时，要考虑到未来的“扩容”。好的制度（如一致性哈希）在增加新人或新部门时，对现有系统的干扰是最小的，无需推倒重来。

[阅读网页](https://thinkingmodels.site/entries/detail/m06187)