[数据结构与算法]哈希算法

哈希算法

哈希算法是一种将任意长度的输入数据映射为固定长度的输出数据的算法。哈希函数的主要目标是保证数据的一致性和完整性，即使输入数据发生微小的变化，输出结果也会发生较大的变化。这种特性使得哈希算法在数据存储、密码学、数据完整性验证等领域得到广泛应用。

哈希算法的特点包括：

1. 固定长度输出： 无论输入数据有多长，哈希算法的输出都是固定长度的。例如，常见的MD5算法输出128位（16字节）的哈希值，SHA-256算法输出256位（32字节）的哈希值。
   
2. 唯一性： 不同的输入数据应该映射为不同的哈希值，但由于输出长度是固定的，可能会出现不同的输入映射为相同的哈希值，这被称为哈希碰撞。
   
3. 不可逆性： 从哈希值不能逆向推导出原始输入数据。即使两个不同的输入具有相同的哈希值，也不应该能够从哈希值还原出原始数据。
   
4. 高效性： 哈希算法的计算应该是高效的，能够在短时间内处理大量数据。
   

常见哈希函数：

MD5（Message Digest Algorithm 5）、SHA-1（Secure Hash Algorithm 1）、SHA-256。

MD5 (Message Digest Algorithm 5):

算法原理: MD5是一种基于加密哈希函数的算法，接收任意长度的输入，并输出一个128位（16字节）的哈希值。MD5算法主要由以下四个步骤组成：

1. 初始化： 初始化四个32位的变量（A、B、C、D），这些变量将存储最终生成的哈希值的四个部分。
   
2. 填充： 将输入数据填充到长度符合特定规则的倍数，通常是64位的倍数。填充包括原始消息长度的编码和一个比特"1"的附加。如果消息的位数不是512的倍数，就添加一些零位，直到满足条件。
   
3. 处理： 将填充后的数据分割成512位的块，并对每个块进行一系列的操作，包括位运算、逻辑函数和非线性函数。这些操作涉及到四个32位的变量，并进行64轮迭代。
   
4. 输出： 将最终处理的结果拼接在一起，形成128位的MD5哈希值。
   

MD5算法是由Ron Rivest于1991年设计的，但由于其安全性问题，现在不再推荐用于安全敏感的应用。MD5容易受到碰撞攻击，即找到两个不同的输入，使得它们产生相同的MD5哈希值。

SHA-1 (Secure Hash Algorithm 1):

算法原理: SHA-1是一种160位（20字节）的哈希函数，接收输入并输出固定长度的哈希值。SHA-1的步骤如下：

1. 初始化： 初始化五个32位的变量（A、B、C、D、E），它们将存储最终生成的哈希值的五个部分。
   
2. 填充： 类似于MD5，SHA-1对输入进行填充，使其长度符合512位的倍数。
   
3. 处理： 将填充后的数据分割成512位的块，并进行80轮迭代。SHA-1的处理过程包括位运算、逻辑函数和非线性函数，但相较于MD5，SHA-1的设计更为安全。
   
4. 输出： 将最终处理的结果拼接在一起，形成160位的SHA-1哈希值。
   

SHA-1曾经是广泛使用的哈希算法，但在2017年之前已经被证明不再足够安全，因为发现了对其的碰撞攻击。

SHA-256 (Secure Hash Algorithm 256-bit):

算法原理: SHA-256是SHA-2家族中的一员，输出256位（32字节）的哈希值。SHA-256的步骤类似于SHA-1，但具有更大的位数和更多的轮数，从而提高了安全性。

1. 初始化： 初始化八个32位的变量（A、B、C、D、E、F、G、H），它们将存储最终生成的哈希值的八个部分。
   
2. 填充： 对输入进行填充，使其长度符合512位的倍数。
   
3. 处理： 将填充后的数据分割成512位的块，并进行64轮迭代。SHA-256的处理过程包括位运算、逻辑函数和非线性函数。
   
4. 输出： 将最终处理的结果拼接在一起，形成256位的SHA-256哈希值。
   

SHA-256目前被广泛应用于许多领域，包括数字签名、数据完整性验证等，因为它提供了较高的安全性。

代码演示:

C++编写的简单示例代码，通过哈希表查找长度为10的数组中出现次数最多的数字：

#include <stdio.h>
#include <stdlib.h>
 
#define ARRAY_SIZE 10
 
int findMaxFrequency(int array[], int size) {
    if (size <= 0) {
        fprintf(stderr, "Invalid array size.\n");
        exit(EXIT_FAILURE);
    }
 
    // 使用哈希表存储数字出现的次数
    int* frequencyMap = (int*)calloc(ARRAY_SIZE, sizeof(int));
 
    // 统计数组中每个数字的出现次数
    for (int i = 0; i < size; ++i) {
        frequencyMap[array[i]]++;
    }
 
    // 找到出现次数最多的数字
    int maxFrequency = 0;
    int resultNumber = array[0]; // 默认结果为数组的第一个数字
 
    for (int i = 0; i < ARRAY_SIZE; ++i) {
        if (frequencyMap[i] > maxFrequency) {
            maxFrequency = frequencyMap[i];
            resultNumber = i;
        }
    }
 
    free(frequencyMap);
    return resultNumber;
}
 
int main() {
    // 示例数组
    int array[ARRAY_SIZE] = {1, 2, 3, 4, 2, 2, 3, 5, 6, 2};
 
    // 查找出现次数最多的数字
    int result = findMaxFrequency(array, ARRAY_SIZE);
 
    for(int i=0;i<10;i++){
      printf("数组数字%d: %d\n",i,array[i]);
  }
    
    // 输出结果
    printf("出现次数最多的数字: %d\n", result);
 
    return 0;
}

执行结果：

总结哈希算法的常见应用

1. 密码存储： 哈希算法常用于存储用户密码。而不是直接存储密码本身，系统通常会将密码哈希后存储。当用户登录时，系统会对用户提供的密码进行哈希，并将其与存储的哈希值进行比较，而不是明文密码。常用的密码哈希算法包括SHA-256和bcrypt。
   
2. 数字签名： 数字签名使用哈希算法来确保数据的完整性和认证。发送方使用私钥对消息进行哈希，并将哈希值与私钥一起签名。接收方使用发送方的公钥验证签名，并通过哈希比较确保消息的完整性。
   
3. 数据完整性验证： 哈希算法用于验证数据在传输过程中是否被篡改。发送方计算数据的哈希值并将其一并发送。接收方接收数据后，再次计算哈希值，如果两个哈希值一致，则数据完整性得到验证，否则说明数据可能被篡改。
   
4. 哈希表： 在计算机科学中，哈希表（Hash Table）是一种常见的数据结构，它使用哈希函数将键映射到存储桶中，从而实现高效的数据检索。哈希算法在这里用于确定键的存储位置。
   
5. 防止重复： 在分布式系统中，哈希算法用于确定唯一标识符，例如在一组服务器中分配任务或数据。这有助于防止重复处理或存储相同的数据。
   
6. 文件校验： 哈希算法可用于生成文件的校验和，以验证文件的完整性。用户可以计算文件的哈希值并与预期的哈希值比较，以确定文件是否被篡改。
   
7. 数字证书： 数字证书中使用了哈希算法来确保证书的完整性。证书颁发机构（CA）使用哈希函数对证书进行签名，以确保证书在传输过程中没有被篡改。