图解什么是一致性哈希算法

作者 | LemonCoder

来源 | 后端技术学堂（ID：lemon10240）

很多同学应该都知道什么是哈希函数，在后端面试和开发中会遇到「一致性哈希」，那么什么是一致性哈希呢？名字听起来很厉害的样子，其实原理并不复杂，这篇文章带你彻底搞懂一致性哈希！

进入主题前，先来一场紧张刺激的模拟面试吧。

模拟面试

面试官：看你简历上写参与了一个大型项目，用到了分布式缓存集群，那你说说你们是怎么做缓存负载均衡？

萌新 ：这个我知道，我们用的是轮询方式，第一个key 给第一个存储节点，第二个 key 给第二个，以此类推。

面试官：还有其他解决方案吗？

萌新：可以用哈希函数，把请求打散随机分配到缓存集群内机器。

面试官：考虑过这种哈希方式负载均衡的扩展性和容错性吗？

萌新：...

面试官：回去等通知吧。

以上如有雷同，算你抄我的。

什么是哈希

数据结构中我们学习过哈希表也称为散列表，我们来回顾下散列表的定义。

散列表，是根据键直接访问在指定储存位置数据的数据结构。通过计算一个关于键的函数也称为哈希函数，将所需查询的数据映射到表中一个位置来访问记录，加快查找速度。这个映射函数称做「散列函数」，存放记录的数组称做散列表。

散列函数能使对一个数据序列的访问过程更加迅速有效，是一种空间换时间的算法，通过散列函数数据元素将被更快定位。

下图示意了字符串经过哈希函数映射到哈希表的过程。没错，输入字符串是用脸滚键盘打出来的：）

哈希示意图.png

常见的哈希算法有MD5、CRC 、MurmurHash 等算法，简单介绍一下。

MD5算法

MD5消息摘要算法（MD5 Message-Digest Algorithm），一种被广泛使用的密码散列函数，可以产生出一个128位（16字节）的散列值（hash value），MD5算法将数据（如一段文字）运算变为另一固定长度值，是散列算法的基础原理。由美国密码学家 Ronald Linn Rivest设计，于1992年公开并在 RFC 1321 中被加以规范。

CRC算法

循环冗余校验（Cyclic Redundancy Check）是一种根据网络数据包或电脑文件等数据，产生简短固定位数校验码的一种散列函数，由 W. Wesley Peterson 于1961年发表。生成的数字在传输或者存储之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。由于本函数易于用二进制的电脑硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误，因此获得广泛应用。

MurmurHash

MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。由 Austin Appleby 在2008年发明，并出现了多个变种，与其它流行的哈希函数相比，对于规律性较强的键，MurmurHash的随机分布特征表现更良好。

这个算法已经被很多开源项目使用，比如libstdc++ (4.6版)、Perl、nginx (不早于1.0.1版)、Rubinius、 libmemcached、maatkit、Hadoop等。

常见散列方法

• 直接定址法：取关键字或关键字的某个线性函数值为散列地址，这个线性函数的定义多种多样，没有标准。

• 数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

• 平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的，取的位数由表长决定。

• 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。

• 取模法：取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即 hash(key) = key % p（p