余数Hash
最简单、常用的Hash算法。
hash(i) = i mod n
缺点：伸缩性差，使用余数Hash的路由算法，在扩容的时候会造成大量的数据无法正确命中（其实不仅仅是无法命中，那些大量的无法命中的数据还在原缓存中在被移除前占据着内存）。
解决方案为：
（1）在网站访问量低谷，通常是深夜，技术团队加班，扩容、重启服务器
（2）通过模拟请求的方式逐渐预热缓存，使缓存服务器中的数据重新分布
一致性Hash
维基百科定义
一致哈希是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对 K/n个关键字重新映射，其中K是关键字的数量， n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。
原理
一致性Hash算法通过一个叫做一致性Hash环的数据结构实现Key到缓存服务器的Hash映射。
先构造一个长度为232的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 232-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到其Hash值（其分布也为[0, 232-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。
环形Hash空间
把数据通过一定的hash算法处理后映射到环上
现在我们将object1、object2、object3、object4四个对象通过特定的Hash函数计算出对应的key值，然后散列到Hash环上。如下图：
Hash(object1) = key1；
Hash(object2) = key2；
Hash(object3) = key3；
Hash(object4) = key4；
将节点通过hash算法映射到环上
在采用一致性哈希算法的分布式集群中将新的节点加入，其原理是通过使用与对象存储一样的Hash算法将机器也映射到环中（一般情况下对机器的hash计算是采用节点的IP或者机器唯一的别名作为输入值），然后以顺时针的方向计算，将所有对象存储到离自己最近的节点中。
假设现在有NODE1，NODE2，NODE3三台节点，通过Hash算法得到对应的KEY值，映射到环中，其示意图如下：
Hash(NODE1) = KEY1;
Hash(NODE2) = KEY2;
Hash(NODE3) = KEY3;
新的问题：负载不均
解决办法：引入虚拟节点
其工作原理是：将一个物理节点拆分为多个虚拟节点，并且同一个物理节点的虚拟节点尽量均匀分布在Hash环上。
实现
可以采用红黑树实现
注意：
-
String重写的hashCode()方法在一致性Hash算法中没有任何实用价值，要重写。因为通过它计算出来的Hash值只分布在一个很小的范围里。这种重新计算Hash值的算法有很多，比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH(MemCache推荐)等 -
TreeMap,TreeSet是Java中对红黑树的实现。 - 如何添加虚拟节点？要有思路。比如起码要考虑：一个真实结点如何对应成为多个虚拟节点？虚拟节点找到后如何还原为真实结点？一个简单的解决方案如：给每个真实结点后面根据虚拟节点加上后缀再取Hash值，比如”192.168.0.0:111″就把它变成”192.168.0.0:111&&VN0″到”192.168.0.0:111&&VN4″，VN就是Virtual Node的缩写，还原的时候只需要从头截取字符串到”&&”的位置就可以了。
优点
在节点的添加和删除时，一致性哈希算法在保持了单调性的同时，还是数据的迁移达到了最小，这样的算法对分布式集群来说是非常合适的，避免了大量数据迁移，减小了服务器的的压力。
-
节点（机器）的删除
以上面的分布为例，如果NODE2出现故障被删除了，那么按照顺时针迁移的方法，object3将会被迁移到NODE3中，这样仅仅是object3的映射位置发生了变化，其它的对象没有任何的改动。如下图：
节点（机器）的删除 -
节点（机器）的添加
如果往集群中添加一个新的节点NODE4，通过对应的哈希算法得到KEY4，并映射到环中，如下图：
节点（机器）的添加通过按顺时针迁移的规则，那么object2被迁移到了NODE4中，其它对象还保持这原有的存储位置。
引用
一致性Hash算法的深入理解
每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)
一致哈希
