哈希算法

出自 MBA智库百科(https://wiki.mbalib.com/)

哈希算法（Hash 算法，Hash 算式，散列算法，消息摘要算法）

　　哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。一般用于快速查找和加密算法。

　　哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映射到一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。

　　通过将单向数学函数（有时称为“哈希算法”）应用到任意数量的数据所得到的固定大小的结果。如果输入数据中有变化，则哈希也会发生变化。哈希可用于许多操作，包括身份验证和数字签名。也称为“消息摘要”。

　　简单解释：哈希(Hash)算法,即散列函数。它是一种单向密码体制,即它是一个从明文到密文的不可逆的映射,只有加密过程,没有解密过程。同时,哈希函数可以将任意长度的输入经过变化以后得到固定长度的输出。哈希函数的这种单向特征和输出数据长度固定的特征使得它可以生成消息或者数据。

　　哈希算法(散列算法或者消息摘要算法)是信息存储和查询所用的一项基本技术，它是一种基于Hash函数的文件构造方法，可实现对记录的快速随机存取。它把给定的任意长关键宇映射为一个固定长度的哈希值，一般用于鉴权、认证、加密、索引等。其主要优点是运算简单，预处理时间较短，内存消耗低，匹配查找速度比较快，便于维护和刷新，支持匹配规则数多等。

　　(1)单向性。即给定一个输入数，容易计算出它的哈希值，但是已知一个哈希值根据同样的算法不能得到原输入数。

　　(2)弱抗碰撞性。即给定一个输入数，要找到另一个得到给定数的哈希值，在使用同一种方法时，在计算上不可行。

　　(3)强抗碰撞性。即对于任意两个不同的输入数，根据同样的算法计算出相同的哈希值，在计算上不可行。

　　哈希算法查找法易于实现，存储需求小，支持范围匹配和动态更新，但其效率受规则的分布情况和规则数量影响大，当有冲突时，查找时间比较长。

　　用来产生一些数据片段（例如消息或会话项）的哈希值的算法。使用好的哈希算法，在输入数据中所做的更改就可以更改结果哈希值中的所有位；因此，哈希对于检测数据对象（例如消息）中的修改很有用。此外，好的哈希算法使得构造两个相互独立且具有相同哈希的输入不能通过计算方法实现。典型的哈希算法包括 MD2、MD4、MD5 和 SHA-1。哈希算法也称为“哈希函数”。

　　另请参阅： 基于哈希的消息验证模式 (HMAC), MD2, MD4, MD5,消息摘要, 安全哈希算法 (SHA-1)。

　　MD5一种符合工业标准的单向 128 位哈希方案，由 RSA Data Security, Inc. 开发。 各种“点对点协议(PTP)”供应商都将它用于加密的身份验证。哈希方案是一种以结果唯一并且不能返回到其原始格式的方式来转换数据（如密码）的方法。质询握手身份验证协议(CHAP) 使用质询响应并在响应时使用单向 MD5哈希法。按照此方式，您无须通过网络发送密码就可以向服务器证明您知道密码。

　　质询握手身份验证协议(CHAP)“点对点协议(PPP)”连接的一种质询响应验证协议，在 RFC 1994 中有所描述。 该协议使用业界标准 MD5哈希算法来哈希质询串（由身份验证服务器所发布）和响应中的用户密码的组合。

　　点对点协议

　　用点对点链接来传送多协议数据报的行业标准协议套件。RFC 1661 中有关于 点对点协议（PPP） 的文档。

　　另请参阅： 压缩控制协议 (CCP)，远程访问，征求意见文档 (RFC)，传输控制协议/Internet 协议 (TCP/IP)，自主隧道。

　　哈希算法在用于分类时，需要考虑不同关键字之间哈希值可能发生的地址冲突。一般采用的是开放定址法来解决冲突，即建立冲突解除区，并使用链表在冲突解除区中存放冲突的关键字。如图1所示，当不同的输入产生相同的Hash值时，后输入的数将被以链表的形式存放在冲突解除区中。冲突的数越多，该Hash值后面的链表越长。在进行信息检索时，如果所需的信息存放在冲突解除区或者没有，由于输出为输入的散列值，需要遍历冲突解除区中的该链表。因此，常规的Hash算法用于对网络中数据包分类还存在如下的问题：当哈希算法选择不当的情况下，可能会造成较多碰撞，导致性能下降，最坏性能不能保证：运算量较大：不能针对不同的规则集通过优化来获得一个最低的冲突率。

　　尽管提出了多种改进的方案，如双Hash机制、可扩展Hash算法等以解决这些问题。但是Hash算法运用于海量信息查询时，仍然存在上述效率较低的问题。