什么是哈希

我们先来简单介绍一下什么是哈希。

哈希表

假设我们有一个有限、快速可达的集合，我们暂且把他称之为哈希表，哈希表是根据关键码值key而直接进行访问的数据结构。我们通过把key值映射到表中一个位置来访问key值对应的一条记录（暂且我们说一条key对应一条记录），以加快查找的速度。

哈希函数

哈希表中需要一个映射来使key快速定位到一个位置，这个映射的函数就叫做哈希函数。哈希函数能使一个数据序列的访问过程更加迅速有效，通过哈希函数，数据元素将被更快地定位。

• 同一个key在多次hashcode()也只会得到一个相同结果；
• 雪崩效应：关键字key的1bit变化，会造成hashcode(key)后的因变量 至少半bit的变化；

哈希数组

为了方便下标索引，我们一般将哈希表的底层设计为一个数组结构，数组中的数据类型可任意，每个位置被称为一个槽位。

哈希地址

哈希地址即哈希数组的下标，一般根据哈希算法不同会生产不同长度的哈希地址。通过下标获得数据的过程，被称为索引取数。通过数据获得下标，被称为哈希映射。 我们在实践中一般会把哈希地址转化为有限的哈希数组下标，在hashcode(key)之后取模 mod N，来将哈希后的地址指向一个有限的N位长度的数组集合

哈希冲突

因为哈希地址有长度，同时key的可能性是无限的，所以key与hashcode(key)转化后的结果是无法一对一映射的，必然会出现多个不同的key对应一个结果地址（使用取模的方式hashcode(key) % N来转化哈希地址就更容易产生了），这种不同的输入得到了相同的输出的场景就叫做哈希冲突。

所以哈希冲突在理论上是一定会出现的，不可避免的。在面对哈希冲突时，我们对冲突的发生并不担心，担心的是冲突的概率，概率越高，则会影响我们哈希算法的安全性，让反推更容易。同时冲突概率越高，会影响数组槽位对应的存储结构的复杂性，hashcode(key)后让搜索更加缓慢。

一致性哈希

在分布式系统中，节点的宕机、某个节点加入或者移出集群是常事，这就意味着哈希表的每次扩展和收缩都会导致所有映射分布的重新计算。这个特性在某些场景下是不可接受的。比如分布式的存储系统。

所以我们需探索一种代价更小的哈希方法，使这种节点变更后造成的影响更小。

循环结构（环状结构）

我们使用一个哈希函数，假设这个哈希函数有nbit，那么他可以映射到一个2^n位的哈希表中。同时我们使用mod模式取模，将hashcode(key)可循环映射到一个有限的哈希表上，这样这个哈希表在我们抽象看来就像一个环状结构。

槽位标记

在有了这个环之后，我们将我们有数据的槽位标记上（例如：A、B、C），

滑动寻址

也就是说，对数据进行哈希后，如果映射到槽位不是标记的槽位，就会按顺时针的方向继续寻址，直到找到最近一个标记槽位。

增加新节点的重映射

若为普通哈希，增加一个节点基本所有的数据映射都要重新改变。 但基于一致性哈希的方案，若我们增加一个节点槽位D在B->C之间，则原D->C间的映射依旧会滑动到C，但是B->D之间的映射会修改为映射到D，所以在增加节点前，我们只用将落到B->D间的存量数据重新映射到D即可完成标记槽点的增加，从而减少了节点变更的影响性。

减少节点（节点宕机）的重映射

若我们一个节点突然宕机了，比如说该节点对应槽位为A，则相当于在环中减少了槽位A。这时，原A->B间的映射依旧会滑动到B，但是C->A之间的映射需要修改为映射到B，所以在减少节点后，以前命中C->A间的存量数据需重新建立到B槽位的映射，在节点宕机时也只会影响C->A这一区间内的映射。

一致性哈希也不是完全一致的

从上面可以看出所谓的一致性哈希在面临节点增减后也不是完全一致的，只是在一定程度上减小了影响性，控住了变更成本。

虚拟节点机制（控制分发的平衡性）

说到哈希的平衡性，是指哈希后的结果能在概率上尽可能的分布到所有的节点槽位上去，这样可以使得所有的缓冲空间都得到利用。

但是在节点槽位少，或者节点槽位在环上分布不均匀时，平均映射到各个槽位的概率会不平均，会发生映射倾斜的问题。 面对这个问题，我们引入虚拟节点的概念来解决

虚拟节点是实际节点在哈希的环状空间中的一个克隆，一个实际节点槽位对应了若干个“虚拟节点”槽位，所以将虚拟节点尽可能均匀的分布，滑动寻址在概率上能较均匀的分发至各个节点槽位。

在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。