哈希 学习笔记

版权声明：原创内容，如需转载请联系作者。 https://blog.csdn.net/CrankZ/article/details/84930323

Tips：Hash=哈希=散列

Tips：哈希经常与哈希函数指一个意思。本文中哈希与哈希函数不做特殊区分，默认就是一个意思。

什么是哈希

在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。
哈希函数就是一种映射，是从关键字到存储地址的映射。
通常，包含哈希函数的算法的算法复杂度都假设为O(1)，这就是为什么在哈希表中搜索数据的时间复杂度会被认为是”平均为O(1)的复杂度”.

哈希两个主要概念

  1. 哈希函数的设计
  2. 哈希碰撞的解决

哈希函数的性质

所有哈希函数都有如下一个基本特性：如果两个哈希值是不相同的（根据同一函数），那么这两个哈希值的原始输入也是不相同的。这个特性是哈希函数具有确定性的结果，具有这种性质的哈希函数称为单向哈希函数。但另一方面，哈希函数的输入和输出不是唯一对应关系的，如果两个哈希值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“哈希碰撞（collision）”，这通常是两个不同长度的输入值，刻意计算出相同的输出值。输入一些数据计算出哈希值，然后部分改变输入值，一个具有强混淆特性的哈希函数会产生一个完全不同的哈希值。

典型的哈希函数都有非常大的定义域，比如SHA-2最高接受(264-1)/8长度的字节字符串。同时哈希函数一定有着有限的值域，比如固定长度的比特串。在某些情况下，哈希函数可以设计成具有相同大小的定义域和值域间的单射。哈希函数必须具有不可逆性。

一个优秀的哈希函数，将能满足：

  • 正向快速：给定原文和 Hash 算法，在有限时间和有限资源内能计算得到 Hash 值；
  • 逆向困难：给定（若干）Hash 值，在有限时间内无法（基本不可能）逆推出原文；
  • 输入敏感：原始输入信息发生任何改变，新产生的 Hash 值都应该发生很大变化；
  • 碰撞避免：很难找到两段内容不同的明文，使得它们的 Hash 值一致（即发生碰撞）。

碰撞避免有时候又被称为“抗碰撞性”，可分为“弱抗碰撞性”和“强抗碰撞性”。给定原文前提下，无法找到与之碰撞的其它原文，则算法具有“弱抗碰撞性”；更一般地，如果无法找到任意两个可碰撞的原文，则称算法具有“强抗碰撞性”。

很多场景下，也往往要求算法对于任意长的输入内容，输出为定长的 Hash 结果。

哈希碰撞

在计算机科学中，碰撞或冲突是指两个不同的元素具有相同的哈希值。即不同的输入却有相同的输出。当数据量足够多时，碰撞是不可避免的。

哈希碰撞产生的理论前提

  1. 输入长度无限大
  2. 但是输出是有限长度

这必然会导致碰撞

举个例子

一般来说一年365天。假设一个班级里有366个学生，那么至少有2位学生生日相同。这就产生了碰撞

但这并不意味着散列算法就不能用了，因为凡事都要考虑代价，买光所有彩票去中一次头奖是毫无意义的。现代散列算法所存在的理由就是，它的不可逆性能在较大概率上得到实现，也就是说，发现碰撞的概率很小，这种碰撞能被利用的概率更小。

随意找到一组碰撞是有可能的，只要穷举就可以。散列算法得到的指纹位数是有限的，比如MD5算法指纹字长为128位，意味着只要我们穷举21282128次，就肯定能得到一组碰撞——当然，这个时间代价是难以想象的，而更重要的是，仅仅找到一组碰撞并没有什么实际意义。

你也许已经听过MD5已经被破解的新闻——但事实上，即便是MD5这种已经过时的散列算法，也很难实现逆向运算。我们现在更多的还是依赖于海量字典来进行尝试，也就是通过已经知道的大量的文件——指纹对应关系，搜索某个指纹所对应的文件是否在数据库里存在。

处理哈希碰撞

本文主要介绍两种方法

  1. 链地址法
  2. 开放地址法

1、链地址法（Seperate Chaining）

数组长度为m，已有k1、k2两个元素

k3经过哈希函数计算，与k2的位置一样，这时候就产生了冲突。

采用链地址法来处理这种情况的话，就直接把k3加在k2后面，形成一个链表。

2、开放地址法

开放地址发的意思是，地址是对所有元素开放的，就算哈希后的地址不是这一个，也可以占用这一个位置。

常见的开放地址法又可分为

  1. 线性探测法
  2. 平方探测法
  3. 再哈希法

为了方便演示，我们把哈希函数设置成简单的 hash(x) = x % 10

2、1线性探测法

我们输入11,25进行运算

11 % 10 = 1
25 % 10 = 5

那么11就插入下标为1的地址中，25就插入下标5的地址中

再插入数字31

31 % 10 = 1

这时候31和11的地址冲突了，怎么办？

31经过哈希函数运算，结果为1,。但是1被占用了，如果采用线性探测法，就在地址1的基础上+1，直到找到下一个空白的地址，然后插入。

小结

  • 开放地址法：每一个地址都对所有元素时开放的
  • 线性探测法：遇到哈希冲突，地址+1，直到找到空白地址，然后插入

这种效果效率低，每次+1的话，很容易会把某一个断区域的地址完全被占用，如果一段区域全部被占用了。那么每次都要+1很多次，计算次数会增加很多，浪费计算资源。

所以为了避免这种情况。诞生出了很多改进方法。比如平方探测法，不是每次都+1了，而是+平方，+1,+4,+9…+n^2，就是为了避免以整块区域完全被占据的情况。所以性能会提高一些。还有二次哈希法，就是遇到冲突时当前key通过另一个哈希函数在进行一次运算，然后地址加上这次哈希的结果，也就是+hash2(key)。

Tips：在JDK1.8之前，Java中的HashMap处理哈希冲突就是用链地址法，但1.8之后改进了这个方法，先使用链表，如果冲突到达了一定的数量，就改用红黑树。

哈希的应用

哈希算法广泛应用于很多场景，例如安全加密和数据结构中哈希表的查找，布隆过滤器和负载均衡（一致性哈希）等等。

  1. 数据结构：比如Java中的HashMap。
  2. 加密或验证：MD5和SHA加密算法
  3. 布隆过滤器：用于查找元素，空间和时间效率都很高。
  4. 一致性哈希

本文主要介绍三种应用

  1. 布隆过滤器
  2. 常见加密算法：MD5,SHA
  3. 哈希在java中的应用

1、布隆过滤器

布隆过滤器（Bloom Filter）是1970年由布隆提出的，它实际上是由一个很长的二进制向量和一系列随意映射函数组成。

 它是一种基于概率的数据结构，主要用来判断某个元素是否在集合内，它具有运行速度快（时间效率），占用内存小的优点（空间效率），但是有一定的误识别率和删除困难的问题。它能够告诉你某个元素一定不在集合内或可能在集合内。

在计算机科学中，我们常常会碰到时间换空间或者空间换时间的情况，通常两者不可兼得，我们要在两者之间取舍。但是布隆过滤器在空间与时间效率上都很高。

关于布隆过滤器，详细请看我另一篇博文https://blog.csdn.net/CrankZ/article/details/84928562

2、常见哈希算法

2、1MD5

MD5即Message-Digest Algorithm 5（信息-摘要算法5），用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一，主流编程语言普遍已有MD5实现。将数据（如汉字）运算为另一固定长度值，是杂凑算法的基础原理，MD5的前身有MD2、MD3和MD4。
MD5是输入不定长度信息，输出固定长度128-bits的算法。经过程序流程，生成四个32位数据，最后联合起来成为一个128-bits散列。基本方式为，求余、取余、调整长度、与链接变量进行循环运算。得出结果。

MD5一度被广泛应用于安全领域。但是在2004年王小云教授公布了MD5、MD4、HAVAL-128、RIPEMD-128几个 Hash函数的碰撞。这是近年来密码学领域最具实质性的研究进展。使用他们的技术，在数个小时内就可以找到MD5碰撞。使本算法不再适合当前的安全环境。目前，MD5计算广泛应用于错误检查。例如在一些BitTorrent下载中，软件通过计算MD5和检验下载到的碎片的完整性。

2、2SHA家族

SHA家族算法的种类很多，有SHA0、SHA1、SHA256、SHA384等等，它们的计算方式和计算速度都有差别。其中SHA1是现在用途最广泛的一种算法。包括GitHub在内的众多版本控制工具以及各种云同步服务都是用SHA1来区别文件，很多安全证书或是签名也使用SHA1来保证唯一性。长期以来，人们都认为SHA1是十分安全的，至少大家还没有找到一次碰撞案例。

但这一事实在2017年2月破灭了。CWI和Google的研究人员们成功找到了一例SHA1碰撞，而且很厉害的是，发生碰撞的是两个真实的、可阅读的PDF文件。这两个PDF文件内容不相同，但SHA1值完全一样。(对于这件事的影响范围及讨论，可参考知乎上的讨论:如何评价 2 月 23 日谷歌宣布实现了 SHA-1 碰撞？)

所以，对于一些大的商业机构来说， MD5 和 SHA1 已经不够安全，推荐至少使用 SHA2-256 算法。

2、3Java使用MD5,SHA1

public static void main(String[] args) {
    System.out.println(encrypt("CrankZ", "MD5"));
    System.out.println(encrypt("CrankZ", "SHA1"));
}

public static String encrypt(String str, String algorithm) {
    // 计算md5函数
    try {
        // 生成一个MD5加密计算摘要
        MessageDigest md = MessageDigest.getInstance(algorithm);
        md.update(str.getBytes());
        // digest()最后确定返回md5 hash值，返回值为8为字符串。因为md5 hash值是16位的hex值，实际上就是8位的字符
        // BigInteger函数则将8位的字符串转换成16位hex值，用字符串来表示；得到字符串形式的hash值
        return new BigInteger(1, md.digest()).toString(16);
    } catch (NoSuchAlgorithmException e) {
        throw new RuntimeException(e);
    }
}

3、Hash在Java中的应用

  1. Object.hashCode()
  2. HashMap

参考：

维基百科
https://blog.csdn.net/asdzheng/article/details/70226007
http://www.alloyteam.com/2017/05/hash-functions-introduction/
https://coding.imooc.com/class/207.html


更多精彩内容