1.什么是哈希?
散列算法(Hash Algorithm),又称哈希算法,杂凑算法,是一种从任意文件中创造小的数字「指纹」的方法。生成的值成为哈希值。与指纹一样,散列算法就是一种以较短的信息来保证文件唯一性的标志,这种标志与文件的每一个字节都相关,而且难以找到逆向规律。因此,当原有文件发生改变时,其标志值也会发生改变,从而告诉文件使用者当前的文件已经不是你所需求的文件。
Hash 算法能将将任意长度的二进制明文映射为较短的二进制串的算法,并且不同的明文很难映射为相同的 Hash 值。
也可以理解为空间映射函数,是从一个非常大的取值空间映射到一个非常小的取值空间,由于不是一对一的映射,Hash 函数转换后不可逆,意思是不可能通过逆操作和 Hash 值还原出原始的值。
散列方法的主要思想是根据结点的关键码值来确定其存储地址:以关键码值K为自变量,通过一定的函数关系h(K)(称为散列函数),计算出对应的函数值来,把这个值解释为结点的存储地址,将结点存入到此存储单元中。检索时,用同样的方法计算地址,然后到相应的单元里去取要找的结点。通过散列方法可以对结点进行快速检索。散列(hash,也称“哈希”)是一种重要的存储方式,也是一种常见的检索方法。
这里有几点:a.将不定长度转换为固定长度(长度一般128)。b.不可逆的
2.特点是什么?
Hash 值又称为指纹或者摘要,具有以下特点:
正向快速:给定明文和 Hash 算法,在有限时间和有限资源内能计算得到 Hash 值。
逆向困难:给定 Hash 值,在有限时间内很难逆推出明文。
输入敏感:原始输入信息发生任何变化,新的 Hash 值都应该出现很大变化。
冲突避免:很难找到两段内容不同的明文,使得它们的 Hash 值一致。
3.Hash 算法有哪些?
常见 Hash 算法有 MD5 和 SHA 系列,目前 MD5 和 SHA1 已经被破解,一般推荐至少使用 SHA2-256 算法。
4.Hash 算法碰撞
稍微想一下就可以发现,既然输入数据长度不固定,而输出的哈希值却是固定长度的,这意味着哈希值是一个有限集合,而输入数据则可以是无穷多个,那么建立一对一关系明显是不现实的。所以“碰撞”是必然会发生的,所以一个成熟的哈希算法会有较好的抗冲突性,同时在实现哈希表的结构时也要考虑到哈希冲突的问题。
比如“666”经过 Hash 后是“fae0b27c451c728867a567e8c1bb4e53”,相同 Hash 算法得到的值是一样的。比如 WiFi 密码如果是 8 位纯数字的话,顶多就是 99999999 种可能性,破解这个密码需要做的就是提前生成好 0 到 1 亿数字的 Hash 值,然后做 1 亿次布尔运算(就是 Bool 值判断,0 或者 1),而现在普通 I5 四核 CPU 每秒能到达 200 亿次浮点数计算,做 1 亿次布尔运算也就是秒级别的时间就破解了。
所以密码尽量不要用纯数字,因为根本没有任何安全性。
5.加盐防碰撞
对数字内容进行 Hash 运算,获取唯一的摘要值来指代原始完整的数字内容,利用 Hash 函数的抗碰撞性来确保内容未被篡改。
常用于用户名和密码来确保用户信息安全,为了防止攻击会采用加盐的方法,就是原来的明文加上一个随机数之后的 Hash 值,Hash 值和盐会保存在两个地方,只要不是同时泄漏就很难被破解。
6.哈希冲突解决策略:
1)开放寻址法(Open Addressing),将所有的元素都存放在哈希表内的数组中,不使用额外的数据结构。开放寻址法的最简单的一种实现就是线性探查(Linear Probing)。
2)链接技术(chaining),在链接法中,把哈希到同一个槽中的所有元素都放到一个链表中。
部分引用:
https://blog.csdn.net/guidao13/article/details/84104526
https://www.cnblogs.com/gaochundong/p/hashtable_and_perfect_hashing.html
网友评论