数据结构 -Hash 常见操作实践
数据结构-Hash 常见操作实践
目录介绍
01.什么是哈希算法
02.哈希算法的应用
03.安全加密的场景
04.唯一标识的场景
05.数据校验的场景
06.散列函数的场景
07.Git 版本的控制
08.云存储文件场景
09.哈希算法的总结
10.哈希算法的特点
11.哈希算法的实践
12.常用哈希码算法
13.Map 哈希的算法
14.理解 HashCode
15.哈希冲突的解决
16.问题思考的答疑
01.什么是哈希算法
哈希算法历史悠久
业界著名的哈希算法也很多，比如 MD5、SHA 等。在平时的开发中，基本上都是拿现成的直接用。今天不会重点剖析哈希算法的原理，也不会教你如何设计一个哈希算法，而是从实战角度告诉你，在实际开发中，我们该如何用哈希算法解决问题。
什么是哈希算法，用一句话就可以概括了。
将任意长度的二进制值串映射为固定长度的二进制值串，这个映射规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。
但是，要设计一个优秀的哈希算法并不容易，我了需要满足的几点要求：
从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；
散列总被的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
哈希算法的执行效率尽量高效，针对较长的文本，也能快速计算出哈希值。
拿 MD5 这种哈希算法具体说明下，比如计算这两个文本的 MD5 哈希值——“今天我来讲哈希算法”、“jiajia"。得到的两串毫无规律的字符串（MD5 的哈希值是 128 位的 Bit 长度，便于表示，转化为 16 进制编码）。可以看出，无论文本的长度是多少，得到的哈希值长度是相同的，而且看起来像一堆随机数，完全没有规律。
试试两个很相似的文本，虽然只有一个标点的差别，但哈希值是完全不相同的。同时根据哈希值，是很难反向推导出原始数据。
哈希算法要处理的文本可能是各种各样的。
比如，对于非常长的文本，如果哈希算法的计算时间很长，那就只能停留在理论研究的层面，很难应用到实际软件开发中。
比如，把今天的这篇包含 4000 多个汉字的文章，用 MD5 计算哈希值，用不了 1ms 的时间。
02.哈希算法的应用
Hash 有哪些流行的算法
目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2。
哈希算法主要有哪些
MD5 算法：MD5，MD5+盐
SHA 算法：包含 5 个算法，分别是 SHA-1、SHA-224、SHA-256、SHA-384 和 SHA-512，后四者并称为 SHA-2。
哈希算法的应用非常非常多，选了最觉的七个
分别是安全加密、唯一标识、数据校验、散列函数、Git 版本控制、云存储、数据分片。
03.安全加密的场景
说到哈希算法的应用，最先想到的应该是安全加密。
最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和 SHA（Secure Hash Algorithm，安全散列算法）。除了这两个之外，当然还有很多其他的加密方法，比如 DES（Advance 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.哈希算法的实践
提供几个简单的概念供大家参考
作为散列算法，首要的功能就是要使用一种算法把原有的体积很大的文件信息用若干个字符来记录，还要保证每一个字节都会对最终结果产生影响。
那么大家也许已经想到了，求模这种算法就能满足我们的需要。事实上，求模算法作为一种不可逆的计算方法，已经成为了整个现代密码学的根基。
只要是涉及到计算机安全和加密的领域，都会有模计算的身影。
散列算法也并不例外，一种最原始的散列算法就是单纯地选择一个数进行模运算，比如以下程序。
在散列函数中加入一个异或过程
在进行计算之前对原始文本进行修改，或是加入额外的运算过程（如移位）
上面的算法是不是很简单？
事实上，常用算法 MD5 和 SHA1，其本质算法就是这么简单，只不过会加入更多的循环和计算，来加强散列函数的可靠性。
12.常用哈希码算法
下面给出在 Java 中几个常用的哈希码(hashCode)的算法。
Object 类的 hashCode. 返回对象的经过处理后的内存地址，由于每个对象的内存地址都不一样，所以哈希码也不一样。这个是 native 方法，取决于 JVM 的内部设计，一般是某种 C 地址的偏移。
String 类的 hashCode. 根据 String 类包含的字符串的内容，根据一种特殊算法返回哈希码，只要字符串的内容相同，返回的哈希码也相同。
Integer 等包装类，返回的哈希码就是 Integer 对象里所包含的那个整数的数值，例如 Integer i1=new Integer(100), i1.hashCode 的值就是 100 。由此可见，2 个一样大小的 Integer 对象，返回的哈希码也一样。
int，char 这样的基础类，它们不需要 hashCode，如果需要存储时，将进行自动装箱操作，计算方法同上。
13.Map 哈希的算法
对 key 进行 Hash 计算
在 JDK8 中，由于使用了红黑树来处理大的链表开销，所以 hash 这边可以更加省力了，只用计算 hashCode 并移动到低位就可以了。
获取到数组的 index 的位置。计算了 Hash，我们现在要把它插入数组中了
14.理解 HashCode
HashCode 也是哈希算法的一种
HashCode 是 Object 的一个方法，hashCode 方法返回一个 hash code 值，且这个方法是为了更好的支持 hash 表，比如 String，Set，HashTable、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,i=1,2,…，k(k<=m-1)，其中 H(key)为散列函数，m 为散列表长，di 为增量序列，可有下列三种取法：
1)．di=1,2,3,…，m-1，称线性探测再散列；
2)．di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…，±(k)^2,(k<=m/2)称二次探测再散列；
3)．di=伪随机数序列，称伪随机探测再散列。
用开放定址法解决冲突的做法是：当冲突发生时，使用某种探测技术（线性探测法、二次探测法（解决线性探测的堆积问题）、随机探测法（和二次探测原理一致，不一样的是：二次探测以定值跳跃，而随机探测的散列地址跳跃长度是不定值））在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止插入即可。
2.再哈希
再哈希法又叫双哈希法，有多个不同的 Hash 函数，当发生冲突时，使用第二个，第三个，….，等哈希函数去计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。
3.链地址法(Java HashMap 就是这么做的)
链地址法的基本思想是：每个哈希表节点都有一个 next 指针，多个哈希表节点可以用 next 指针构成一个单向链表，将所有关键字为同义词的结点链接在同一个单链表中。
4.建立一个公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
16.问题思考的答疑
1.如何防止数据库中的用户信息被脱库？你会如何存储用户密码这么重要的数据吗？
一.使用 MD5 进行加密
二.字典攻击：如果用户信息被“脱库”，黑客虽然拿到的是加密之后的密文，但可以通过“猜”的方式来破解密码，这是因为，有些用户的密码太简单。
三.针对字典攻击，我们可以引入一个盐（salt），跟用户密码组合在一起，增加密码的复杂度。
四.最好对密码验证次数进行限时间段限制。
2.在实际开发中，我们应该如何用哈希算法解决问题？
在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。
3.为何银行密码 6 个数字不易破解
用户设置一个简单密码，进行加密后就变成 32 位，64 位，128 位等密码了，然后在网上传输就安全多了，一般这种加密密码和时间戳也正相关。截获了也用处不大，就是把时间参数传递过去了，服务器也和本地时间比对的，超过 3 分钟他们就认为是非法消息，它是不断变化的，破解很困难。
很多网站都有输入次数限制，所以对很多网站的密码破解都集中在加密算法上，很少进行字典式攻击了，当然黑客找到网站的漏洞，绕过次数限制，也会进行字典式轰炸。
综合库：https://github.com/yangchong211/YCAppTool
视频播放器：https://github.com/yangchong211/YCVideoPlayer
综合博客汇总：https://github.com/yangchong211/YCBlogs
版权声明: 本文为 InfoQ 作者【杨充】的原创文章。
原文链接:【http://xie.infoq.cn/article/dfe0648150cdfbffeda188889】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
还未添加个人签名 2018-07-30 加入
还未添加个人简介
评论