01.什么是哈希算法哈希算法历史悠久业界著名的哈希算法也很多比如MD5、SHA等。在平时的开发中基本上都是拿现成的直接用。今天不会重点剖析哈希算法的原理也不会教你如何设计一个哈希算法而是从实战角度告诉你在实际开发中我们该如何用哈希算法解决问题。什么是哈希算法用一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串这个映射规则就是哈希算法而通过原始数据映射之后得到的二进制值串就是哈希值。但是要设计一个优秀的哈希算法并不容易我了需要满足的几点要求从哈希值不能反向推导出原始数据所以哈希算法也叫单向哈希算法对输入数据非常敏感哪怕原始数据只修改了一个Bit最后得到的哈希值也大不相同散列总被的概率要很小对于不同的原始数据哈希值相同的概率非常小哈希算法的执行效率尽量高效针对较长的文本也能快速计算出哈希值。拿MD5这种哈希算法具体说明下比如计算这两个文本的MD5哈希值——“今天我来讲哈希算法”、“jiajia。得到的两串毫无规律的字符串MD5的哈希值是128位的Bit长度便于表示转化为16进制编码。可以看出无论文本的长度是多少得到的哈希值长度是相同的而且看起来像一堆随机数完全没有规律。MD5(今天我来讲哈希算法) bb4767201ad42c74e650c1b6c03d78fa MD5(jiajia) cd611a31ea969b908932d44d126d195b试试两个很相似的文本虽然只有一个标点的差别但哈希值是完全不相同的。同时根据哈希值是很难反向推导出原始数据。MD5(我今天讲哈希算法) 425f0d5a917188d2c3c3dc85b5e4f2cb MD5(我今天讲哈希算法 ) a1fb91ac128e6aa37fe42c663971ac3d哈希算法要处理的文本可能是各种各样的。比如对于非常长的文本如果哈希算法的计算时间很长那就只能停留在理论研究的层面很难应用到实际软件开发中。比如把今天的这篇包含4000多个汉字的文章用MD5计算哈希值用不了1ms的时间。02.哈希算法的应用Hash有哪些流行的算法目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2。哈希算法主要有哪些MD5算法MD5MD5盐SHA算法包含5个算法分别是SHA-1、SHA-224、SHA-256、SHA-384和SHA-512后四者并称为SHA-2。哈希算法的应用非常非常多选了最觉的七个分别是安全加密、唯一标识、数据校验、散列函数、Git版本控制、云存储、数据分片。03.安全加密的场景说到哈希算法的应用最先想到的应该是安全加密。最常用于加密的哈希算法是MD5MD5 Message-Digest AlgorithmMD5消息摘要算法和SHASecure Hash Algorithm安全散列算法。除了这两个之外当然还有很多其他的加密方法比如DESAdvance Encryption Standard高级加密标准。对用于加密的哈希算法来说有两点很重要第一是很难根据哈希值反向推导出原始数据第二是散列冲突的概率要很小。第一点很好理解加密的目的就是不会后悔原始数据泄露所以很难通过哈希值反向推导出原始以数据这是一个基本要求。重点说说第二点但不管什么哈希算法我们只能尽量减少碰撞冲突的概率理论上是没办法做到完全不冲突的这是为什么呢基于组合数学中一个叛党基础的理论鸽巢原理也叫抽屉原理。这个原理本身很简单它是说如果有10个鸽巢有11只鸽子那肯定有1个鸽巢中的鸽子数量大于1换句话说就是肯定有一个巢里的鸽子数量大于1。哈希算法产生的哈希值的长度是固定且有限的。比如前面说的MD5的鸽子哈希值是固定的128位二进制串能表示的数据是有限的最多表示2^128个数据而我们要哈希的数据可以是无穷的那必然会存在哈希值相同的情况。如果我们拿到一个MD5哈希值希望通过毫无规律的穷举的方法找到这个MD5值相同的另一个数据那耗费的时间应该是个天文数字了。即便哈希算法理论上存在冲突但还是很难破解的。除此之外没有绝对安全的加密。越复杂、越难破解的加密算法需要的计算时间也越长。比如SHA-256比SHA-1要更复杂、更安全相应的计算时间就会比较长。04.唯一标识的场景先举个例子。如果要在海量的图库中搜索一张图是否存在我们不能单纯地用图片的元信息比如图片名称来对比因为有可能存在名称相同但图片内容不同或者名称不同图片内容相同的情况。那我们该如何搜索呢任何文件在计算机中都可以表示成二进制码串所以比较笨的办法就是拿要查找的图片的二进制码串与图库中所有图片的二进制码串逐一比对。如果相同则说明图片在图库中存在。但是每个图片小则几十KB、大则几MB,转化成二进制是一个非常长的串比对起来非常耗时。有没有比较快的方法呢可以给每一个图片取一个唯一标识或者说信息摘要。比如我们可以从图片二进制码串开关取100个字节从中间取100个字节从最后取100个字节然后将这300个字节放一块。通过这个唯一标识来判定图片是否在图库中这样就可以减少很多工作量。如果还想继续提高效率我们可以把每个图片的唯一标识和相应的图片文件在图库中的路径信息都存储在散列表中。当要查看某个图片是不是在图库的时候我们先通过哈希算法对这个图片取唯一标识然后在散列表中查找是否存在这个标识。如果不存在那就说明这个图片不在图库中如果存在我们再通过散列表存储的文件路径获取到这个已经存在的图片跟现在要插入的图片做全量的比对看是否完全一样如果一样就说明已经存在如果一一样说明两张图片尽管唯一标识相同但是并不是相同的图片。05.数据校验的场景电驴这样的BT下载软件听过吧BT下载的原理是基石地P2P协议的。我们从多个机器上并行下载一个2GB的电影这个电影文件可能会被分割成很多文件块比如可以分成100块每块大约200MB。等所有的文件块都下载完成之后再组装成一个完整的电影文件就行了。网络传输是不安全的下载的文件块有可能是被宿主机恶意修改过的又或者下载过程中出现了错误所以下载的文件块可能不是完整的。如果我们没有能力检测这种恶意修改或者文件下载出错就会导致最终合并后的电影无法观看甚至导致电脑中毒。现在的问题是如何来校验文件块的安全、正确、完整呢具体的BT协议很复杂校验方法也有很多我来说其中的一种思路。我们通过哈希算法对100个文件块分别取哈希值并且保存种子文件中。在前面讲过哈希算法有一个特点对数据很敏感。只要文件块内容有一丁点儿的改变最后计算出的哈希值就会完全不同。所以当文件块下载完成之后我们可以通过相同的哈希算法对下载好的文件逐一求哈希值然后跟种子文件中保存的哈希值比对。如果不同说明这个文件块不完整或者被篡改了需要再重新从其他宿主机上下载这个文件块。06.散列函数的场景散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。不过相对哈希算法的其他应用散列函数对于散列算法冲突的要求要低很多。即便是出现个别散列冲突只要不是过于严重我们都可以通过开放寻址法或者链表法解决。不仅如此散列函数对于散列算法计算得到的值是否能反向解密也并不关心。散列函数中用到的散列算法更加关注散列后的值是否能平均分布也就是一组数据是否能均匀的散列到各个槽中。除此之外散列函数执行的快慢也会影响散列表的性能能以散列函数用的散列算法一般都比较简单比较追求效率。最常见的散列函数应用场景比如工业存储key-value集合HashMap数据结构存储key就用到了散列函数HashMap为何对key使用哈希算法hash值key存在的目的是加速键值对的查找key的作用是为了将元素适当地放在各个桶里对于抗碰撞的要求没有那么高。07.Git版本的控制以Git为代表的众多版本控制工具都在使用SHA1等散列函数检查文件更新包括GitHub在内的众多版本控制工具以及各种云同步服务都是用SHA1来区别文件很多安全证书或是签名也使用SHA1来保证唯一性。长期以来人们都认为SHA1是十分安全的至少大家还没有找到一次碰撞案例。08.云存储文件场景现在大部分的网络部署和版本控制工具都在使用散列算法来保证文件可靠性。在进行文件系统同步、备份等工具时使用散列算法来标志文件唯一性能帮助我们减少系统开销这一点在很多云存储服务器中都有应用。当原有文件发生改变时其标志值也会发生改变从而告诉文件使用者当前的文件已经不是你所需求的文件。散列函数很难可逆这种不可逆性体现在你不仅不可能根据一段通过散列算法得到的指纹来获得原有的文件也不可能简单地创造一个文件并让它的指纹与一段目标指纹相一致。09.哈希算法的总结第一个应用是唯一标识哈希算法可以对大数据做信息摘要通过一个较短的二进制编码来表示很大的数据。第二个应用是校验数据的完整性和正确性。第三个应用是安全加密任何哈希算法都会出现散列冲突但是这个冲突的概率非常小。越是复杂的哈希算法越难破解但同样计算时间也就越长。所以选择哈希算法的时候要权衡安全性和计算时间来决定用哪种哈希算法。第四个应用是散列函数这个我们前面讲散列表的时候详细说过它对哈希算法的要求非常特别更加看重的是散列的平均性和哈希算法的执行效率。10.哈希算法的特点正向快速给定明文和 hash 算法在有限时间和有限资源内能计算出 hash 值。逆向困难给定若干 hash 值在有限时间内很难基本不可能逆推出明文。输入敏感原始输入信息修改一点信息产生的 hash 值看起来应该都有很大不同。冲突避免很难找到两段内容不同的明文使得它们的 hash 值一致发生冲突。即对于任意两个不同的数据块其hash值相同的可能性极小对于一个给定的数据块找到和它hash值相同的数据块极为困难。11.哈希算法的实践提供几个简单的概念供大家参考作为散列算法首要的功能就是要使用一种算法把原有的体积很大的文件信息用若干个字符来记录还要保证每一个字节都会对最终结果产生影响。那么大家也许已经想到了求模这种算法就能满足我们的需要。事实上求模算法作为一种不可逆的计算方法已经成为了整个现代密码学的根基。只要是涉及到计算机安全和加密的领域都会有模计算的身影。散列算法也并不例外一种最原始的散列算法就是单纯地选择一个数进行模运算比如以下程序。# 构造散列函数 def hash(a): return a % 8 # 测试散列函数功能 print(hash(233)) print(hash(234)) print(hash(235))123上述的程序完成了一个散列算法所应当实现的初级目标用较少的文本量代表很长的内容求模之后的数字肯定小于8。但也许你已经注意到了单纯使用求模算法计算之后的结果带有明显的规律性这种规律将导致算法将能难保证不可逆性。所以我们将使用另外一种手段那就是异或。在散列函数中加入一个异或过程# 构造散列函数 def hash(a): return (a % 8) ^ 5 # 测试散列函数功能 print(hash(233)) print(hash(234)) print(hash(235)) # 输出结果 - 4 - 7 - 6很明显的加入一层异或过程之后计算之后的结果规律性就不是那么明显了。如果用户使用连续变化的一系列文本与计算结果相比对就很有可能找到算法所包含的规律。在进行计算之前对原始文本进行修改或是加入额外的运算过程如移位# 构造散列函数 def hash(a): return (a 2 (a 1)) % 8 ^ 5 # 测试散列函数功能 print(hash(233)) print(hash(234)) print(hash(235)) # 输出结果 - 0 - 5 - 6这样处理得到的散列算法就很难发现其内部规律上面的算法是不是很简单事实上常用算法MD5和SHA1其本质算法就是这么简单只不过会加入更多的循环和计算来加强散列函数的可靠性。12.常用哈希码算法下面给出在Java中几个常用的哈希码(hashCode)的算法。Object类的hashCode. 返回对象的经过处理后的内存地址由于每个对象的内存地址都不一样所以哈希码也不一样。这个是native方法取决于JVM的内部设计一般是某种C地址的偏移。String类的hashCode. 根据String类包含的字符串的内容根据一种特殊算法返回哈希码只要字符串的内容相同返回的哈希码也相同。Integer等包装类返回的哈希码就是Integer对象里所包含的那个整数的数值例如Integer i1new Integer(100), i1.hashCode的值就是100 。由此可见2个一样大小的Integer对象返回的哈希码也一样。intchar这样的基础类它们不需要hashCode如果需要存储时将进行自动装箱操作计算方法同上。13.Map哈希的算法对key进行Hash计算在JDK8中由于使用了红黑树来处理大的链表开销所以hash这边可以更加省力了只用计算hashCode并移动到低位就可以了。static final int hash(Object key) { int h; //计算hashCode并无符号移动到低位 return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }举个例子: 363771819^(363771819 16)。这样做可以实现了高地位更加均匀地混到一起。0101 1010 1110 1011 0111 1010 1011(363771819)0000 0000 0000 0001 0101 1010 1110(5550) XOR--------------------------------------- 0101 1010 1110 1010 0010 0000 0101(363766277)获取到数组的index的位置。计算了Hash我们现在要把它插入数组中了//tab是NodeK,V[] tab int index (tab.length - 1) hash;通过位运算确定了当前的位置因为HashMap数组的大小总是2^n所以实际的运算就是 (0xfff…ff) hash 这里的tab.length-1相当于一个mask滤掉了大于当前长度位的hash使每个i都能插入到数组中。这个对象是一个包装类Nodestatic class NodeK,V implements Map.EntryK,V { final int hash; final K key; V value; NodeK,V next; //getter and setter .etc. }插入包装类到数组。如果输入当前的位置是空的就插进去如图左为插入前右为插入后0 0 | | 1 - null 1 - null | | 2 - null 2 - null | | ..- null ..- null | | i - null i - new node | | n - null n - null如果当前位置已经有了node且它们发生了碰撞则新的放到前面旧的放到后面这叫做链地址法处理冲突。可以发现失败的hashCode算法会导致HashMap的性能由数组下降为链表所以想要避免发生碰撞就要提高hashCode结果的均匀性。0 0 | | 1 - null 1 - null | | 2 - null 2 - null | | ..- null ..- null | | i - old i - new - old | | n - null n - null14.理解HashCodeHashCode也是哈希算法的一种HashCode是Object的一个方法hashCode方法返回一个hash code值且这个方法是为了更好的支持hash表比如StringSetHashTable、HashMap等;HashCode的意义是什么如果用 equal 去比较的话如果存在1000个元素你 new 一个新的元素出来需要去调用1000次equal去逐个和他们比较是否是同一个对象这样会大大降低效率。hashcode实际上是返回对象的存储地址如果这个位置上没有元素就把元素直接存储在上面如果这个位置上已经存在元素这个时候才去调用equal方法与新元素进行比较这样大大提高效率。HashCode的作用减少查找次数提高程序效率。例如查找是否存在重复值h(k1)≠h(k2)则k1≠k2首先查看h(k2)输出值内存地址查看该内存地址是否存在值如果无则表示该值不存在重复值如果有则进行值比较相同则表示该值已经存在散列列表中如果不相同则再进行一个一个值比较而无需一开始就一个一个值的比较减少了查找次数用hashcode判断两个对象是否相等可以吗肯定是不可以的因为不同的对象可能会生成相同的hashcode值。虽然不能根据hashcode值判断两个对象是否相等但是可以直接根据hashcode值判断两个对象不等如果两个对象的hashcode值不等则必定是两个不同的对象。如果要判断两个对象是否真正相等必须通过equals方法。思考一下下面问题使用HashMap存储对象对key进行哈希算法可能会出现碰撞那么如何解决碰撞呢15.哈希冲突的解决什么是哈希冲突对不同的关键字可能得到同一散列地址即key1≠key2而f(key1)f(key2)这种现象称hash冲突。即key1通过f(key1)得到散列地址去存储key1同理key2发现自己对应的散列地址已经被key1占据了。解决办法总共有四种1.开放寻址法所谓的开放定址法就是一旦发生了冲突就去寻找下一个空的散列地址只要散列表足够大空的散列地址总能找到并将记录存入 。开放寻址法Hi(H(key) di) MOD m,i1,2,…k(km-1)其中H(key)为散列函数m为散列表长di为增量序列可有下列三种取法1)di1,2,3,…m-1称线性探测再散列2)di1^2,(-1)^2,2^2,(-2)^2,(3)^2,…±(k)^2,(km/2)称二次探测再散列3)di伪随机数序列称伪随机探测再散列。用开放定址法解决冲突的做法是当冲突发生时使用某种探测技术线性探测法、二次探测法解决线性探测的堆积问题、随机探测法和二次探测原理一致不一样的是二次探测以定值跳跃而随机探测的散列地址跳跃长度是不定值在散列表中形成一个探测序列。沿此序列逐个单元地查找直到找到给定的关键字或者碰到一个开放的地址即该地址单元为空为止插入即可。2.再哈希再哈希法又叫双哈希法有多个不同的Hash函数当发生冲突时使用第二个第三个….等哈希函数去计算地址直到无冲突。虽然不易发生聚集但是增加了计算时间。3.链地址法(Java HashMap就是这么做的)链地址法的基本思想是每个哈希表节点都有一个next指针多个哈希表节点可以用next指针构成一个单向链表将所有关键字为同义词的结点链接在同一个单链表中。​​​​​​​建立一个公共溢出区showWEIBO.COM/ttarticle/p/show?id2309405283732931608887这种方法的基本思想是将哈希表分为基本表和溢出表两部分凡是和基本表发生冲突的元素一律填入溢出表。