Hash 这些知识你也应该知道

什么是Hash

Hash中文翻译为散列，又成为“哈希”，是一类函数的统称，其特点是定义域无限，值域有限。把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。

简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

Hash的作用

hash就是将任意长度的消息压缩成某一固定长度的消息摘要的函数。相当于文件的指纹。

由于文件是无限的，而映射后的字符串能表示的位数是有限的。因此可能会存在不同的key对应相同的Hash值。这就是存在碰撞的可能。

Hash存储数据

hash表的本质其实就是数组，hash表中通常存放的是键值对Entry。

这里的学号是个key，哈希表就是根据key值来通过哈希函数计算得到一个值，这个值就是下标值，用来确定这个Entry要存放在哈希表中哪个位置。

hash碰撞的解决方法

hash碰撞的解决方式是开放寻址法和拉链法。

开放寻址法指的是，当前数组位置1被占用了，就放到下一个位置2上去，如果2也被占用了，就继续往下找，直到找到空位置。

拉链法采用的是链表的方式，这个时候位置1就不单单存放的是Entry了，此时的Entry还要额外保存一个next指针，指向数组外的另一个位置，将李四安排在这里，张三那个Entry中的next指针就指向李四的这个位置，也就是保存的这个位置的内存地址。如果还有冲突，就把又冲突的那个Entry放到一个新位置上，然后李四的Entry指向它，这样就形成一个链表。

开放寻址法和拉链法都是想办法找到下一个空位置来存发生冲突的值。

Hash的实际用途

唯一性验证

• java中用于判断变量是否相等都放进 hashCode() 中，⼀起⽣成⼀个尽量不会碰撞的整数

数据完整性验证：

• 从⽹络上下载⽂件后，通过⽐对⽂件的 Hash 值（例如 MD5、SHA1），可以确认下载的⽂件是否有损坏。如果下载的⽂件 Hash 值和⽂件提供⽅给出的 Hash 值⼀致，则证明下载的⽂件是完好⽆损的

快速查找：

• HashMap

隐私保护：

• 当重要数据必须暴露的时候，有事可以选择暴露它的 Hash 值（例如 MD5），以保障原数据的安全。例如⽹站登录时，可以只保存⽤户密码的 Hash 值，在每次登录验证时只需要将输⼊的密码的 Hash 值和数据库中保存的 Hash 值作⽐对就好，⽹站⽆需知道⽤户的密码。这样，当⽹站数据失窃时，⽤户不会因为⾃⼰的密码被盗导致其他⽹站的安全也受到威胁。

作者：Arrom
链接：https://juejin.cn/post/7127862424887099406
来源：稀土掘金