说唱有嘻哈 演算法有哈希
java零基础入门-高级特性篇(三) 哈希演算法和HashMap
讲完了List之后，我们继续讲集合中的另外两大巨头，Map和Set。在讲解这两个巨头之前，很有必要来了解一下哈希演算法，因为Map和Set的无脑实现类就是HashMap和HashSet，所以在这之前了解Hash演算法对我们更好的理解这两个实现类很有帮助。
哈希演算法是什么
哈希演算法又叫散列演算法，通常用于文件校验，数字签名等场景，比如下面这个新闻
不是在说哈希演算法，这新闻跟哈希演算法有什么关系？
Hash演算法是一种演算法思想，有很多种实现，新闻中的MD5又叫单向散列演算法，是散列演算法的一种实现。看新闻得知一个叫Wow.exe的文件可能中毒了，而公告叫大家检测该文件的MD5校验码，这又是个什么意思？
MD5演算法对文件进行计算以后，可以得到一个32位长度的字元串，这个就是新闻中的MD5校验码。如果文件被病毒修改过，那么会得到一个完全不同的32位字元串，所以我们下载这个WOW.exe文件以后，只需要对这个文件使用MD5演算法，看看校验码是否跟网站给出的MD5校验码一致，就可以判断该文件是否中毒。
相同的文件经过哈希演算法的计算可以得到相同的编码，不同的文件，哪怕只有一点点的修改，都会得到一个完全不同的编码。
那么将上面的结论反过来，具有相同MD5编码的文件，一定是完全相同的文件吗？答案是否定的，两个完全不同的文件得到的MD5编码可能相同，但是概率非常低，也就是说一个被病毒修改过的WOW.exe文件，有可能跟源文件的MD5一样，但是概率低到可以忽略不计，所以比对MD5是可靠的。
现在我们对哈希演算法有了一个大致的了解，那么哈希演算法有什么用，能解决什么问题呢？
哈希演算法解决了什么问题
又要拿快递说事了，没办法，快递里很多规则都是程序员定的，所以用这个来看比较形象。
双十一刚过不久，大家收快递有没有收到手软？手机简讯有没有收到手抖？双十一快递员可没时间给你送上门，往驿站一扔，然后驿站入库以后，就会给你发送一个像下面这样的简讯。
这个简讯其他的信息不重要，最重要的是取货码这个信息。为什么驿站的帅哥美女看到你这个码，马上就能找到你的快递？这个又要来看看驿站的货架是怎么设计的了。
这里A10就是货架编号，8是指第8层，9856是订单后四位，这个快递放在A10架的第8层。每一个快递放到驿站之后，根据在货架上的存放位置，就可以得到一串编码，一旦你去拿快递，驿站小哥看一眼你的快递编码就知道你的快递在哪个架子的什么地方了。
其实哈希演算法跟这个快递入库出库的过程非常相似。哈希演算法的目的，也就是要解决的问题就是高速存取。
首先，我们要存数据必须开辟一块内存空间。（存快递需要一个XX驿站）
然后，我们需要将数据随机，并且均匀的分布到内存空间中。（快递，随机放在快递架子上，并且尽可能均匀的分布。这里均匀的意思是尽量保证快递在架每一个架子，每一层都有，而不是堆在一个架子的一层，如果都堆在一层，找的时候还是一个个去对快递单号，架子没有起到作用，找起来一样很慢）。
数据就算有冲突，必须放在一个空间中，也要保证这个空间中的数据尽量的少。（一个架子上每一层的快递其实不止一个，但是是有限制的，不能太多，这样一来，就算需要一个个的去比对单号后四位，也会很快的找到需要的快递）。
这里将一个快递的位置计算成一个编码A10-8-9856，其实可以看成是一个哈希演算法的实现。但是这个实现不太优秀，因为有过多的快递挤在一个位置。优秀的哈希演算法，既要平局的分配空间，还要尽可能少的将多个数据放在同一个空间，比如MD5的哈希演算法实现就非常优秀，使用场景很多。
好了，基础知识说完了，可以来看看HashMap到底是个什么回事了。
HashMap
上面讲到的两大点，总结一下就是：hash演算法是一种计算方法，将一个文件或者一个值经过hash演算法的计算，得到一个值，这个值的特点是在空间上随机，均匀的分布，以达到高速存取的目的。
前面说过数组和链表，数组查询快，链表增删快，我现在要高速存（增）取（查询），那么数组和链表都不能满足要求，怎么办？将他们组合起来用呗！
先看看Map的特点，Map是一种Key-value结构，key-value又是个啥？初学者学习知识一般都处于十万个为什么状态，可以理解。key-value可以这样理解：快递编码就是Key（A10-8-9856），value就是你的快递包裹，通过Key可以找到value，这样理解了吧。
key用来计算数据存储的位置，value就是要存放的数据。存数据的时候，根据key经过哈希演算法计算出一个地址，将数据扔进去，取得的时候，通过key计算出地址，直接过去拿value，无需遍历，直接存取，这样就达到了高速存储的目的。
看不懂图的，这样理解：数组就是快递的架子，这里的架子有10个，从0开始编号。如果同一个架子的快递多了，就要分层放了，同一个架子的每一层就组成了链表。有没有感觉很形象？（和快递架那张图对比看）
前面看到计算文件的哈希演算法实现是MD5，驿站放快递也有自己的编码实现，那么HashMap如何实现哈希演算法？HashMap的实现是将Key的值计算为一个int值，然后将这个int值作为数组的下标。也就是说key决定了value在数组的什么位置，hash演算法就是将需要保存的数据，均匀的分布在数组之中，避免出现过多的数据在数组的同一个位置。
但是上面说过，hash演算法无法保证不重复，这里重复有两种情况，两种情况的处理方式不同。
1.如果key的值一样，比如上图中，2个数据的key都是111，那么hash演算法计算出的hash下标肯定一样，这种情况，后一个value会直接覆盖掉前一个value，上图中就是第二个数据的bbb直接覆盖掉了第一个数据aaa。
2.第二个情况就是两个不同的值，计算出相同的下标，这个时候会变成链表的存储方式，后来的数据在前面，数据中有一部分存了下一个数据(前一个数据的地址)。上图中ddd后插入，但是在链表中被添加到最前面，并且指向了先插入的数据ccc。（链表使用addFirst()方法头尾插入效率是非常高的）
有了这个处理方法，无论计算出的数组下标值是否一样，都能保证，任何一个不同的Key都能取到value，并且是高速获取。
HashMap的底层实现
HashMap在jdk1.8之前使用的是数组加链表的实现方式，而在1.8中，当链表长度超过8之后，会转为使用数组加红黑树的实现方式。这个知识了解即可，有兴趣的同学可以去看一看红黑树这种数据结构。
HashMap说了这么多 为什么没有说HashSet
一句话，HashSet的底层其实就是HashMap，惊不惊喜，意不意外。
下一章介绍HashMap和HashSet的具体用法和Map，Set家族的其他成员。
推荐阅读：