什么是Hash？什么是Hash表？什么是Hash冲突？
HASH
哈希（散列）是指：任意长度的输入经过hash算法转化为固定长度的输出。
public static String strToHashKey(String k) {
String tmpKey;
try {
final MessageDigest mDigest = MessageDigest.getInstance("MD5");
mDigest.update(k.getBytes());
tmpKey = bytesToHexString(mDigest.digest());
} catch (NoSuchAlgorithmException e) {
tmpKey = String.valueOf(k.hashCode());
}
return tmpKey;
}
private static String bytesToHexString(byte[] b) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < b.length; i++) {
String hex = Integer.toHexString(0xFF & b[i]);
if (hex.length() == 1) {
sb.append('0');
}
sb.append(hex);
}
return sb.toString();
}
public static void main(String[] args) {
String str = "TEST_HASH_01_STR";
String str2 = "TEST_HASH_02_STR";
String str3 = "TEST_HASH_03_STR";
String str4 = "TEST_HASH_04_STR";
System.out.println(str + "的hash值= " + strToHashKey(str));
System.out.println(str2 + "的hash值= " + strToHashKey(str2));
System.out.println(str3 + "的hash值= " + strToHashKey(str3));
System.out.println(str4 + "的hash值= " + strToHashKey(str4));
}
控制台输出
--------------------------------------------------------
TEST_HASH_01_STR的hash值= 488ffb5451eca9a66e5841f2d33127c7
TEST_HASH_02_STR的hash值= 4f637e42de1540f7f51687a1e776a5aa
TEST_HASH_03_STR的hash值= 2008b46e01406eb4a44d3176a23cdec2
TEST_HASH_04_STR的hash值= 3e8eb32d529479a488201c53232e79df
哈希的使用
Hash取模 (hash(输入) % n)
现在有3个服务器，要做负载均衡，就可以对请求的ip地址或者用户的id等使用Hash函数，然后将计算得出的Hash值对机器数取模，余数为几，就把请求分配到相应的服务器上。
缺点：新增服务器或者服务器宕机的时候，绝大多数请求基本上都需要重新映射到另一个节点。这种变动有时候是不能接受的。比如在Web负载均衡的场景下，session会保存在每个节点里。当然，如果你是“无状态”的服务，那不会存在这个问题。因为如果增加或者删除了一个节点，就会导致几乎所有的数据都需要重新迁移。
一致性Hash
尽可能降低分布式环境下，通过哈希定位运算确认元素位置的集群服务受机器数的影响，避免使用固定值取模，改为范围定位的方式。
上面的取模运算的除数是机器数，而一致性Hash的除数是2^32（int类型的最大值）。从0到232 - 1,首尾相连构成了一个环。
我们先对服务器节点的IP进行Hash，然后除以2^32
得到服务器节点在这个Hash环中的位置。如果有请求进来了，同样进行Hash然后处于2^32求余。如果落在Hash环上，然后顺时针找到第一个节点，这个节点就负责处理这个请求。
优点：解决因为横向伸缩导致的大规模数据变动。
缺点：一致性Hash算法在节点数量较少的时候，会出现分布不均匀的问题。
解决方案就是在Hash环上增加虚拟节点。
哈希的应用
1.密码学和数字签名。
2.文件的完整性检查。
3.基于HASH的数据结构。
哈希算法的特点
1.不可逆：不可以根据hash值计算出原值。
2.效率高，HASH运算能快速计算出结果。
3.冲突少，优秀的哈希算法具备的特点。
哈希算法
（1）MD4
MD4（RFC 1320）是 MIT 的Ronald L. Rivest在 1990 年设计的，MD 是 Message Digest（消息摘要） 的缩写。它适用在32位字长的处理器上用高速软件实现——它是基于 32位操作数的位操作来实现的。
（2）MD5
MD5（RFC 1321）是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。
（3）SHA-1及其他
SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举（brute-force）性更好。SHA-1 设计时基于和MD4相同原理，并且模仿了该算法。
什么是Hash表？什么又是Hash冲突？
HASH表
哈希表是基于数组的一种存储方式，它主要由哈希函数和数组构成。当要存储一个数据的时候，首先用一个函数计算数据的地址，然后再将数据存进指定地址位置的数组里面。这个函数就是哈希函数，而这个数组就是哈希表。
哈希冲突
哈希是通过对数据进行再压缩，转为为固定长度的输出。但由于通过哈希函数产生的哈希值是有限的，而数据可能比较多，导致经过哈希函数处理后仍然有不同的数据对应相同的值。
哈希冲突的影响因素
装填因子（装填因子=数据总数 / 哈希表长）、哈希函数、处理冲突的方法
HASH冲突的解决方案
1.开放地址方法
（1）线性探测
按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。
（2）再平方探测
按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。
（3）伪随机探测
按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。
2.链式地址法（HashMap的哈希冲突解决方法）
对于相同的值，使用链表进行连接。使用数组存储每一个链表。
优点：
（1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
（2）由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
（3）开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
（4）在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
缺点：
指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率。
3.建立公共溢出区
建立公共溢出区存储所有哈希冲突的数据。
4.再哈希法
对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。
