什么是Hash函数
hash函数，一般翻译做散列或者直接音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。
什么是Hash冲突
如果两个关键字通过hash函数得到的值是一样的，就是hash冲突。
什么是Hash表（散列表）
根据散列函数和冲突处理将一组关键字分配在连续的地址空间内，并以散列值记录在表中的存储位置，这种表就是散列表。
常见的Hash算法：
- 直接寻址法
取关键字或关键字的某个线性函数值为散列地址。即H（key）=key或H（key） = a?key + b，其中a和b为常数,?代表运算符号（这种散列函数叫做自身函数）
- 数字分析法
分析数字的规律，利用数据的特点来构造冲突几率较低的散列地址。例如人的生日，前面的年很容易重复，用月和日构建散列表冲突的几率会明显降低。
- 折叠法
将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
- 平方取中法
取关键字平方后的中间几位作为散列地址。
- 随机数法
选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。
- 除留余数法
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H（key） = key MOD p， p《=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
现在来思考一下这样一道题：
- 题目描述：
提供一组数据 1,5,7,6,3,4,8，对这组数据进行存储，然后给定一个数num，请你判断num是否存在刚才的数据集中?
- 顺序查找法
最容易想到的方法就是遍历数据，在遍历的过程中比较当前元素是否等于数num,等于则存在，如果遍历结束也没有找到和num相等的元素，则不存在. 这种方法就是顺序查找法，时间复杂度O(n).
arr = new int[]{1,5,7,6,3,4,8};
for (int m : arr) {
if (m == num) {
return "num存在于数据集中"
}
}
return "num不存在于数据集中"
- 二分查找法
除此之外，还可以对数据进行排序，然后进行则半查询（每次比较中间数据和num的大小），也就是二分查找法，时间复杂度O(log(n)).
那么是否存在一种方法，时间复杂度比上面的两种方法更低呢，也即是，是否存在一种时间复杂度为O(1)的方法，可以让我们直接判断出num在数据中是否存在. -
直接寻址法
看下面这个数组，可以看出来，这个该数组中索引和索引所在元素是相等的，如果我们要判断数num是否在数组中，只需要判断arr[num]是否等于空就行了，这就是直接寻址法。利用了数组随机索引的特性，时间复杂度O(1).
这种方法可以用来解决一些特定问题，例如：限制服务器内存只有100m,给你全国人的年龄文件（一个人的年龄占一行），求出每个年龄都有多少人。
全国超过10亿人的年龄数据，肯定是超过100m的，直接加载到内存是不行的，我们就可以初始化一个长度为200的数组nums（最大年龄不可能超过200），读取文件每次取出一个人的年龄age，nums[age]++;最后输出数组即可。
不过这种方式的缺点也很明显，就是最大和最小数之间的差不能过大，例如给定10个随机数，范围是0到1亿之间，还使用这种方式，需要创建一个初始长度1亿的数组，严重的浪费空间。 - 除留余数法
有什么方法可以解决这种最大最小数差距过大的情况吗，例如数据（1,3,4,5,10002）.如果使用直接寻址法就需要创建一个长度为10002的数组。这种情况下，我们可以对数据进行取模，例如上面数据个数5，1 mod 5 = 1,3 mod 5 = 3, 4 mod 5 = 4, 5 mod 5 = 0, 10002 mod 5 = 2; 也就是（1，3，4，0，2）这时候我们只需要创建一个长度为5的数组nums,然后用nums[m mod 5] = m,存放数据即可[5, 1, 10002, 3, 4]。
现在再来对数据（1,3,4,5,10003）使用留余数法，先进行取模运算，1 mod 5 = 1, 3 mod 5 = 3, 4 mod 5 = 4, 5 mod 5 = 0, 10003 mod 5 = 3. （1， 3， 4， 0， 3），可以看到3和10003取模的结果都是3，上面对数据求模 (数据%空间位置数) 他就是一个hash算法，只不过这是一种比较普通又简单的hash 算法。这种情况就称之为hash冲突。
hash冲突的解决方法
- 开放寻址法
所有的元素都存放在散列表里，每个表项或包含动态集合的一个元素或者NIL。当查找某个元素时，要系统的检查所有表项，直到找到所有的元素或者最终查明元素不在表中
所有的元素都存放在散列表里，每个表项或包含动态集合的一个元素或者NIL。当查找某个元素时，要系统的检查所有表项，直到找到所有的元素或者最终查明元素不在表中
简单来说就是3 mod 5 = 3,把数组nums的3号坑位占了，当10003 mod 5 = 3,来到3号坑位存放数据时，发现该坑位已经被使用，就往后面找还没有被占的坑位。
- 拉链法
把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0..m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。
简单来说就是3 mod 5 = 3把nums的3号坑位占用了，10003 mod 5 = 3,来到3号坑位存放数据时，发现该坑位已经被使用,也不往后面找了，直接和数据3共有这个坑位，HashMap就是使用这种方式解决的hash冲突.
Hash算法的应用场景
Hash算法在分布式中间件中得到了广泛的应用，例如集群模式redis的请求路由策略（16384个槽位），ShardingSphere分库分表键的路由策略，nginx的负载均衡策略等。
主要应用场景主要分两个
负载均衡
例如nginx的ip_hash,使用ip_hash可以保证来自同一客户端的请求由固定的服务器处理，避免了分布式环境下session的共享问题，实现了会话粘滞。分布式存储
例如redis请求路由策略，Redis集群将所有数据划分为 16384 个 slots(槽位)，每个节点负责其中一部分槽位。集群默认会对 key 值使用 crc16 算法进行 hash 得到一个整数值，然后用这个整数值对 16384 进行取模来得到具体 槽位。HASH_SLOT = CRC16(key) mod 16384
普通Hash算法中存在的问题
我们来看下nginx以ip_hash作为负载均衡策略时，如果服务器宕机或者扩容场景下会出现什么情况可以看出来，无论是扩容还是缩容，因为服务器数量变化，都需要对所有ip进行rehash,3台服务器时，由server1对客户端10.13.22.10提供服务，扩容之后由server2提供服务。扩容缩容之后提供对同一客户端提供服务的服务器发生了变化，并且这种变化的范围是不可控的，甚至可能rehash之后所有客户端都路由到其新的目标服务器处理。
如果在真实生产情况下，后台服务器很多台，客户端也有很多，那么影响是很大的，缩容和扩容都会存在这样的问题，大量用户的请求会被路由到其他的目标服务器处理，用户在原来服务器中的会话都会丢失。
一致性Hash算法
一致性Hash算法在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点（Hot Spot）问题，初衷和CARP十分相似。一致性Hash修正了CARP使用的简单哈希算法带来的问题，使得分布式哈希（DHT）可以在P2P环境中真正得到应用。
一致性Hash算法的实现方法
和普通hash不同的地方在于，一致性hash定义了一个hash环的概念，hash环可以看作是一个由0～（2^32) - 1个元素首尾相连组成的圆环。再通过hash算法将数据处理后映射到环上。
假如现在我们有三台服务器：server0，server1，server2，五个客户端：client0，client1,client2,client3,client4,client5
现在对server0,server1,server2三台服务器ip进行Hash函数运算得到指定的key，再散列到hash环上。
再对客户端进行hash运算，求出key值散列到hash环。
散列到hash环上的客户端，客户端的请求由该客户端顺时针寻找到的第一个服务器负责处理。
例如图中client1,client0,client3的请求由server2处理，cilent4的请求由server1处理，client2的请求由server0处理。
服务器扩容与缩容
普通hash取模算法在服务器增加或者减少的时候，会导致大量客户端路由到新的目标服务器，导致用户在原来服务器中的会话都会丢失或者大量数据需要迁移等问题。
在一致性hash增加或者删除服务器节点又是怎样的呢。
-
服务器扩容（增加节点）
增加server3节点
从图中可以看出来，扩容之后顺时针寻找路由服务器，只有client1请求服务器变成了server3，其他都没有变化。
-
服务缩容（删除节点）
服务缩容
当服务server0因为故障宕机之后，根据顺时针规则，只有client2的目标服务器由server0变为了server1，其他客户端服务器的关系都没有发生变化。
从上面的分析可以看出来，一致性hash在服务器扩容时候，只会影响新增节点hash环顺时针下第一个server的客户端数据，缩容的时候，只会影响原本由宕机服务器处理的数据。
虚拟节点
从图中我们可以发现一个问题，路由到server1的客户端只有client2，其他客户端请求全部路由到了server2服务器导致负载不均衡。针对这种情况，一致性hash中引入了虚拟节点。
“虚拟节点”（ virtual node ）是实际节点（机器）在 hash 空间的复制品（ replica ），一实际个节点（机器）对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以hash值排列。
以上图为例，为server1和server2创建2个虚拟节点之后再进行映射，这里我们将原服务器的ip加上#1，#2在进行hash运算，求出key,散列到hash环。
从图中可以看到，4个节点分别散列到了环的各个位置（如果还是散列不均匀，可以创建更多的虚拟节点），实际工作中，通过虚拟节点-实际节点的映射关系，将客户端请求交给实际服务器处理，例如根据顺时针规则，client1的请求由server2#2处理，server2#2属于server2的虚拟节点，所以client1的请求由server2处理。
实现一致性hash
/**
* @author xialu
* @version 1.0
* @date 2021/7/26 8:25 下午
*/
public class ConsistentHashWithVirtual {
public static void main(String[] args) {
/**
* 服务器id
*/
String[] serviceIds = new String[]{"10.55.12.31", "10.19.12.32", "10.11.22.33"};
SortedMap<Integer, String> map = new TreeMap<>();
/**
* 虚拟节点个数.
*/
int virtualCount = 3;
/**
* 构建虚拟节点
*/
for (String serviceId : serviceIds) {
for (int i = 1; i <= virtualCount; i++) {
String virtualId = serviceId + "#" + i;
int index = Math.abs(virtualId.hashCode());
map.put(index, "由虚拟节点:" + virtualId + " 映射到服务器: " + serviceId);
}
}
String[] clientIds = new String[]{"13.161.12.01", "60.111.12.12", "109.11.12.23", "9.1.2.23", "130.220.985.101"};
for (String clientId : clientIds) {
int index = Math.abs(clientId.hashCode());
SortedMap<Integer, String> tailMap = map.tailMap(index);
if (tailMap.isEmpty()) {
System.out.println("客户端：" + clientId + " 被路由到服务器：" + map.get(map.firstKey()));
} else {
Integer firstKey = tailMap.firstKey();
System.out.println("客户端：" + clientId + " 被路由到服务器：" + tailMap.get(firstKey));
}
}
}
}
