[区块链] 密码学中Hash算法（基础）

在介绍Hash算法之前，先给大家来个数据结构中对hash表（散列表）的简单解释，然后我再逐步深入，讲解一下hash算法。

一、Hash原理——基础篇

1.1 概念

　　哈希表就是一种以键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。

　　哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

　　使用哈希查找有两个步骤:

　　1. 使用哈希函数将被查找的键转换为数组的索引。在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突

　　2. 处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法，本文后面会介绍拉链法和线性探测法。

　　哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

　　在Hash表中，记录在表中的位置和其关键字之间存在着一种确定的关系。这样我们就能预先知道所查关键字在表中的位置，从而直接通过下标找到记录。使ASL趋近与0. （ASL：Average Search Length，平均查找长度）

1) 哈希(Hash)函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；

2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1！=key2，而 f (key1) = f(key2)；

3) 只能尽量减少冲突而不能完全避免冲突，这是因为通常关键字集合比较大，其元素包括所有可能的关键字，而地址集合的元素仅为哈希表中的地址值。

在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突” 的方法。所以，下文我们从这两方面分别来介绍：

1.2 Hash构造函数的方法

1.2.1 直接定址法：

　　直接定址法是以数据元素关键字k本身或它的线性函数作为它的哈希地址，即：H（k）=k 或 H（k）=a * k + b ； (其中a,b为常数)

　　例1，有一个人口统计表，记录了从1岁到100岁的人口数目，其中年龄作为关键字，哈希函数取关键字本身，如图(1)：

地址	A₁	A₂	……	A₉₉	A₁₀₀
年龄	1	2	……	99	100
人数	980	800	……	495	107

　　可以看到，当需要查找某一年龄的人数时，直接查找相应的项即可。如查找99岁的老人数，则直接读出第99项即可。

地址	A0	A1	……	A₉₉	A₁₀₀
年份	1980	1981	……	1999	2000
人数	980	800	……	495	107

　　如果我们要统计的是80后出生的人口数，如上表所示，那么我们队出生年份这个关键字可以用年份减去1980来作为地址，此时f(key)=key-1980

　　这种哈希函数简单，并且对于不同的关键字不会产生冲突，但可以看出这是一种较为特殊的哈希函数，实际生活中，关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费，因此这种方法适应性并不强。

　　此法仅适合于：地址集合的大小 = 关键字集合的大小，其中a和b为常数。

1.2.2 数字分析法：

　　假设关键字集合中的每个关键字都是由 s 位数字组成 (u₁, u₂, …, u_s)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。

数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时，可以通过对关键字的各位进行分析，丢掉分布不均匀的位，作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。

　　例2，要构造一个数据元素个数n=80,哈希长度m=100的哈希表。不失一般性，我们这里只给出其中8个关键字进行分析，8个关键字如下所示：

K1=61317602 K2=61326875 K3=62739628 K4=61343634

K5=62706815 K6=62774638 K7=61381262 K8=61394220

分析上述8个关键字可知，关键字从左到右的第1、2、3、6位取值比较集中，不宜作为哈希地址，剩余的第4、5、7、8位取值较均匀，可选取其中的两位作为哈希地址。设选取最后两位作为哈希地址，则这8个关键字的哈希地址分别为：2，75，28，34，15，38，62，20。

　　此法适于:能预先估计出全体关键字的每一位上各种数字出现的频度。

1.2.3 折叠法：

　　将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：移位叠加:将分割后的几部分低位对齐相加；边界叠加:从一端沿分割界来回折叠，然后对齐相加。

所谓折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位），这方法称为折叠法。这种方法适用于关键字位数较多，而且关键字中每一位上数字分布大致均匀的情况。

　　折叠法中数位折叠又分为移位叠加和边界叠加两种方法，移位叠加是将分割后是每一部分的最低位对齐，然后相加；边界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。

　　例3，当哈希表长为1000时，关键字key=110108331119891，允许的地址空间为三位十进制数，则这两种叠加情况如图：

       移位叠加                              边界叠加

       8 9 1                                     8 9 1

       1 1 9                                     9 1 1

       3 3 1                                     3 3 1

       1 0 8                                     8 0 1

    +  1 1 0                                   + 1 1 0              

   (1) 5 5 9                                  (3)0 4 4

　　用移位叠加得到的哈希地址是559，而用边界叠加所得到的哈希地址是44。如果关键字不是数值而是字符串，则可先转化为数。转化的办法可以用ASCⅡ字符或字符的次序值。

　　此法适于：关键字的数字位数特别多。

1.2.4 平方取中法

　　这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方，然后根据可使用空间的大小，选取平方数是中间几位为哈希地址。

　　哈希函数 H(key)=key²的中间几位”因为这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。

　　例4，若设哈希表长为1000则可取关键字平方值的中间三位，如图所示：

关键字	关键字的平方	哈希函数值
1234	1522756	227
2143	4592449	924
4132	17073424	734
3214	10329796	297

　　此法适于:关键字中的每一位都有某些数字重复出现频度很高的现象

1.2.5 减去法

　　减去法是数据的键值减去一个特定的数值以求得数据存储的位置。

　　例5，公司有一百个员工，而员工的编号介于1001到1100，减去法就是员工编号减去1000后即为数据的位置。编号1001员工的数据在数据中的第一笔。编号1002员工的数据在数据中的第二笔…依次类推。从而获得有关员工的所有信息，因为编号1000以前并没有数据，所有员工编号都从1001开始编号。

1.2.6 基数转换法

　　将十进制数X看作其他进制，比如十三进制，再按照十三进制数转换成十进制数，提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数，并且两个基数应该是互素的。

　　例6：Hash(80127429)=(80127429)₁₃=8*13⁷+0*13⁶+1*13⁵+2*13⁴+7*13³+4*13²+2*13¹+9=(502432641)₁₀如果取中间三位作为哈希值，得Hash（80127429）=432

为了获得良好的哈希函数，可以将几种方法联合起来使用，比如先变基，再折叠或平方取中等等，只要散列均匀，就可以随意拼凑。

1.2.7 除留余数法：

　　取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址，即设定哈希函数为 Hash(key)=key mod p (p≤m)，其中，除数p称作模。

　　除留余数法不仅可以对关键字直接取模，也可以在折叠、平方取中等运算后取模。对于除留余数法求哈希地址，关键在于模p的选择。使得数据元素集合中每一个关键字通过该哈希函数映射到内存单元的任意地址上的概率相等，从而尽可能减少发生哈希冲突的可能性。

　　理论研究表明，除留余数法的模p取不大于表长且最接近表长m素数时效果最好，且p最好取1.1n～1.7n之间的一个素数（n为存在的数据元素个数）。例如：当n=7时，p最好取11、13等素数。又例下图：

表长m	8	16	32	64	128	256	512	1000
模p	7	13	31	61	127	251	503	997

　　由于除留余数法的地址计算方法简单，而且在许多情况下效果较好。

　　例7，公司有236个员工，而员工编号介于1000到9999，除留余数法就是员工编号除以数据个数236后，去余数即为数据的位置。编号5428员工的数据（编号5428除以236取余数得0）放数据中的第一笔，编号3512员工数据（编号3512除以236取余数得8）放数据中的第九笔…依次类推。

1.2.8 随机数法：

　　亦称为“乘余取整法”。随机乘数法使用一个随机实数f,0≤f<1,乘积f*k的分数部分在0～1之间，用这个分数部分的值与n（哈希表的长度）相乘，乘积的整数部分就是对应的哈希值，显然这个哈希值落在0～n-1之间。其表达公式为：Hash(k)=「n*(f*k%1)」其中“f*k%1”表示f*k 的小数部分，即f*k%1=f*k-「f*k」[5] ↑

　　例8，对下列关键字值集合采用随机乘数法计算哈希值，随机数f=0.103149002 哈希表长度n=100得图(6)：

k	f*k	n((fk)的小数部分)	Hash(k)
319426	32948.47311	47.78411	47
718309	74092.85648	86.50448	86
629443	64926.41727	42.14427	42
919697	84865.82769	83.59669	83

　　此方法的优点是对n的选择不很关键。通常若地址空间为p位就是选n=2p.Knuth对常数f的取法做了仔细的研究，他认为f取任何值都可以，但某些值效果更好。如f=（-1）/2=0.6180329…比较理想。

1.2.9 随机乘数法

　　例9，对下列关键字值集合采用随机乘数法计算哈希值，随机数f=0.103149002 哈希表长度n=100得图：

k	f*k	n((fk)的小数部分)	Hash(k)
319426	32948.47311	47.78411	47
718309	74092.85648	86.50448	86
629443	64926.41727	42.14427	42
919697	84865.82769	83.59669	83

1.2.10 字符串数值哈希法

　　在很都情况下关键字是字符串，因此这样对字符串设计Hash函数是一个需要讨论的问题。下列函数是取字符串前10个字符来设计的哈希函数

Int Hash _ char (char *X)

{

  　　int I ,sum 

 　　 i=0;

 　　 while (i 10 && X[i]) 

  　　　　Sum +=X[i++];

 　　 sum%=N;      //N是记录的条数

  }

这种函数把字符串的前10个字符的ASCⅡ值之和对N取摸作为Hash地址，只要N较小，Hash地址将较均匀分布[0，N]区间内，因此这个函数还是可用的。对于N很大的情形，可使用下列函数

int ELFhash (char *key )

{

　　 Unsigned long h=0,g;

　　whie (*key)

　　{ 

　　　　h=(h<<4)+ *key;

　　　　key++;

　　　　g=h & 0 xF0000000L;

　　　　if (g) h^=g>>24;

　　　　h & =～g;

　　}

　　h=h % N

　　return （h）;

}

这个函数称为ELFHash(Exextable and Linking Format ,ELF,可执行链接格式)函数。它把一个字符串的绝对长度作为输入，并通过一种方式把字符的十进制值结合起来，对长字符串和短字符串都有效，这种方式产生的位置不可能不均匀分布。

1.2.11 旋转法

　　旋转法是将数据的键值中进行旋转。旋转法通常并不直接使用在哈希函数上，而是搭配其他哈希函数使用。

　　例11，某学校同一个系的新生（小于100人）的学号前5位数是相同的，只有最后2位数不同，我们将最后一位数，旋转放置到第一位，其余的往右移。

新生学号	旋转过程	旋转后的新键值
5062101	5062101	1506210
5062102	5062102	2506210
5062103	5062103	3506210
5062104	5062104	4506210
5062105	5062105	5506210

　　运用这种方法可以只输入一个数值从而快速地查到有关学生的信息。

　　在实际应用中，应根据具体情况，灵活采用不同的方法，并用实际数据测试它的性能，以便做出正确判定。通常应考虑以下五个因素：

　　1.计算哈希函数所需时间（简单）

　　2.关键字的长度

　　3.哈希表大小

　　4.关键字分布情况

　　5.记录查找频率

1.3 Hash处理冲突方法

　　通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：

1.3.1 开放定址法

　　所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入
公式为：fi(key) = (f(key)+di) MOD m (di=1,2,3,……,m-1)
　　※ 用开放定址法解决冲突的做法是：当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者
碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表
中无待查的关键字，即查找失败。
　　比如说，我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34},表长为12。我们用散列函数f(key) = key mod l2
　　当计算前S个数{12,67,56,16,25}时，都是没有冲突的散列地址，直接存入：
这里写图片描述
　　计算key = 37时，发现f(37) = 1，此时就与25所在的位置冲突。
　　于是我们应用上面的公式f(37) = (f(37)+1) mod 12 = 2。于是将37存入下标为2的位置：

1.3.2 再哈希法

　　再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数
计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。

1.3.3 链地址法

　　链地址法的基本思想是：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向
　　链表连接起来，如：
键值对k2, v2与键值对k1, v1通过计算后的索引值都为2，这时及产生冲突，但是可以通道next指针将k2, k1所在的节点连接起来，这样就解决了哈希的冲突问题
这里写图片描述

1.3.4 建立公共溢出区：

　　这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

二、Hash算法——进阶篇

2.1 Hash是什么，它的作用

　　先举个例子。我们每个活在世上的人，为了能够参与各种社会活动，都需要一个用于识别自己的标志。也许你觉得名字或是身份证就足以代表你这个人，但是这种代表性非常脆弱，因为重名的人很多，身份证也可以伪造。最可靠的办法是把一个人的所有基因序列记录下来用来代表这个人，但显然，这样做并不实际。而指纹看上去是一种不错的选择，虽然一些专业组织仍然可以模拟某个人的指纹，但这种代价实在太高了。

　　而对于在互联网世界里传送的文件来说，如何标志一个文件的身份同样重要。比如说我们下载一个文件，文件的下载过程中会经过很多网络服务器、路由器的中转，如何保证这个文件就是我们所需要的呢？我们不可能去一一检测这个文件的每个字节，也不能简单地利用文件名、文件大小这些极容易伪装的信息，这时候，我们就需要一种指纹一样的标志来检查文件的可靠性，这种指纹就是我们现在所用的Hash算法(也叫散列算法)。

　　散列算法（Hash Algorithm），又称哈希算法，杂凑算法，是一种从任意文件中创造小的数字「指纹」的方法。与指纹一样，散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。

　　这种标志有何意义呢？之前文件下载过程就是一个很好的例子，事实上，现在大部分的网络部署和版本控制工具都在使用散列算法来保证文件可靠性。而另一方面，我们在进行文件系统同步、备份等工具时，使用散列算法来标志文件唯一性能帮助我们减少系统开销，这一点在很多云存储服务器中都有应用。

　　当然，作为一种指纹，散列算法最重要的用途在于给证书、文档、密码等高安全系数的内容添加加密保护。这一方面的用途主要是得益于散列算法的不可逆性，这种不可逆性体现在，你不仅不可能根据一段通过散列算法得到的指纹来获得原有的文件，也不可能简单地创造一个文件并让它的指纹与一段目标指纹相一致。散列算法的这种不可逆性维持着很多安全框架的运营，而这也将是本文讨论的重点。

2.2 Hash算法有什么特点

　　一个优秀的 hash 算法，将能实现：

正向快速：给定明文和 hash 算法，在有限时间和有限资源内能计算出 hash 值。
逆向困难：给定（若干） hash 值，在有限时间内很难（基本不可能）逆推出明文。
输入敏感：原始输入信息修改一点信息，产生的 hash 值看起来应该都有很大不同。
冲突避免：很难找到两段内容不同的明文，使得它们的 hash 值一致（发生冲突）。即对于任意两个不同的数据块，其hash值相同的可能性极小；对于一个给定的数据块，找到和它hash值相同的数据块极为困难。

　　但在不同的使用场景中，如数据结构和安全领域里，其中对某一些特点会有所侧重。

2.2.1 Hash在管理数据结构中的应用

　　在用到hash进行管理的数据结构中，就对速度比较重视，对抗碰撞不太看中，只要保证hash均匀分布就可以。比如hashmap，hash值（key）存在的目的是加速键值对的查找，key的作用是为了将元素适当地放在各个桶里，对于抗碰撞的要求没有那么高。换句话说，hash出来的key，只要保证value大致均匀的放在不同的桶里就可以了。但整个算法的set性能，直接与hash值产生的速度有关，所以这时候的hash值的产生速度就尤为重要，以JDK中的String.hashCode()方法为例：

public int hashCode() {
    int h = hash;
    //hash default value : 0 
    if (h == 0 && value.length > 0) {
        //value : char storage
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

　　很简洁的一个乘加迭代运算，在不少的hash算法中，使用的是异或+加法进行迭代，速度和前者差不多。

2.2.2 Hash在在密码学中的应用

　　在密码学中，hash算法的作用主要是用于消息摘要和签名，换句话说，它主要用于对整个消息的完整性进行校验。举个例子，我们登陆知乎的时候都需要输入密码，那么知乎如果明文保存这个密码，那么黑客就很容易窃取大家的密码来登陆，特别不安全。那么知乎就想到了一个方法，使用hash算法生成一个密码的签名，知乎后台只保存这个签名值。由于hash算法是不可逆的，那么黑客即便得到这个签名，也丝毫没有用处；而如果你在网站登陆界面上输入你的密码，那么知乎后台就会重新计算一下这个hash值，与网站中储存的原hash值进行比对，如果相同，证明你拥有这个账户的密码，那么就会允许你登陆。银行也是如此，银行是万万不敢保存用户密码的原文的，只会保存密码的hash值而而已。在这些应用场景里，对于抗碰撞和抗篡改能力要求极高，对速度的要求在其次。一个设计良好的hash算法，其抗碰撞能力是很高的。以MD5为例，其输出长度为128位，设计预期碰撞概率为1/2¹²⁸，这是一个极小极小的数字——而即便是在MD5被王小云教授破解之后，其碰撞概率也非常低。而对于两个相似的字符串，MD5加密结果如下：

MD5("version1") = "966634ebf2fc135707d6753692bf4b1e";
MD5("version2") = "2e0e95285f08a07dea17e7ee111b21c8"

　　可以看到仅仅一个比特位的改变，二者的MD5值就天差地别了.

ps : 其实把hash算法当成是一种加密算法，这是不准确的，我们知道加密总是相对于解密而言的，没有解密何谈加密呢，HASH的设计以无法解为目的的。并且如果我们不附加一个随机的salt值，HASH口令是很容易被字典攻击入侵的。

2.3 Hash算法是如何实现的？

　　密码学和信息安全发展到现在，各种加密算法和散列算法已经不是只言片语所能解释得了的。在这里我们仅提供几个简单的概念供大家参考。

　　作为散列算法，首要的功能就是要使用一种算法把原有的体积很大的文件信息用若干个字符来记录，还要保证每一个字节都会对最终结果产生影响。那么大家也许已经想到了，求模这种算法就能满足我们的需要。

　　事实上，求模算法作为一种不可逆的计算方法，已经成为了整个现代密码学的根基。只要是涉及到计算机安全和加密的领域，都会有模计算的身影。散列算法也并不例外，一种最原始的散列算法就是单纯地选择一个数进行模运算，比如以下程序。

1 #  构造散列函数
2 def hash(a):
3     return a % 8
4 
5 #  测试散列函数功能
6 print(hash(233))
7 print(hash(234))
8 print(hash(235))

# 输出结果
- 1
- 2
- 3

　　很显然，上述的程序完成了一个散列算法所应当实现的初级目标：用较少的文本量代表很长的内容（求模之后的数字肯定小于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

这样处理得到的散列算法就很难发现其内部规律，也就是说，我们并不能很轻易地给出一个数，让它经过上述散列函数运算之后的结果等于4——除非我们去穷举测试。

上面的算法是不是很简单？事实上，下面我们即将介绍的常用算法MD5和SHA1，其本质算法就是这么简单，只不过会加入更多的循环和计算，来加强散列函数的可靠性。

2.4 Hash有哪些流行的算法

　　目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2。

MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。其输出为 128 位。MD4 已证明不够安全。
MD5（RFC 1321）是 Rivest 于1991年对 MD4 的改进版本。它对输入仍以 512 位分组，其输出是 128 位。MD5 比 MD4 复杂，并且计算速度要慢一点，更安全一些。MD5 已被证明不具备”强抗碰撞性”。
SHA （Secure Hash Algorithm）是一个 Hash 函数族，由 NIST（National Institute of Standards and Technology）于 1993 年发布第一个算法。目前知名的 SHA-1 在 1995 年面世，它的输出为长度 160 位的 hash 值，因此抗穷举性更好。SHA-1 设计时基于和 MD4 相同原理，并且模仿了该算法。SHA-1 已被证明不具”强抗碰撞性”。
为了提高安全性，NIST 还设计出了 SHA-224、SHA-256、SHA-384，和 SHA-512 算法（统称为 SHA-2），跟 SHA-1 算法原理类似。SHA-3 相关算法也已被提出。

　　可以看出，上面这几种流行的算法，它们最重要的一点区别就是”强抗碰撞性”。

2.5 那么，何谓Hash算法的「碰撞」？

　　你可能已经发现了，在实现算法章节的第一个例子，我们尝试的散列算法得到的值一定是一个不大于8的自然数，因此，如果我们随便拿9个数去计算，肯定至少会得到两个相同的值，我们把这种情况就叫做散列算法的「碰撞」（Collision）。

　　这很容易理解，因为作为一种可用的散列算法，其位数一定是有限的，也就是说它能记录的文件是有限的——而文件数量是无限的，两个文件指纹发生碰撞的概率永远不会是零。

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

　　随意找到一组碰撞是有可能的，只要穷举就可以。散列算法得到的指纹位数是有限的，比如MD5算法指纹字长为128位，意味着只要我们穷举21282128次，就肯定能得到一组碰撞——当然，这个时间代价是难以想象的，而更重要的是，仅仅找到一组碰撞并没有什么实际意义。更有意义的是，如果我们已经有了一组指纹，能否找到一个原始文件，让它的散列计算结果等于这组指纹。如果这一点被实现，我们就可以很容易地篡改和伪造网络证书、密码等关键信息。

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

2.5.1 MD5的实际碰撞案例

　　下面让我们来看看一个真实的碰撞案例。我们之所以说MD5过时，是因为它在某些时候已经很难表现出散列算法的某些优势——比如在应对文件的微小修改时，散列算法得到的指纹结果应当有显著的不同，而下面的程序说明了MD5并不能实现这一点。

import hashlib

#  两段HEX字节串，注意它们有细微差别
a = bytearray.fromhex("0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef")

b = bytearray.fromhex("0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef")

#  输出MD5，它们的结果一致
print(hashlib.md5(a).hexdigest())
print(hashlib.md5(b).hexdigest())

### a和b输出结果都为：
cee9a457e790cf20d4bdaa6d69f01e41
cee9a457e790cf20d4bdaa6d69f01e41

　　而诸如此类的碰撞案例还有很多，上面只是原始文件相对较小的一个例子。事实上现在我们用智能手机只要数秒就能找到MD5的一个碰撞案例，因此，MD5在数年前就已经不被推荐作为应用中的散列算法方案，取代它的是SHA家族算法，也就是安全散列算法（Secure Hash Algorithm，缩写为SHA）。

2.5.2 SHA家族算法以及SHA1碰撞

　　安全散列算法与MD5算法本质上的算法是类似的，但安全性要领先很多——这种领先型更多的表现在碰撞攻击的时间开销更大，当然相对应的计算时间也会慢一点。

　　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.6. Hash在Java中的应用

2.6.1 HashMap的复杂度

　　在介绍HashMap的实现之前，先考虑一下，HashMap与ArrayList和LinkedList在数据复杂度上有什么区别。下图是他们的性能对比图：

	获取	查找	添加/删除	空间
ArrayList	O(1)	O(1)	O(N）	O(N)
LinkedList	O(N)	O(N)	O(1)	O(N)
HashMap	O(N/Bucket_size)	O(N/Bucket_size)	O(N/Bucket_size)	O(N)

　　可以看出HashMap整体上性能都非常不错，但是不稳定，为O(N/Buckets)，N就是以数组中没有发生碰撞的元素，Buckets是因碰撞产生的链表。

注：发生碰撞实际上是非常稀少的，所以N/Bucket_size约等于1

　　HashMap是对Array与Link的折衷处理，Array与Link可以说是两个速度方向的极端，Array注重于数据的获取，而处理修改（添加/删除）的效率非常低；Link由于是每个对象都保持着下一个对象的指针，查找某个数据需要遍历之前所有的数据，所以效率比较低，而在修改操作中比较快。

2.6.2 HashMap的实现

　　本文以JDK8的API实现进行分析

2.6.2.1 对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)

0001 0101 1010 1110 1011 0111 1010 1011(363771819)
0000 0000 0000 0000 0001 0101 1010 1110(5550) XOR
--------------------------------------- =
0001 0101 1010 1110 1010 0010 0000 0101(363766277)

　　这样做可以实现了高地位更加均匀地混到一起。

　　下面给出在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，如果需要存储时，将进行自动装箱操作，计算方法同上。

2.6.2.2 获取到数组的index的位置

　　计算了Hash，我们现在要把它插入数组中了

i = (tab.length - 1) & hash；

　　通过位运算，确定了当前的位置，因为HashMap数组的大小总是2^n，所以实际的运算就是 (0xfff…ff) & hash ，这里的tab.length-1相当于一个mask，滤掉了大于当前长度位的hash，使每个i都能插入到数组中。

2.6.2.3 生成包装类

　　这个对象是一个包装类，Node

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        //getter and setter .etc.
}

2.6.2.4 插入包装类到数组

(1). 如果输入当前的位置是空的，就插进去，如图，左为插入前，右为插入后

    0           0
    |           |
    1 -> null   1 - > null
    |           |
    2 -> null   2 - > null
    |           | 
    ..-> null   ..- > null
    |           | 
    i -> null   i - > new node
    |           |
    n -> null   n - > null

(2). 如果当前位置已经有了node，且它们发生了碰撞，则新的放到前面，旧的放到后面，这叫做链地址法处理冲突。

    0           0
    |           |
    1 -> null   1 - > null
    |           |
    2 -> null   2 - > null
    |           | 
    ..-> null   ..- > null
    |           | 
    i -> old    i - > new - > old
    |           |
    n -> null   n - > null

　　我们可以发现，失败的hashCode算法会导致HashMap的性能由数组下降为链表，所以想要避免发生碰撞，就要提高hashCode结果的均匀性。

2.6.3 扩容

　　如果当表中的75%已经被占用，即视为需要扩容了

(threshold = capacity * load factor ) < size

　　它主要有两个步骤：

2.6.3.1 容量加倍

　　左移1位，就是扩大到两倍，用位运算取代了乘法运算

newCap = oldCap << 1;
newThr = oldThr << 1;

2.6.3.2 遍历计算Hash

for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        //如果发现当前有Bucket
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            //如果这里没有碰撞
            if (e.next == null)
                //重新计算Hash，分配位置
                newTab[e.hash & (newCap - 1)] = e;
            //这个见下面的新特性介绍，如果是树，就填入树
            else if (e instanceof TreeNode)
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            //如果是链表，就保留顺序....目前就看懂这点
            else { // preserve order
                Node<K,V> loHead = null, loTail = null;
                Node<K,V> hiHead = null, hiTail = null;
                Node<K,V> next;
                do {
                    next = e.next;
                    if ((e.hash & oldCap) == 0) {
                        if (loTail == null)
                            loHead = e;
                        else
                            loTail.next = e;
                        loTail = e;
                    }
                    else {
                        if (hiTail == null)
                            hiHead = e;
                        else
                            hiTail.next = e;
                        hiTail = e;
                    }
                } while ((e = next) != null);
                if (loTail != null) {
                    loTail.next = null;
                    newTab[j] = loHead;
                }
                if (hiTail != null) {
                    hiTail.next = null;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }

　　由此可以看出扩容需要遍历并重新赋值，成本非常高，所以选择一个好的初始容量非常重要。

2.6.4 扩容如何提升性能？

解决扩容损失：如果知道大致需要的容量，把初始容量设置好以解决扩容损失；
比如我现在有1000个数据，需要 1000/0.75 = 1333 个坑位，又 1024 < 1333 < 2048，所以最好使用2048作为初始容量。
解决碰撞损失：使用高效的HashCode与loadFactor，这个…由于JDK8的高性能出现，这儿问题也不大了。

2.6.5 HashMap与HashTable的主要区别

在很多的Java基础书上都已经说过了，他们的主要区别其实就是Table全局加了线程同步保护

HashTable线程更加安全，代价就是因为它粗暴的添加了同步锁，所以会有性能损失。
其实有更好的concurrentHashMap可以替代HashTable，一个是方法级，一个是Class级。

2.6.6 在Android中使用SparseArray代替HashMap

官方推荐使用SparseArray([spɑ:s][ə’reɪ],稀疏的数组)或者LongSparseArray代替HashMap。官方总结有一下几点好处：

SparseArray使用基本类型(Primitive)中的int作为Key，不需要Pair

总结

　　可以看到无论是密码学、数据结构等计算机领域，还是现实生活中的应用，到处可以看到Hash的影子。希望这篇总结的博文，可以帮助到大家更好的学习哈希算法。

　　最后要感谢一下博文的创作者，谢谢！

【时间仓促，如有错误，欢迎指正！ || 欢迎留下您的评语！大家一起探讨、学习区块链!】

【转载请注明出处！http://www.cnblogs.com/X-knight/】

Reference

本文链接：https://www.cnblogs.com/X-knight/p/9134900.html