细说Hash（哈希）

一. 散列函数（Hash function)

含义：

把任意长度的输入，提取数据摘要，通过散列算法转换成固定长度的输出。

特性：

1.散列的值不同，则输入的内容必定不同。

2.散列的值相同，输入的值不一定相同（存在哈希碰撞的情况）。

3.散列的值不可逆（无法通过散列的值推导出原输入内容）

Hash算法：

Hash算法没有固定的公式，只要符合散列思想的算法都可以称之为Hash算法。MD5 和 SHA-1 可以算是当前用途最广泛的Hash算法了。

MD5被广泛用于校验数据完整性，如：当下载完文件后，可以生成一份MD5文件和源文件的MD5做对比，如果一样的话，则视为文件完整，否则，就可能因为下载有缺失、数据被人修改过等导致下载的文件和源文件不一致。

PS：小知识，即使是MD5也是会出现哈希碰撞的情况的，不过概率极低极低而且很难通过人为修改数据让散列值一致~ 所以基本还是可以认为MD5校验是准确的。 如果需要极高准度，不希望有任何哈希碰撞的可能的话，可以对源文件进行一次MD5得出散列值A，然后再对源文件进行一次SHA-1得出散列值B，再把A和B连接起来再进行一次MD5，这样通过结合MD5和SHA-1的方式来得出的校验结果，应该是高度精准了~

二.哈希表（Hash table）

数组：读数据速度很快，可增删数据效率却很低。

链表：增删数据效率很高，可读数据的速度就很慢。

哈希表：我认为是集数组和链表的优点于一身，读写都能有较高的效率。

哈希表的工作流程：

1.用户输入一组键值对{key, value}数据。

2.使用hash函数对用户输入的key进行处理F(key)。

3.通过F(key)的处理结果直接得到对应存储位置上的值。PS：不需要一个个遍历，直接得到值。

4.如果对应位置上的值为空，则直接放入value即可。

哈希碰撞：

上面工作流程的第四步，一旦对应位置上已经有值存在了，且该值对应的key 不等于当前用户输入的key，则发生了哈希碰撞。因为不同的输入源（key）经过Hash函数处理后是有可能生成相同的散列值的。

处理哈希碰撞的方法有多种，此处拿hashmap的方案来作为解决方案（我认为他的方案挺好的~）。 我们保存数据时可以以链表的形式来保存数据，当发生哈希冲突时，只需要遍历链表，看看有没存在相同key的，有就覆盖，没就在链表末端追加这组新的数据就可以了。 然后为了加快查找速度，当链表的数量大于8个时，我们可以把链表转换成红黑树。

PS：即使发生哈希碰撞，最理想的情况依然是均匀分布在每个散列值下面，如果某几个散列值发生碰撞的次数过多，导致分布不均，此时的哈希表效率就变低了，也不是我们想要的结果，可以考虑换一种哈希算法试试。