哈希算法

哈希算法

哈希算法（Hash）又称摘要算法（Digest），它的作用是：对任意一组输入数据进行计算，得到一个固定长度的输出摘要。哈希算法的目的就是为了验证原始数据是否被篡改，输出值的数据长度取决于哈希函数(hash)的算法方式。

哈希值的长度固定只是一个表象，重点在于映射到一个有限集合里（或者某个位置范围），方便做下一步操作。集合有限，所以可以用有限长度表示。从无限到有限的性质, 和做存储位置映射的hash类似，才被一起都叫hash。

哈希函数对字符串进行哈希处理后，得到的结果通常是一个二进制数据，但是为了方便表示和传输，通常会将其转换为十六进制字符串。

数组的低层是哈希表，哈希表是根据关键码值（Key Value）而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录，以加快查找的速度。这个映射函数就做散列函数，存放记录的数组叫做散列表。

散列存储的基本思路：以数据中每个元素的关键字K为自变量，通过散列函数H（k）计算出函数值，以该函数值作为一块连续存储空间的的单元地址，将该元素存储到函数值对应的单元中。

二进制与16进制：

二进制1位有21种状态，2位有22种状态，3位是23,4位是24，即16种状态。

16进制（0-9和A-F），1位是16种状态。

因此，一位16进制数 = 4位2进制数

哈希算法特征：

  1. 输出值的数据长度是固定不变的，输出值的数据长度取决于哈希函数(hash)的算法方式。
  2. 两个相同数据输入后，输出的哈希值也一定相同。
  3. 两个相似数据输入后，即使他们相差只是一点点，输出的哈希值也会有很大的不同(输入相似输出不一定相似)。
  4. 两个完全不同数据输入后，即使他们完全不同，输出的哈希值会有低概率相同出现。抽屉原理，输入数据存在无限可能，而输出有固定范围，因此一定会存在不同输入得到相同输出的情况，即哈希碰撞，碰撞越多，算法越不可靠；
  5. 输出的哈希值不能还原为原始数据。
  6. 哈希函数(hash)的加密(运算)相对其他加密方式，较为简单。

哈希函数(hash)在输入数据转换数据的各种情况下都会被用到。

哈希常见算法：

  1. MD5（Message Digest Algorithm 5）：产生128位的哈希值，常用于校验文件完整性。但由于其较低的安全性和容易碰撞（collision）的特点，已逐渐不再被推荐在加密领域使用。
  2. SHA-1（Secure Hash Algorithm 1）：产生160位的哈希值，曾广泛应用于安全领域。然而，SHA-1 已经被证明存在严重的安全弱点，因此在加密场景中也不再推荐使用。
  3. SHA-256（Secure Hash Algorithm 256）：产生256位的哈希值，安全性较高，仍然广泛应用于密码学、区块链等领域。
  4. SHA-3（Secure Hash Algorithm 3）：是美国国家标准与技术研究院（NIST）于2015年发布的新一代安全哈希算法，其基于 Keccak 算法，提供了多个摘要长度选项，如 SHA-3-224、SHA-3-256、SHA-3-384 和 SHA-3-512。
  5. CRC32（Cyclic Redundancy Check）：产生32位的哈希值，主要用于数据校验和错误检测，如文件校验、网络通信等。

哈希作用：

  1. 数据完整性验证：哈希函数可以为任意长度的数据生成固定长度的哈希值。通过对数据进行哈希计算，可以得到一个唯一的摘要值，用于验证数据的完整性。通过比较不同时间或不同地点生成的哈希值，可以确定数据是否被篡改或损坏。

  2. 加密与安全：哈希函数在密码学中扮演着重要角色。它们被用于存储密码、数字签名、消息认证等方面。密码哈希函数将用户的密码转换成固定长度的哈希值，并将其存储在数据库中，而不是明文保存密码。这样可以在验证用户身份时，直接比较哈希值，而不会使原始密码暴露在可能的攻击下。

  3. 数据索引和快速查找：哈希函数常用于索引和散列查找算法，如散列表（Hash Table），Bloom Filter 等。它们将数据映射到固定大小的哈希表中的位置，以实现高效的数据访问和查找操作。哈希函数可以减少搜索的复杂度，提高数据检索的速度。

  4. 数据分片和负载均衡：在分布式系统中，哈希函数可用于根据数据的特征将其均匀地分配到多个节点上。通过使用哈希函数，可以将数据均匀地散列到不同的存储节点上，实现负载均衡和数据的分布式存储。

  5. 数据唯一性标识：哈希函数可以将任意长度的数据映射为固定长度的哈希值。这样的哈希值通常可以作为数据的唯一标识符，用于数据的比较、去重和识别等应用场景。

哈希冲突解决办法：

  1. 开放寻址法（Open Addressing）：当发生冲突时，该方法会顺序地在哈希表中搜索下一个可用的槽位，直到找到空闲位置来存储数据。这种方法简单直接，但可能导致聚集效应，即连续的冲突会导致性能下降。
  2. 链地址法（Chaining）：该方法使用链表来解决冲突。哈希表的每个槽位包含一个指向链表头部的指针，在发生冲突时，新的元素被添加到对应槽位的链表中。这样可以避免聚集效应，并且适用于大多数情况。
  3. 再哈希法（Rehashing）：这种方法使用不同的哈希函数来处理冲突。当发生冲突时，会根据另一个哈希函数再次计算哈希值，并尝试将数据放置在新的位置上。这样可以尽量避免冲突，但需要额外的哈希函数。
  4. 建立公共溢出区（Overflow Area）：当发生冲突时，将冲突的数据存储在一个公共溢出区域中。这种方法简单，但可能会导致哈希表的使用效率降低。
  5. 完美哈希函数（Perfect Hashing）：完美哈希函数是一种能够确保没有冲突发生的哈希函数。它通过在构建哈希表时对输入数据进行分析和处理，选择适合的哈希函数来避免冲突。