【虾说区块链】什么是hash算法?什么是好的hash算法?

欢迎收听「虾说区块链」。现在区块链这个概念在互联网上相当火热，这里简单做一个普及，不涉及项目推广投资，单纯地对区块链相关基础知识概念作一个说明讲解。本人区块链技术爱好者，结合相关区块链资料总结整理了「虾说区块链」，也是自己一个学习笔记，涉及相关内容如理解有误，也请及时指正。

hash算法也称为散列函数算法，在区块链中应用的相当频繁，在说明hash算法之前先明确一个概念。

计算机在底层机器码是采用二进制的模式，所谓二进制简单来说就是底层以0/1来标识，所有数据传输记录都以010101的模式来存储记录，两种状态也可认为就是一个日常生活中的开关，1标识开，0标识关。那么计算机中最小的数据单位也就是这里说的0或者1，这里我们称为bit（比特或者位），8个bit组成一个字节。当然计算机中也有八进制、十六进制的表示，这里暂时不展开讨论。只明确底层一个二进制的概念。

Hash算法广泛应用于计算机信息科学领域中，也是十分基础的密码学相关知识。

Hash表，也称散列表，学过计算机数据结构的都比较清楚这个概念。Hash表是根据关键码值（key、value）而进行直接访问的数据结构，把关键码值映射到表中中一个位置来访问记录，加快查找速度，这个映射的函数称为hash函数，存放记录的数组叫散列表。

先来看一个转换：touhezijindeyu经过各种hash加密后得到的值：

Hash算法能把任意长度的二进制值映射为固定长度的二进制值，一般来说前一个二进制值我们成为明文，后面通过映射后得到的固定二进制值成为密文或者成为hash值。一旦在明文做任何修改，密文hash值就会有较大出入。

良好的hash算法需要满足：

• 快速定向：输入明文后，hash函数能在有限的时间和资源下计算出hash值。

  
  

• 难以逆推：得到密文hash值后，在规定的时间内无法推导出明文（注意是规定时间内，这个理论上和实际还是有一些区别）。

  
  

• 明文修改异常：明文稍作修改，密文hash值会有较大出入。

  
  

• 避免冲突：不同明文，难以出现相同密文hash值。

Hash函数一个映像的关系组，那么理论上会出现，明文x不等于y，那么f（x）=f（y）的情况。避免出现不同明文出现相同hash值，这种称为抗碰撞性，也就是上文说到的解决冲突。

散列函数的值需要尽可能的平均，同时需要良好的处理冲突的方法，一般解决冲突的方法如下：

• 线性探查法：发生冲突后，线性向前去探索，找到一个附近的空位置。这种方法会导致出现堆积现象，那么在存取的时候，无法明确同义词，那么盲目探查序列，这种探查法比较线性，原理较为明了，但是整个执行效率就会受到较大影响。

  
  

• 双散列函数法：在位置冲突后，再次使用一次散列函数进行计算，使得探查序列跳跃式分布。

常用的构造散列函数的方法：

• 直接寻址法：直接取key或者key的某个线性函数值为散列地址，那么H（key）=key或者H（key）=a*key+b，a、b为参数。

  
  

• 数字分析法：分析一组数据，发现有冲突可能，那么假设冲突后的数字来构成散列地址，这种方式事先找出数字的规律，然后尽可能利用数据来构造冲突几率低的散列地址。

  
  

• 平方取中法：取keyword平方后的中间几位作为散列地址。

  
  

• 折叠法：keyword切割，分成位数相同的几组，当然最后一组可不同，然后这几组的叠加和作为散列地址。

  
  

• 随机数法：选择一组随机函数，取keyword得随机值作为散列地址。

  
  

• 除留余数法：取keyword，然后被某个不大于散列列表表长m的数除后得到余数为散列地址。公式：H(key) = key MOD p, p<=m。不仅能够对keyword直接取模，也可在折叠、平方取中等运算之后取模。

Hash函数分类：

• 加法hash：把输入的元素一个个加起来的到最终结果。

  
  

• 位运算hash：通过利用各种位运算，移位或者异或来混合输入元素。

  
  

• 乘法hash：利用乘法的不相关性。比如乘以一个固定或者不停变化的数。

  
  

• 除法hash：和乘法的不相关性类似，但是除法效率较慢，所以应用较少。

  
  

• 查表hash：CRC系列相关算法。

  
  

• 混合hash：通过混合上述5种方式。

Hash算法应用：

• 校验文件：上述CRC校验和奇偶校验算法，防止数据篡改，MD5算法，目前听到的较多的一种校验文件完整性算法。

  
  

• 数字签名：由于非对称算法的运算速度，在常用数字签名协议中，单向的散列函数都是比较常用的，对于hash值，又会称为“数字摘要”进行数字签名。

  
  

• 挑战-认证模式：一般用于信道传输过程中，防止侦听破坏的一种方式。

Hash函数使用限制：

Hash函数中，不论输入的文件长度多少，输出结果都是一组固定长度的数字字符，结合加密方法的概念，hash算法是一个不可逆向的单项函数。文件有任意改动，即可检测出来。同时hash算法是一个无限大范围映射到一个有限小范围的模式，那么节省空间同时便于查找。

当然不是所有都适合hash算法，总结以下几个限制：

• hash函数是大范围映射到小范围，故实际输入考虑和小范围相当或者更小，理论上尽量避免冲突。

• hash函数是单向不可逆。

上期回顾：【虾说区块链】区块链术语及密码学基础解析

下期预告：【虾说区块链】区块链的3种加密算法及安全要求详解（附代码）

更多精彩内容点击公众号底部菜单栏查看~

点击“阅读原文”进入直播室听专栏音频。