哈希加密算法原理（常用的哈希加密算法）
哈希加密算法原理（常用的哈希加密算法）
散列表,它是基于高速存取的角度设计的，也是一种典型的“空间换时间”的做法。顾名思义，该数据结构能够理解为一个线性表，可是当中的元素不是紧密排列的，而是可能存在空隙。
散列表（Hash table，也叫哈希表），是依据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
比方我们存储70个元素，但我们可能为这70个元素申请了100个元素的空间。70/100=0.7，这个数字称为负载因子。
我们之所以这样做，也是为了“高速存取”的目的。我们基于一种结果尽可能随机平均分布的固定函数H为每一个元素安排存储位置，这样就能够避免遍历性质的线性搜索，以达到高速存取。可是因为此随机性，也必定导致一个问题就是冲突。
所谓冲突，即两个元素通过散列函数H得到的地址同样，那么这两个元素称为“同义词”。这类似于70个人去一个有100个椅子的饭店吃饭。散列函数的计算结果是一个存储单位地址，每一个存储单位称为“桶”。设一个散列表有m个桶，则散列函数的值域应为[0,m-1]。
扩展资料:
SHA家族的五个算法，分别是SHA-1、SHA-224、SHA-256、SHA-384，和SHA-512，由美国国家安全局（NSA）所设计，并由美国国家标准与技术研究院（NIST）发布；是美国的政府标准。后四者有时并称为SHA-2。
SHA-1在许多安全协定中广为使用，包括TLS和SSL、PGP、SSH、S/MIME和IPsec，曾被视为是MD5（更早之前被广为使用的杂凑函数）的后继者。但SHA-1的安全性如今被密码学家严重质疑；
虽然至今尚未出现对SHA-2有效的攻击，它的算法跟SHA-1基本上仍然相似；因此有些人开始发展其他替代的杂凑算法。
应用
SHA-1, SHA-224, SHA-256, SHA-384 和 SHA-512 都被需要安全杂凑算法的美国联邦政府所应用，他们也使用其他的密码算法和协定来保护敏感的未保密资料。FIPS PUB 180-1也鼓励私人或商业组织使用 SHA-1 加密。Fritz-chip 将很可能使用 SHA-1 杂凑函数来实现个人电脑上的数位版权管理。
首先推动安全杂凑算法出版的是已合并的数位签章标准。
SHA 杂凑函数已被做为 SHACAL 分组密码算法的基础。
参考资料:百度百科-sha家族
引言
将任意长度的二进制字符串映射为定长二进制字符串的映射规则我们称为散列（hash）算法，又叫哈希（hash）算法，而通过原始数据映射之后得到的二进制值称为哈希值。哈希表（hash表）结构是哈希算法的一种应用，也叫散列表。用的是数组支持按照下标随机访问数据的特性扩展、演化而来。可以说没有数组就没有散列表。
哈希算法主要特点
从哈希值不能反向推导原始数据，也叫单向哈希。
对输入数据敏感，哪怕只改了一个Bit，最后得到的哈希值也大不相同。
散列冲突的概率要小。
哈希算法执行效率要高，散列结果要尽量均衡。
哈希算法的核心应用
安全加密 ：对于敏感数据比如密码字段进行MD5或SHA加密传输。
唯一标识 ：比如图片识别，可针对图像二进制流进行摘要后MD5，得到的哈希值作为图片唯一标识。
散列函数 :是构造散列表的关键。它直接决定了散列冲突的概率和散列表的性质。不过相对哈希算法的其他方面应用，散列函数对散列冲突要求较低，出现冲突时可以通过开放寻址法或链表法解决冲突。对散列值是否能够反向解密要求也不高。反而更加关注的是散列的均匀性，即是否散列值均匀落入槽中以及散列函数执行的快慢也会影响散列表性能。所以散列函数一般比较简单，追求均匀和高效。
*负载均衡 ：常用的负载均衡算法有很多，比如轮询、随机、加权轮询。如何实现一个会话粘滞的负载均衡算法呢？可以通过哈希算法，对客户端IP地址或会话SessionID计算哈希值，将取得的哈希值与服务器列表大小进行取模运算，最终得到应该被路由到的服务器编号。这样就可以把同一IP的客户端请求发到同一个后端服务器上。
*数据分片 ：比如统计1T的日志文件中“搜索关键词”出现次数该如何解决？我们可以先对日志进行分片，然后采用多机处理，来提高处理速度。从搜索的日志中依次读取搜索关键词，并通过哈希函数计算哈希值，然后再跟n(机器数)取模，最终得到的值就是应该被分到的机器编号。这样相同哈希值的关键词就被分到同一台机器进行处理。每台机器分别计算关键词出现的次数，再进行合并就是最终结果。这也是MapReduce的基本思想。再比如图片识别应用中给每个图片的摘要信息取唯一标识然后构建散列表，如果图库中有大量图片，单机的hash表会过大，超过单机内存容量。这时也可以使用分片思想，准备n台机器，每台机器负责散列表的一部分数据。每次从图库取一个图片，计算唯一标识，然后与机器个数n求余取模，得到的值就是被分配到的机器编号，然后将这个唯一标识和图片路径发往对应机器构建散列表。当进行图片查找时，使用相同的哈希函数对图片摘要信息取唯一标识并对n求余取模操作后，得到的值k，就是当前图片所存储的机器编号，在该机器的散列表中查找该图片即可。实际上海量数据的处理问题，都可以借助这种数据分片思想，突破单机内存、CPU等资源限制。
*分布式存储 ：一致性哈希算法解决缓存等分布式系统的扩容、缩容导致大量数据搬移难题。
JDK集合工具实现 ：HashMap、 LinkedHashMap、ConcurrentHashMap、TreeMap等。Map实现类源码分析，详见
总结
本文从哈希算法的原理及特点，总结了哈希算法的常见应用场景。
其中基于余数思想和同余定理实现的哈希算法（除留取余法），广泛应用在分布式场景中（散列函数、数据分片、负载均衡）。由于组合数学中的“鸽巢”原理，理论上不存在完全没有冲突的哈希算法。（PS:“鸽巢”原理是指有限的槽位，放多于槽位数的鸽子时，势必有不同的鸽子落在同一槽内，即冲突发生。同余定理：如果a和b对x取余数操作时a%x = b%x，则a和b同余）
构造哈希函数的常规方法有：数据分析法、直接寻址法、除留取余法、折叠法、随机法、平方取中法等 。
常规的解决哈希冲突方法有开放寻址法（线性探测、再哈希）和链表法。JDK中的HashMap和LinkedHashMap均是采用链表法解决哈希冲突的。链表法适合大数据量的哈希冲突解决，可以使用动态数据结构（比如：跳表、红黑树等）代替链表，防止链表时间复杂度过度退化导致性能下降；反之开放寻址法适合少量数据的哈希冲突解决。
MD5即Message-Digest Algorithm 5（信息摘要算法5），是计算机广泛使用的散列算法之一。经MD2、MD3和MD4发展而来，诞生于20世纪90年代初。用于确保信息传输完整一致。虽然已被破解，但仍然具有较好的安全性，加之可以免费使用，所以仍广泛运用于数字签名、文件完整性验证以及口令加密等领域。
算法原理：
散列算法得到的结果位数是有限的，比如MD5算法计算出的结果字长为128位，意味着只要我们穷举2^128次，就肯定能得到一组碰撞，下面让我们来看看一个真实的碰撞案例。我们之所以说MD5过时，是因为它在某些时候已经很难表现出散列算法的某些优势——比如在应对文件的微小修改时，散列算法得到的指纹结果应当有显著的不同，而下面的程序说明了MD5并不能实现这一点。
而诸如此类的碰撞案例还有很多，上面只是原始文件相对较小的一个例子。事实上现在我们用智能手机只要数秒就能找到MD5的一个碰撞案例，因此，MD5在数年前就已经不被推荐作为应用中的散列算法方案，取代它的是SHA家族算法，也就是安全散列算法（Secure Hash Algorithm，缩写为SHA）。
SHA实际包括有一系列算法，分别是SHA-1、SHA-224、SHA-256、SHA-384以及SHA-512。而我们所说的SHA2实际是对后面4中的统称。各种SHA算法的数据比较如下表，其中的长度单位均为位：
MD5和SHA1，它们都有4个逻辑函数，而在SHA2的一系列算法中都采用了6个逻辑函数。
以SHA-1为例，算法包括有如下的处理过程：
和MD5处理输入方式相同
经过添加位数处理的明文，其长度正好为512位的整数倍，然后按512位的长度进行分组，可以得到一定数量的明文分组，我们用Y 0 ，Y 1 ，……Y N-1 表示这些明文分组。对于每一个明文分组，都要重复反复的处理，这些与MD5都是相同的。
而对于每个512位的明文分组，SHA1将其再分成16份更小的明文分组，称为子明文分组，每个子明文分组为32位，我们且使用M[t]（t= 0, 1,……15）来表示这16个子明文分组。然后需要将这16个子明文分组扩充到80个子明文分组，我们将其记为W[t]（t= 0, 1,……79），扩充的具体方法是：当0≤t≤15时，Wt = Mt；当16≤t≤79时，Wt = ( W t-3 ⊕ W t-8 ⊕ W t-14 ⊕ W t-16 ) 1，从而得到80个子明文分组。
所谓初始化缓存就是为链接变量赋初值。前面我们实现MD5算法时，说过由于摘要是128位，以32位为计算单位，所以需要4个链接变量。同样SHA-1采用160位的信息摘要，也以32位为计算长度，就需要5个链接变量。我们记为A、B、C、D、E。其初始赋值分别为：A = 0x67452301、B = 0xEFCDAB89、C = 0x98BADCFE、D = 0x10325476、E = 0xC3D2E1F0。
如果我们对比前面说过的MD5算法就会发现，前4个链接变量的初始值是一样的，因为它们本来就是同源的。
经过前面的准备，接下来就是计算信息摘要了。SHA1有4轮运算，每一轮包括20个步骤，一共80步，最终产生160位的信息摘要，这160位的摘要存放在5个32位的链接变量中。
在SHA1的4论运算中，虽然进行的就具体操作函数不同，但逻辑过程却是一致的。首先，定义5个变量，假设为H0、H1、H2、H3、H4，对其分别进行如下操作：
（A）、将A左移5为与 函数的结果求和，再与对应的子明文分组、E以及计算常数求和后的结果赋予H0。
（B）、将A的值赋予H1。
（C）、将B左移30位，并赋予H2。
（D）、将C的值赋予H3。
（E）、将D的值赋予H4。
（F）、最后将H0、H1、H2、H3、H4的值分别赋予A、B、C、D
这一过程表示如下：
而在4轮80步的计算中使用到的函数和固定常数如下表所示：
经过4轮80步计算后得到的结果，再与各链接变量的初始值求和，就得到了我们最终的信息摘要。而对于有多个明文分组的，则将前面所得到的结果作为初始值进行下一明文分组的计算，最终计算全部的明文分组就得到了最终的结果。
通过之前的学习，我们已经了解了哈希函数在散列表中的应用，哈希函数就是哈希算法的一个应用。那么在这里给出哈希的定义： 将任意长度的二进制值串映射为固定长度的二进制值串，这个映射规则就是哈希算法，得到的二进制值串就是哈希值 。
要设计一个好的哈希算法并不容易，它应该满足以下几点要求：
哈希算法的应用非常广泛，在这里就介绍七点应用：
有很多著名的哈希加密算法：MD5、SHA、DES...它们都是通过哈希进行加密的算法。
对于加密的哈希算法来说，有两点十分重要：一是很难根据哈希值反推导出原始数据；二是散列冲突的概率要很小。
当然，哈希算法不可能排除散列冲突的可能，这用数学中的 鸽巢原理 就可以很好解释。以MD5算法来说，得到的哈希值为一个 128 位的二进制数，它的数据容量最多为 2 128 bit，如果超过这个数据量，必然会出现散列冲突。
在加密解密领域没有绝对安全的算法，一般来说，只要解密的计算量极其庞大，我们就可以认为这种加密方法是较为安全的。
假设我们有100万个图片，如果我们在图片中寻找某一个图片是非常耗时的，这是我们就可以使用哈希算法的原理为图片设置唯一标识。比如，我们可以从图片的二进制码串开头取100个字节，从中间取100个字节，从结尾取100个字节，然后将它们合并，并使用哈希算法计算得到一个哈希值，将其作为图片的唯一标识。
使用这个唯一标识判断图片是否在图库中，这可以减少甚多工作量。
在传输消息的过程中，我们担心通信数据被人篡改，这时就可以使用哈希函数进行数据校验。比如BT协议中就使用哈希栓发进行数据校验。
在散列表那一篇中我们就讲过散列函数的应用，相比于其它应用，散列函数对于散列算法冲突的要求低很多（我们可以通过开放寻址法或链表法解决冲突），同时散列函数对于散列算法是否能逆向解密也并不关心。
散列函数比较在意函数的执行效率，至于其它要求，在之前的我们已经讲过，就不再赘述了。
接下来的三个应用主要是在分布式系统中的应用
复杂均衡的算法很多，如何实现一个会话粘滞的负载均衡算法呢？也就是说，我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。
最简单的办法是我们根据客户端的 IP 地址或会话 ID 创建一个映射关系。但是这样很浪费内存，客户端上线下线，服务器扩容等都会导致映射失效，维护成本很大。
借助哈希算法，我们可以很轻松的解决这些问题：对客户端的 IP 地址或会话 ID 计算哈希值，将取得的哈希值域服务器的列表的大小进行取模运算，最后得到的值就是被路由到的服务器的编号。
假设有一个非常大的日志文件，里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？
分析一下，这个问题有两个难点：一是搜索日志很大，没办法放到一台机器的内存中；二是如果用一台机器处理这么大的数据，处理时间会很长。
针对这两个难点，我们可以先对数据进行分片，然后使用多台机器处理，提高处理速度。具体思路：使用 n 台机器并行处理，从日志文件中读出每个搜索关键词，通过哈希函数计算哈希值，然后用 n 取模，最终得到的值就是被分配的机器编号。
这样，相同的关键词被分配到了相同的机器上，不同机器只要记录属于自己那部分的关键词的出现次数，最终合并不同机器上的结果即可。
针对这种海量数据的处理问题，我们都可以采用多机分布式处理。借助这种分片思路，可以突破单机内存、CPU等资源的限制。
处理思路和上面出现的思路类似：对数据进行哈希运算，对机器数取模，最终将存储数据（可能是硬盘存储，或者是缓存分配）分配到不同的机器上。
你可以看一下上图，你会发现之前存储的数据在新的存储规则下全部失效，这种情况是灾难性的。面对这种情况，我们就需要使用一致性哈希算法。
哈希算法是应用非常广泛的算法，你可以回顾上面的七个应用感受一下。
其实在这里我想说的是一个思想： 用优势弥补不足 。
例如，在计算机中，数据的计算主要依赖 CPU ，数据的存储交换主要依赖内存。两者一起配合才能实现各种功能，而两者在性能上依然无法匹配，这种差距主要是： CPU运算性能对内存的要求远高于现在的内存能提供的性能。
也就是说，CPU运算很快，内存相对较慢，为了抹平这种差距，工程师们想了很多方法。在我看来，散列表的使用就是利用电脑的高计算性能（优势）去弥补内存速度（不足）的不足，你仔细思考散列表的执行过程，就会明白我的意思。
以上就是哈希的全部内容
