HashMap的工作原理(一)：Hash算法

1、什么是Hash

Hash也被称为散列、哈希，对应的英文都是Hash.他们的基本原理都是把任意长度的输入，通过Hash算法变成固定长度的输出.这个映射的规则就是对应的Hash算法，而原始数据映射之后的二进制串就是哈希值. 经常使用的Hash算法有MD5和SHA，他们都是历史悠久的Hash算法.

String s = "Hash算法";
System.err.println(md5(s));
// 输出结果：f1ab62697296f0b575b9229dba7ea1ba

这个例子中，"Hash算法"是原始值，f1ab62697296f0b575b9229dba7ea1ba则是通过这种md5的hash算法得到的Hash值。整个Hash算法的过程就是把原始任意长度的值空间映射成固定长度的值空间的过程.

对于Hash算法来说，主要会在数据结构和密码学中得到应用，在这两种不同的领域，算法的设计重点也是不同的.

2、Hash算法的特点

hash算法作为一个算法，有许多不同的实现方式，比如上面说的MD5或者SHA. 这些算法除了满足上述Hash的基本功能之外，也需要有其他的特点来确保他是一个可用的、合理的、优秀的Hash算法.

从Hash值不可以反向推导出原始的数据
经过Hash映射之后的数据和原始数据没有对应关系
Hash算法的执行效率要高效，长的文本或字符串能够很快的计算出哈希值
输入数据的微小变化会得到完全不同的Hash值，相同的数据会得到相同的值
这里也可以说Hash算法的**抗篡改能力：对于一个数据块，哪怕只修改一个比特位，其Hash值的改动也会非常大. **

String s = "Hash算法";System.err.println(md5(s));// 输出结果：f1ab62697296f0b575b9229dba7ea1baString s = "Hesh算法";System.err.println(md5(s));// 输出结果：d789d51b7005d2d55c23bbfc4367d97d

通过这个实例我们可以看到，只是改变了一个字符，却能导致两个hash值几乎每一位都不同.

Hash算法的冲突概率要小
Hash算法的原理是把输入空间的值映射到Hash空间内，由于Hash值的空间远小于输入的空间，而且借助抽屉原理，可以得出一个结论——一定会存在不同的输入被映射成相同输出的情况，如果一个Hash算法足够好，那么他就一定会有更小的发生冲突的概率. 也就是说，一个好的Hash算法应该具有优秀的抗碰撞能力
**抗碰撞能力：对于任意两个不同的数据块，其Hash值相同的可能性极小；对于一个给定的数据块，找到一个和他Hash值相同的数据块是极为苦难的. **

抽屉原理
桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理

3、数据结构中的Hash

在使用到Hash进行管理的数据结构中，比如HashMap，在这种数据结构中，Hash值（Key）存在的目的就是加速键值对的查找，因为HashMap的桶数组的容量是有限的，而且HashMap也采用了一系列的方法来进行碰撞处理，所以对于数据结构中的Hash，对抗碰撞能力的要求并不是很高.

但是对于HashMap的set操作，需要实现快速存储，那么这里就要求Hash算法的速度尽可能的快了.

4、密码学中的Hash

在密码学中，Hash算法的作用主要在于消息摘要或者是签名. 比如我们在登录某些网站的时候，需要输入密码来完成登陆操作，对于这些网站的运营商来说，明文保存密码是万万不可的，所以大部门网站的解决方式就是用Hash算法去生成密码的签名也就是他的Hash值，运营商后台去保存这个Hash值. 由于Hash算法的不可逆的特点，即使黑客拿到了这个Hash值，也不可以推出密码.

这样的场景里面，Hash算法的速度显得并不是那么重要了，与之相对的，抗碰撞和抗篡改能力要求极高. 一个优秀的Hash算法他的抗碰撞能力是非常强大的. 以MD5为例，输出长度为128位，设计预期的碰撞概率是1/264，这是一个极小的数字.

2004年8月17日的美国加州圣巴巴拉，正在召开的国际密码学会议（Crypto’2004）安排了三场关于杂凑函数的特别报告。其中来自山东大学的王小云教授做了破译MD5、HAVAL-128、 MD4和RIPEMD算法的报告。
在会场上，当她公布了MD系列算法的破解结果之后，报告被激动的掌声打断。她的研究成果作为密码学领域的重大发现宣告了固若金汤的世界通行密码标准MD５的堡垒轰然倒塌，引发了密码学界的轩然大波。
经过了王小云教授的破解之后，MD5的碰撞上限被降低至1/241

即使是降低到了1/241，这也是一个很小的数字，也就是需要经过240次查找，才能有1/2的概率来找到一个和目标文件相同的Hash值.

5、Random Oracle

有没有可能找到这么一个算法，如果输出长度为128位，那么把这128位“充分利用到”，让它可以有1/2128种不同的hash值，而且分布均匀，抗篡改能力也特别高，一点点改动就会让hash值面目全非，一点都不浪费（这里的表述非常不严格）？稍微严格一点表述，就是： 有没有这样一个算法，使得对于任何一个给定的输入，此算法都会输出一个固定的均匀随机的输出？

问题的答案是密码学家们到现在也没有能力去构造出一个这样的算法，但是大家更加倾向于这个算法是存在的，而且有不少的密码学算法构造和这个假设有关，这个假设的名字就是Random Oracle（随机预言机）

6、Hash的用途

应用一：安全加密
上述的密码学中的Hash，在安全加密的应用比较广泛.
不过需要知道的是，现在的世界上没有一个绝对安全的加密. 越复杂、越难破解的加密算法，需要计算的时间就越长. 密码学界一直在致力去找一种可以快速生成并且很难被破解的Hash算法. 而且我们在实际的开发中，也需要权衡破解难度和计算时间，来决定究竟使用哪种加密算法.
应用二：唯一标识
由于Hash算法的抗碰撞能力，我们可以对一些难以查找、比较的文件或者其他的数据进行Hash计算，生成一个Hash值，也就是他的唯一标识. 这样去判断文件是否存在这样的操作就会简单很多.
应用三：数据校验
BT种子下载软件的原理是基于P2P协议的，从多个机器上下载一个2GB的电影，这个电影文件可能会被分成很多块，等所有块下载好然后组装成一个完整电影.
网络传输是不安全的，所以下载出来的文件块是可能不完整的，这个时候我们就可以通过对文件块进行Hash运算，在下载之后和之前的Hash值进行对比，就可以进行数据校验.
应用四：散列函数
基本用在数据结构中，散列表的实现.
应用五：负载均衡
在分布式系统中，需要应用负载均衡的方式去将会话的请求分发给不同的服务器. 这里我们可以使用Hash算法对客户端IP进行计算Hash值，与服务器列表大小进行取模运算，获取对应需要被路由道的服务器编号.
应用六：数据分片
一般都在应用于分布式解决问题，分治的思想，通过Hash来进行分区域分片实现“分”的操作.
应用七：分布式存储
通过Hash值确定数据要存储到哪台机器上；如果机器新增了，数量改变了，我们可以通过一致性hash算法来避免大量的数据搬运.

7、一致性Hash算法

一致性哈希算法在1997年由麻省理工学院提出，是一种特殊的哈希算法，目的是解决分布式缓存的问题。在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。一致性哈希解决了简单哈希算法在分布式哈希表( Distributed Hash Table，DHT) 中存在的动态伸缩等问题