一.什么是hash

百度百科上的定义是：

是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

二.hash函数

hash函数并没有具体的公式，只是一种广义上的思想。最终的目的都是通过一个运算来将输入压缩，常用Hash函数有：

1．直接寻址法。取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）

2． 数字分析法。分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

3． 平方取中法。取关键字平方后的中间几位作为散列地址。

4． 折叠法。将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。

5． 随机数法。选择一随机函数，取关键字作为随机函数的种子生成随机值作为散列地址，通常用于关键字长度不同的场合。

6． 除留余数法。取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生碰撞。

 

三.hash算法

hash算法其实就是通过hash函数运算得到的每个数据的hash值来将数据均匀分布的一个过程。以下用一个列子来讲解：

应用场景：

有三万张图片缓存到三台服务器上，最好这三万张图片均匀缓存到三台服务器上，这样能减小服务器的压力。

 

思路：

用每一个图片的key进行hash计算得到一个值，将这个值与服务器数量取模运算得到一个余数，这个余数就是该图片应该存放的服务器的编号。

当需要查找该图片的时候用key来重复以上过程就可以知道图片存放的位置在哪里。

 

缺陷：如果在存放完成以后，服务器数量改变，以上流程得到的值会改变，无法准确计算出图片的存放位置。也就是说hash算法要求运算的基础值，严格不变！为了应对这种变化，需要采用hash算法的升级版——一致性hash算法。

 

四.一致性hash算法

假设有一个环，这个环是由2的32次方个点组成的，这个环就叫hash环。

为什么是2的32次方，是因为32喂的操作系统一个指针是4字节，一字节8位，也就是

32位。也就是说一个指针指向的内存空间最多能有2的32次方个值

其实这也就是为什么hashMap底层源码中给出的扩容极限容量为2的32次方。

只有落在这个区间才有位置给你存储。

如果新增一台服务器D

可以发现受影响的就只有一小部分，大部分的数据都不会受影响，

查找的时候都可以准确的找到

一致性hash算法的缺点：

hash偏斜，服务器做完hash运算以后映射到hash环上的位置可能不均匀

分布不均匀的直接后果就是命中不均匀，可以明显看到很大几率运算出来的图片存放位置会是A，这样也会造成存储的不均匀。

 

解决hash偏斜的方法就是增加服务器台数。当然如果在不增加实际物理服务器的情况下可以增加虚拟节点来达到解决hash倾斜的问题。

各虚拟节点上的命中虚拟节点的图片分别映射到各自对应的物理节点即可。