散列算法（Hash Algorithm），又称哈希算法，杂凑算法，是一种从任意文件中创造小的数字「指纹」的方法。也可以理解为空间映射函数，是从一个非常大的取值空间映射到一个非常小的取值空间，由于不是一对一的映射，Hash 函数转换后不可逆，意思是不可能通过逆操作和 Hash 值还原出原始的值。在互联网环境中有非对称加密、文件签名、Hash表寻址算法等应用。
Hash算法类型
直接寻址法：按照该值作为三列地址进行查找。
除留余数法（数据取模法）：对该值按照散列表的长度来取余。
处理Hash冲突时的方法：
开放寻址法：冲突后向前或者向后寻找空位作为当前地址。
再散列法：准备多个散列函数，冲突后使用其他散列函数计算。
拉链法：冲突后，将冲突的数据放到一个链表中。
Hash算法在分布式环境中的应用
请求的负载均衡（如nginx的ip_hash策略）
Nginx负载均衡的经典应用就是通过ip地址或者sessionid进行计算哈希值，哈希值与服务器数量进行取模运算，得到的值就是当前请求应该被路由到的服务器编号，如此，同一个客户端ip发送过来的请求就可以路由到同一个目标服务器，实现会话粘滞。
如果不使用hash算法，就需要非常维护非常大的映射表，造成内存浪费，且服务器上下线后不利于维护。
分布式存储
比如Redis集群模式下，数据应该存储在哪个redis应用里呢？通过Hash算法就可以解决这个问题。
普通HASH算法带来的数据迁移问题
在普通HASH算法下，，如果hash表扩容/缩容，所有的数据均需要重新计算一遍来确定寻址位置。在大量数据的环境下，这会带来很多问题。比如Nginx下的ip_hash负载均衡策略，它的目的是将同一个客户端的请求路由到同一台服务器上，当服务器扩容或者缩容时，使用普通hash算法则使得所有客户端重新计算路由的服务器编号，大量的客户端session失效，这在互联网环境下是难以接受的。
一致性HASH算法
有一条直线，直线开头和结尾分别定为为1和2的32次方减1，这相当于一个地址。
对于这样一条线，弯过来构成一个圆环形成闭环，这样的一个圆环称为hash环。
我们把服务器的ip或者主机名求hash值然后对应到hash环上，那么针对客户端用户，也根据它的ip进行hash求值，对应到环上某个位置，然后如何确定一个客户端路由到哪个服务器处理呢？按照顺时针方向找最近的服务器节点。比如服务器A在hash环上对应的值为100，服务器B在hash环上对应的值为200，那么经过hash计算后值为大于100小于200的均路由到服务器B上。
当服务下线时
会按照顺时针将请求路由至下一个服务器。
当服务上线时
会将当前节点逆时针至上一台服务器的请求路由至本服务器。
总的来说Hash环按照服务器的数量划分成了不同的段，每台服务器负责一段，增减服务器均只影响部分数据，具有良好的容错性和扩展性。
但分段也造成了数据倾斜问题，即负载不均衡的问题，有的服务器器不堪重负，有的服务器资源闲置浪费。这就需要我们尽可能的使服务器分布均衡。当我们的服务器节点较少时，可以采用填充虚拟节点的方式来平衡分段。具体的做法是给每个虚拟节点分配一个真实的物理节点，当请求到虚拟节点时，路由至附带的真实节点。
一致性HASH算法的简单实现
不含虚拟节点
public class ConsistentHashNoVirtual {
public static void main(String[] args) {
//step1 初始化：把服务器节点IP的哈希值对应到哈希环上
// 定义服务器ip
String[] tomcatServers = new String[]{"123.111.0.0", "123.101.3.1", "111.20.35.2", "123.98.26.3"};
SortedMap<Integer, String> hashServerMap = new TreeMap<>();
for (String tomcatServer : tomcatServers) {
// 求出每⼀个ip的hash值，对应到hash环上，存储hash值与ip的对应关系
int serverHash = Math.abs(tomcatServer.hashCode());
// 存储hash值与ip的对应关系
hashServerMap.put(serverHash, tomcatServer);
}
//step2 针对客户端IP求出hash值
// 定义客户端IP
String[] clients = new String[]{"10.78.12.3", "113.25.63.1", "126.12.3.8"};
for (String client : clients) {
int clientHash = Math.abs(client.hashCode());
//step3 针对客户端,找到能够处理当前客户端请求的服务器（哈希环上顺时针最近）
// 根据客户端ip的哈希值去找出哪⼀个服务器节点能够处理（）| tailMap返回大于等于Key的map
SortedMap<Integer, String> integerStringSortedMap = hashServerMap.tailMap(clientHash);
if (integerStringSortedMap.isEmpty()) {
// 取哈希环上的顺时针第一台服务器
Integer firstKey = hashServerMap.firstKey();
System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" + hashServerMap.get(firstKey));
} else {
Integer firstKey = integerStringSortedMap.firstKey();
System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" + hashServerMap.get(firstKey));
}
}
}
}计算结果：
==========>>>>客户端：10.78.12.3 被路由到服务器：111.20.35.2
==========>>>>客户端：113.25.63.1 被路由到服务器：123.98.26.3
==========>>>>客户端：126.12.3.8 被路由到服务器：111.20.35.2含有虚拟节点
public class ConsistentHashWithVirtual {
// 定义服务器ip
public static final String[] TOMCAT_SERVERS = new String[]{"123.111.0.0", "123.101.3.1", "111.20.35.2", "123.98.26.3"};
// 定义客户端IP
public static final String[] CLIENT_IPS = new String[]{"10.78.12.3", "113.25.63.1", "126.12.3.8"};
// 定义针对每个真实服务器虚拟出来⼏个节点
public static final int VIRTAUL_COUNT = 3;
public static void main(String[] args) {
//step1 初始化：把服务器节点IP的哈希值对应到哈希环上
SortedMap<Integer, String> hashServerMap = new TreeMap<>();
for (String tomcatServer : TOMCAT_SERVERS) {
// 求出每⼀个ip的hash值，对应到hash环上，存储hash值与ip的对应关系
int serverHash = Math.abs(tomcatServer.hashCode());
// 存储hash值与ip的对应关系
hashServerMap.put(serverHash, tomcatServer);
// 处理虚拟节点
for (int i = 0; i < VIRTAUL_COUNT; i++) {
int virtualHash = Math.abs((tomcatServer + "#" + i).hashCode());
hashServerMap.put(virtualHash, "----由虚拟节点" + i + "映射过来的请求：" + tomcatServer);
}
}
//step2 针对客户端IP求出hash值
for (String client : CLIENT_IPS) {
int clientHash = Math.abs(client.hashCode());
//step3 针对客户端,找到能够处理当前客户端请求的服务器（哈希环上顺时针最近）
// 根据客户端ip的哈希值去找出哪⼀个服务器节点能够处理（）| tailMap返回大于等于Key的map
SortedMap<Integer, String> integerStringSortedMap = hashServerMap.tailMap(clientHash);
if (integerStringSortedMap.isEmpty()) {
// 取哈希环上的顺时针第⼀台服务器
Integer firstKey = hashServerMap.firstKey();
System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" + hashServerMap.get(firstKey));
} else {
Integer firstKey = integerStringSortedMap.firstKey();
System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" + hashServerMap.get(firstKey));
}
}
}
}计算结果：
==========>>>>客户端：10.78.12.3 被路由到服务器：111.20.35.2
==========>>>>客户端：113.25.63.1 被路由到服务器：----由虚拟节点2映射过来的请求：111.20.35.2
==========>>>>客户端：126.12.3.8 被路由到服务器：----由虚拟节点0映射过来的请求：123.101.3.1