原作者：Linux教程，原文地址：「链接」

什么是哈希算法？

哈希算法（Hash Algorithm），又称为散列算法或杂凑算法，是一种将任意长度的数据输入转换为固定长度输出值的数学函数。其输出结果通常被称为：

• 哈希值（Hash Value）
• 哈希码（Hash Code）
• 消息摘要（Message Digest）

该类算法在信息安全领域具有广泛应用，主要包括以下几个方面：

• 数据完整性校验
• ：用于验证数据在传输或存储过程中是否被篡改。
• 数字签名与认证
• ：作为加密系统的一部分，确保信息来源的真实性和不可否认性。
• 密码存储
• ：对用户密码进行哈希处理后存储，增强安全性。
• 快速数据查找
• ：如哈希表结构中用于高效检索数据。

Part1 哈希算法的工作原理

哈希算法通过一个特定的哈希函数（Hash Function）将原始输入数据（明文、文件、字符串等）映射为一个固定长度的二进制串或十六进制字符串，这个过程也称为“哈希运算”或“摘要生成”。

例如：

输入："Hello, world!"
输出（SHA-256）："315f5bdb76d078c43b8ac0064e4a01646bf518ea4a329b7f9a7a3e68c3f5fc0"

常见哈希算法

Part2哈希算法：从哈希表谈起

在介绍哈希算法之前，我们先从一个与其密切相关且广泛使用的数据结构——哈希表（Hash Table）讲起。理解哈希表的工作原理，有助于我们更好地掌握哈希算法的设计思想及其应用场景。

2.1 数据结构 —— 哈希表（Hash Table）

2.1.1、哈希表的基本概念

哈希表（Hash Table），又称为散列表，是一种基于键值对（Key-Value Pair）存储的数据结构。它通过哈希函数将键（Key）映射为数组索引，从而实现高效的插入、查找和删除操作。

简而言之：

给定一个键 key，我们可以使用哈希函数快速定位其对应的值 value，时间复杂度接近 (1)。

2.1.2、哈希表与其他数据结构的效率对比：

虽然数组和链表也可以实现基本的查询功能，但它们在效率上远不如哈希表。下面是三种结构在常见操作上的性能比较：

说明：

• 数组和链表：若未排序，查找和删除都需要遍历整个结构，因此时间复杂度为线性。
• 哈希表：通过哈希函数直接计算出数据的位置，避免了遍历，使得增删查改都具有常数级的时间复杂度（理想情况下）。

2.1.3、哈希表的核心机制

哈希表的高效性依赖于两个关键组件：

1. 哈希函数（Hash Function）
2. 将任意长度的输入（如字符串、整数等）转换为固定长度的数值。
3. 该数值再通过取模运算确定其在数组中的位置（即“桶”）。
4. 冲突解决策略
5. 不同的键可能映射到同一个位置（称为哈希冲突），需要通过链地址法、开放寻址法等方式解决。

哈希表的基本工作流程如下：

1. 插入操作：输入键 key → 哈希函数计算索引 → 存储值 value 到对应桶中。
2. 查询操作：输入键 key → 哈希函数计算索引 → 直接访问桶获取值 value。
3. 删除操作：类似查询，找到后进行删除。

哈希表的代码实现

typedef struct {  
    int key;  
    char *val;  
} Pair;  
/* 基于数组实现的哈希表*/  
typedef struct {  
    Pair *buckets[MAX_SIZE];  
} ArrayHashMap;  
/* 构造函数*/  
ArrayHashMap *newArrayHashMap() {  
    ArrayHashMap *hmap = malloc(sizeof(ArrayHashMap));  
    for (int i=0; i < MAX_SIZE; i++) {  
        hmap->buckets[i] = NULL;  
    }  
    return hmap;  
}  
/* 析构函数*/  
void delArrayHashMap(ArrayHashMap *hmap) {  
    for (int i = 0; i < MAX_SIZE; i++) {  
        if (hmap->buckets[i] != NULL) {  
            free(hmap->buckets[i]->val);  
            free(hmap->buckets[i]);  
        }  
    }  
    free(hmap);  
}  
/* 添加操作*/  
void put(ArrayHashMap *hmap, const int key, const char *val) {  
    Pair *Pair = malloc(sizeof(Pair));  
    Pair->key = key;  
    Pair->val = malloc(strlen(val) + 1);  
    strcpy(Pair->val, val);  
    int index = hashFunc(key);  
    hmap->buckets[index] = Pair;  
}  
/* 删除操作*/  
void removeItem(ArrayHashMap *hmap, const int key) {  
    int index = hashFunc(key);  
    free(hmap->buckets[index]->val);  
    free(hmap->buckets[index]);  
    hmap->buckets[index] = NULL;  
}  
/* 获取所有键值对*/  
void pairSet(ArrayHashMap *hmap, MapSet *set) {  
    Pair *entries;  
    int i = 0, index = 0;  
    int total = 0;  
    /* 统计有效键值对数量*/  
    for (i = 0; i < MAX_SIZE; i++) {  
        if (hmap->buckets[i] != NULL) {  
            total++;  
        }  
    }  
    entries = malloc(sizeof(Pair) * total);  
    for (i = 0; i < MAX_SIZE; i++) {  
        if (hmap->buckets[i] != NULL) {  
            entries[index].key = hmap->buckets[i]->key;  
            entries[index].val = malloc(strlen(hmap->buckets[i]->val) + 1);  
            strcpy(entries[index].val, hmap->buckets[i]->val);  
            index++;  
        }  
    }  
    set->set = entries;  
    set->len = total;  
}  
/* 获取所有键*/  
void keySet(ArrayHashMap *hmap, MapSet *set) {  
    int *keys;  
    int i = 0, index = 0;  
    int total = 0;  
    /* 统计有效键值对数量*/  
    for (i = 0; i < MAX_SIZE; i++) {  
        if (hmap->buckets[i] != NULL) {  
            total++;  
        }  
    }  
    keys = malloc(total * sizeof(int));  
    for (i = 0; i < MAX_SIZE; i++) {  
        if (hmap->buckets[i] != NULL) {  
            keys[index] = hmap->buckets[i]->key;  
            index++;  
        }  
    }  
    set->set = keys;  
    set->len = total;  
}  
/* 获取所有值*/  
void valueSet(ArrayHashMap *hmap, MapSet *set) {  
    char **vals;  
    int i = 0, index = 0;  
    int total = 0;  
    /* 统计有效键值对数量*/  
    for (i = 0; i < MAX_SIZE; i++) {  
        if (hmap->buckets[i] != NULL) {  
            total++;  
        }  
    }  
    vals = malloc(total * sizeof(char *));  
    for (i = 0; i < MAX_SIZE; i++) {  
        if (hmap->buckets[i] != NULL) {  
            vals[index] = hmap->buckets[i]->val;  
            index++;  
        }  
    }  
    set->set = vals;  
    set->len = total;  
}  
/* 打印哈希表*/  
void print(ArrayHashMap *hmap) {  
    int i;  
    MapSet set;  
    pairSet(hmap, &set);  
    Pair *entries = (Pair *)set.set;  
    for (i = 0; i < set.len; i++) {  
        printf("%d -> %s\n", entries[i].key, entries[i].val);  
    }  
    free(set.set);  
}

2.2 哈希算法的作用

哈希表之所以能高效运行，核心在于哈希函数的设计质量。而哈希函数正是哈希算法的具体体现之一。

哈希算法与哈希表的关系可以总结为：

• 哈希算法是一种通用算法，将任意数据转化为固定长度的摘要。
• 哈希函数是哈希算法的一个具体应用，用于哈希表中将键映射为索引。
• 哈希表是数据结构，依赖哈希函数实现高效的数据访问。

换句话说：

哈希算法是基础，哈希函数是它的具体实现形式，而哈希表则是哈希函数的重要应用场景之一。

观察发现，在哈希表中进行增删查改的时间复杂度都是(1) ，非常高效。

我们可以通过一个通用公式来描述哈希算法的行为：

对于任意输入数据 x，哈希函数 H(x) 生成一个输出y=H(x)，满足以下基本性质。

Part3哈希函数的通用特性

Part4哈希算法的常见特性（进阶）

除了上述基础特性外，高质量的哈希算法还具备以下几个关键属性：

Part5 哈希算法的典型应用场景

在理解了哈希算法的基本概念和常见类型后，我们接下来通过 C++ 编程语言实现两个常见的哈希算法：CRC32 和 SHA-256，并解析其实现原理和应用场景。

5.1 CRC32 算法实现

CRC32（Cyclic Redundancy Check 32）是一种非加密类校验算法，主要用于检测数据传输中的随机错误。其输出为一个 32 位（4 字节）整数。

注意：CRC32 不具备抗碰撞性，不适合用于密码学安全场景。

实现原理：

CRC32 使用一种基于多项式除法的算法来计算校验值。核心步骤如下：

1. 初始化 CRC 值为 0xFFFFFFFF。
2. 对每个字节依次异或到 CRC 值中。
3. 进行 8 次位移操作，并根据当前最低位决定是否异或预定义的多项式 0xEDB88320。
4. 最终结果取反得到标准 CRC32 校验值。

C++ 实现代码

#include <iostream>
#include <string>
unsigned int crc32(const std::string& data) {
    unsigned int crc = 0xFFFFFFFF;
    const unsigned int polynomial = 0xEDB88320;
    for (unsigned char byte : data) {
        crc ^= byte;
        for (int i = 0; i < 8; ++i) {
            if (crc & 1) {
                crc = (crc >> 1) ^ polynomial;
            } else {
                crc >>= 1;
            }
        }
    }
    return ~crc;
}
int main() {
    std::string input = "Hello, World!";
    unsigned int hash = crc32(input);
    std::cout << "CRC32: " << std::hex << hash << std::endl;
    return 0;
}

输出示例

CRC32: 1c291ca3

5.2 SHA-256 算法实现

SHA-256 是 SHA-2 系列中的一种安全哈希算法，广泛用于数字签名、密码存储、区块链等安全敏感领域。它将任意长度的输入转换为一个固定长度的 256 位（32 字节）哈希值。

SHA-256 的核心处理流程如下：

1. 消息填充
2. ：确保输入长度对 512 位整除。
3. 分块处理
4. ：将数据划分为多个 512 位的消息块。
5. 初始化哈希值
6. ：使用 8 个固定的初始哈希值（H0~H7）。
7. 压缩函数
8. ：对每个消息块执行一系列逻辑运算（AND、XOR、NOT、ROTATE）、位移和加法操作。
9. 最终输出
10. ：将 8 个中间哈希值拼接，生成最终的 256 位哈希值。

使用 OpenSSL 库实现 SHA-256（推荐方式）

OpenSSL 提供了成熟的哈希函数接口，适用于实际开发。

#include <iostream>
#include <iomanip>
#include <sstream>
#include <openssl/sha.h>
std::string sha256(const std::string& data) {
    unsigned char hash[SHA256_DIGEST_LENGTH];
    SHA256(reinterpret_cast<const unsigned char*>(data.c_str()), data.size(), hash);
    std::stringstream ss;
    for (int i = 0; i < SHA256_DIGEST_LENGTH; ++i) {
        ss << std::hex << std::setw(2) << std::setfill('0') << static_cast<int>(hash[i]);
    }
    return ss.str();
}
int main() {
    std::string input = "Hello, World!";
    std::string hash = sha256(input);
    std::cout << "SHA-256: " << hash << std::endl;
    return 0;
}

编译时需链接 OpenSSL：

g++ -o sha256_example sha256_example.cpp -lssl -lcrypto

输出示例

SHA-256: a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b7748722cfcbd35a5

学习建议

• 初学者
• 可尝试手动实现 CRC32 来理解基础哈希机制；
• 进阶开发者
• 推荐使用如 OpenSSL、Crypto++ 等成熟库实现 SHA-256；
• 若需要完全自定义实现 SHA-256，可参考 FIPS 180-4 标准文档逐步编码。