Hash 大家都知道，把某个要存储的内容的索引 key 通过某个规则计算一下，算出来一个值，这个值往往范围比原来小，且概率意义上不会冲突。
由于 Hash 计算复杂度往往比查找要快，被大量应用到各种大规模的系统中，特别是分布式系统。具体实践中有几个典型的问题。
问题来源
一致性 Hash 讨论地已经很多，基本故事就是分布式存储系统中，通过 Hash 来决定内容存到哪个节点上。
典型的比如 cache 系统，后面放若干节点，查找某个 key，hash 到某个节点，再进一步检索。
最简单的自然是按照节点数量取个模，理想状态下不会有啥问题。
但是如果发生如下情况，就无法正常工作了。 加节点（一般是有计划的） 减节点（可能突然故障，无法预知）
所以提出了一致性 hash，即考虑如下四个方面的算法： 平衡性(Balance)：哈希结果尽可能分布到所有的节点，这样可以使得所有的节点都得到利用； 单调性(Monotonicity)：加入新的节点后，已经分配节点的 hash 结果 被映射到原有的或者新的节点上去，而不会被映射到其他节点； 分散性(Spread)：同样内容尽量避免 hash 到不同节点； 负载(Load)：不同内容避免 hash 到同样节点。
简单的说，就是有一个算法，首先分配尽量均匀，其次，当节点个数变化的时候，尽量维持原来内容的映射，并进行局部调整。
能满足的算法有很多，这里介绍两个比较经典的。
基于环的实现
该算法最初于 1997 年在论文 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web 中提出。算法复杂度为 O(log(n))。
主要设计思想为：构造一个环（顺序标上编号比如
0 ~ 2^32-1），将已有节点编号并分配到这个环上，分割环为不同的段。
对每个内容，hash 后是一个独一无二的数字，这个数字肯定会落入某个段上，按照固定方向往前找到的第一个节点编号即为要分配到的节点。
考虑两个相邻的节点 A 和 C，如果要在中间添加一个节点 B，那么 AB 段上内容会从 C 节点重新分配到 B 节点。反之，如果删除掉 B 节点，那么 AB 段上内容会再次分配到 C 节点上。
这种算法很好的满足性质 2-4，唯独平衡性没有解决。即当节点个数不多的时候，内容可能会集中在某些段，划分到部分节点上。要解决这个问题也很简单，把一个节点虚拟为多个虚节点，提高整体节点个数，然后再分散放到环上。这样就提高了平衡性。
基于概率转移的实现
该算法最初于 2014 年在论文 A Fast, Minimal Memory, Consistent Hash Algorithm 中由 Google 工程师 John Lamping 和 Eric Veach 提出。算法复杂度为 O(log(n))。
主要设计思想为：假设原先有 n 个节点，新加上一个节点后，每个 key 都有 1/n+1 的概率转移到新的节点上，n/n+1 的概率留在原先分配的节点。
举个例子，原先有 1 个节点，再加一个节点，那么已有内容有 1/2 的概率跳转到到第二个节点。原先有 2 个节点（每个里面有 1/2 的内容），再加一个节点，则已分配内容应该有 1/3 的概率转移到新的节点。
一个简单的实现代码为：
int ch(int key, int num_buckets) { random.seed(key) ; int b = 0; // This will track ch(key, j +1) . for (int j = 1; j < num_buckets; j++) { if (random.next() < 1.0/(j+1)) b = j ; } return b; }
即根据 key 生成 num_buckets-1 个（0~1.0）的伪随机数，依次检查随机数序列：
- 第一个随机数 <1/2，则放第二个节点；
- 第二个随机数 <1/3，则放第三个节点；
- ...
注意伪装随机数序列由 key 唯一确定。意味着同样的内容在多次分配中，分配结果将是一致的。
另外，可以计算出如果当前分配为 b，下一个结果 j >= i 的概率（即 b+1 到 i-1 的过程都不发生跳变）
P(j>=i) = (b+1)/i
最终优化为如下代码：
int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) { int64_t b = -1, j = 0; while (j < num_buckets) { b = j; key = key * 2862933555777941757ULL + 1; j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1)); } return b; }
这个算法依赖于伪随机算法的输出，特点有： 分布均匀性由伪随机算法决定，而跟 key 自身均匀性无关，实践均匀性远好于基于环的算法； 不需要对 key 进行计算，复杂度低，实践计算时间也比基于环的算法好。
算法没解决的问题：当中间减掉节点的时候，序号会发生变化，变为 0...n-1。因此需要在外面维护一个映射关系，动态映射到原先的节点上。
