更多文章，请关注我的个人博客：www.ahey.net
引言
哈希算法，多应用于多数框架的底层实现，在JAVA中与其相关的有HashMap、HashTable等。
首先抛几个问题
- 都知道Hashmap底层使用了hash（取模）算法，它与一致性hash算法有什么区别呢？
- 在分布式缓存中，hash算法起了很大的作用，它也是上述提到的取模算法吗？
- 取模法与一致性哈希算法有什么区别？
什么是哈希算法
hash即散列，哈希算法又称散列算法，将任意长度的二进制值映射为较短的固定长度的二进制值（哈希值），哈希值是一段数据唯一且极其紧凑的数值表示形式，常用于快速查找和加密算法。
传统取模法（以Hashmap为例）
HashMap底层结构是数组+链表+红黑树。数组相当于一个bucket，在bucket这一层就用到了取模法。
假设数组的长度为n，当一个Node（key-value）加入时，先计算key的hash值，再通过 （n -1）& hash 的位操作，得到bucket的下标。这里的位操作其实就是取模算法 hash % n的优化版。这时候问题来了，由于数组容量必定有限，当需要扩容（新增Node节点）时，Hashmap会rehash（重建hash表），可想而知重建会导致大量的key需要迁移并重新计算下标。 故Hashmap源码中提到了要合理设置初始长度和负载因子，以“内存换性能”的操作来避免rehash。
取模思路如下
假设数组初始长度n = 5，增加结点至n = 6，最终导致全部数据都需进行迁移，改变下标。
换个角度思考，是否可以做到，在扩容的时候尽最大化地减少迁移的操作，并且保证原来的key仍在原来的位置（在分布式缓存系统中，这点尤为重要，否则容易引起缓存雪崩等情况）
一致性哈希算法
引自wiki
一致哈希 是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对K/n 个关键字重新映射，其中K是关键字的数量，n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。
其实一致性哈希算法也是一种取模法，只不过不直接对服务器数量进行取模分发，而是对2^32进行取模，以此解决重新散列的问题。
实现原理大致如下
构造由2^32个点位组成的环形hash空间
将服务器节点映射到hash空间
将存储对象映射到hash空间
将对象沿顺时针转动，碰到的第一个服务器节点，即当前对象应缓存的节点
将上述原理概括成描述一致性哈希算法的规则：环形空间，节点映射，对象映射，顺时针相遇
它目前已经应用于AWS Dynamodb高可用 Nosql数据库、Memcached分布式缓存、Nginx负载均衡等
一致性哈希基于分布式缓存的应用
为什么说一致性哈希是一种特殊的哈希算法，可以借助分布式缓存的例子来说明。
假设现在有三个服务器节点A、B、C，三条待缓存的键值对数据a、b、c。
初始节点
- 将三个服务器节点通过hash(ip地址) % 2^32 取模得到一个整数值（介于0 ~ 2^32），定位到环形空间上
- 将三个缓存对象通过hash(key) % 2^32 取模得到一个整数值（介于0 ~ 2^32），定位到环形空间上
- 将缓存对象沿顺时针“转动”，当第一个遇到的服务器节点，就是缓存对象对应存储的节点
如下图所示，缓存对象a在服务节点A上存储，缓存对象b在服务节点B上存储...
节点故障
- 假设此时节点B出现故障下线了，按照一致性哈希的规则中的“顺时针相遇”，缓存对象b应该与服务节点C相遇，存储位置变动，而其他节点按兵不动，不受影响
新增节点
- 假设此时新增一个节点D，位于A与C之间，如下图，按照一致性哈希的规则中的“顺时针相遇”可知，所有缓存对象无需再次转动
- 假设此时新增一个节点E，位于A与B之间，如下图，按照一致性哈希的规则中的“顺时针相遇”可知，缓存对象b与服务节点E相遇，存储位置变动
hash环倾斜
在描述基于分布式缓存的应用时，看似一切都很理想化。
但是会遇到一种情况，实际服务节点的映射位置可能比较极端，进而造成数据倾斜，这种情况会导致大多数的缓存对象都集中在一个节点，失去了哈希算法存在的意义。
虚拟节点
hash算法无法保证绝对的平衡，一致性哈希算法容易导致数据倾斜，故它又引入了“虚拟节点”，即实际节点在hash空间的复制节点，两者关系为1：n，虚拟节点在hash空间中以hash值排列
总结
一致性哈希算法，相较于常规的取模法，解决了增删节点导致的重新散列的问题，基于“环形空间，节点映射，对象映射，顺时针相遇”的规则，加上虚拟节点的引入，很大程度地解决了分布式系统的心结，故它常用于Nginx负载均衡、Dynamodb分布式数据库等。
