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

前言

这篇文章将会简单介绍几种常见的哈希算法，然后是C++或Java的标准库中哈希函数与哈希表的基本使用，最后将会提供一个使用C语言手搓FNV-1a算法的示例，以及使用它实现的哈希表。

这篇文章虽然内容不多，但前前后后，也是删删改改了好多天了，虽然内容还是不尽人意，但希望此文能为你提供一点帮助，不说理解哈希，至少能够使用吧。

不知道某位大佬会不会来看这篇文章，关于哈希表的部分我不是很拿得准，如果理解有误，请帮我指出。

什么是哈希算法（散列算法）

散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。[1]好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。

如今，散列算法也被用来加密存在数据库中的密码（password）字符串，由于散列算法所计算出来的散列值（Hash Value）具有不可逆（无法逆向演算回原本的数值）的性质，因此可有效的保护密码。

——Wikipedia

我个人认为散列是一种数学思想，或者说是一种思维方式，能被应用到任意的方面。

简单的说，哈希算法是一套映射，向它输入不同的数据就能获得不同的结果，比如无论算几次都有hash(A) = a恒成立,而不可能有hash(B) = a（前提是没有碰撞），而且你没办法从结果逆推出原来的数据。

哈希算法有什么应用场景

1. 安全加密：基于哈希算法的输出值与原始数据唯一对应且不可逆向，哈希值散乱分布不可预测这两个特性，哈希算法可以被应用于密码存储，数据加密等安全领域。

2. 唯一标识：哈希算法的输入值可以是任意长度，输出值与原始数据唯一对应且不可逆向，所以哈希算法能被应用于文件校验领域，作为一个文件的”指纹“，成为它的唯一标识。

3. 数据校验：哈希值有”散列“特征，即便原始数据只进行了细微的修改，依然会导致哈希值产生巨大的变化。由此，在安全加密和唯一标识的基础上，哈希算法还能被应用于数据校验。

4. 散列函数：散列函数（哈希函数）是哈希表的基础，也是其最关键的部分，它直接决定了哈希表中发生碰撞（冲突）的概率和哈希表的性能。

5. 数据分片和分布式：通过类似哈希表的结构，我们可以将一次数据索拆分并下发至不同的机器执行，以此实现分布式网络，提高运行效率甚至是解决单机根本无法进行的操作。

什么是哈希碰撞（哈希冲突）

前文提到了“哈希算法获取数据的唯一对应哈希值”，这实际上需要建立在没有“哈希碰撞”的基础上。在理想情况下，我们向哈希函数输入两串数据，所返回哈希值一定不相同，但实际上，这样的说法并不成立。当不同的数据经过某种哈希算法获得了同一个哈希值，我们就称这时发生了“哈希碰撞”，就像是坐标系中的两个本应不相交的函数，随着X值的延伸，突然“碰撞”了，产生了至少一个交点。

哈希碰撞一旦发生，所谓的“密码学价值”也就得大打折扣了，但对于大多数哈希算法而言，碰撞虽无法避免，却也是难以发生的，在有限的范围内，我们可以近似地认为，哈希函数不会发生碰撞。

尽管如此，哈希碰撞依然带来了巨大的安全隐患，这种隐患不只是你从互联网上下载的文件的校验问题，它涉及到操作系统，企业服务器网络，甚至是金融体系的安全。

当然，数学家们也不是吃素的，早期的一些哈希算法被爆出漏洞后，不断的有一些新的算法出现，这些新算法的安全性极高，在短期，甚至是一段比较长的时期内几乎不会出现安全问题。

常见的哈希算法

实际上，哈希函数应该分为加密哈希函数和非加密哈希函数

Every cryptographic hash function is a hash function. But not every hash function is a cryptographic hash.

A cryptographic hash function aims to guarantee a number of security properties. Most importantly that it’s hard to find collisions or pre-images and that the output appears random. (There are a few more properties, and “hard” has well defined bounds in this context, but that’s not important here.)

Non cryptographic hash functions just try to avoid collisions for non malicious input. Some aim to detect accidental changes in data (CRCs), others try to put objects into different buckets in a hash table with as few collisions as possible.

In exchange for weaker guarantees they are typically (much) faster.

I’d still call MD5 a cryptographic hash function, since it aimed to provide security. But it’s broken, and thus no longer usable as a cryptographic hash. On the other hand when you have a non cryptographic hash function, you can’t really call it “broken”, since it never tried to be secure in the first place.

——https://security.stackexchange.com/a/11841

简单地说，非加密哈希函数只要求能够防御基本的恶意攻击，比较简单快速，而加密哈希函数则为了实现较高的安全性，不可逆性以及更加难以预测的哈希值分布而变得复杂。

我没有对这两个分类进行进一步的讨论，想要了解更多可以访问上面的连接。

到底怎样才能算是”常见“呢？这个问题很难回答…但我再这里列出了wiki上提到的部分以及我在搜集资料时见到比较多的算法。

另外，wiki上关于SHA-256等函数的碰撞情况是”无“，这显然是无稽之谈…我将他们全部改成“近似无”了。

C++和Java中预置的哈希函数和哈希表

1. C++

// ISO C++ 11标准及以后，标准库中提供了一个 std::hash<T>，返回参数的哈希值
// std::hash<T> 所使用的哈希算法是由具体编译器实现所决定的
// 对于老旧的编译器，std::hash<T> 所使用的算法很可能是已经被破解，不再安全的
// 下面是 std::hash<T> 的一个使用列，打印字符串“Hello world!“的哈希值
void hashTest()
{
    std::string str = "Hello world!";
    std::hash<std::string> hashFunction;
    size_t hashValue = hashFunction(str);
    std::cout << hashValue << std;:endl;
}

// 还有两个键值对数据结构，分别是 std::map<T,T> 和 std::unordered_map<T,T>
// 前者的内部存储方式为平衡二叉查找树（比如红黑树），后者是真正的哈希表
// std::map
map<std::string,int> nameAgeMap =
{
    {"Hatsune Miku",15},
    {"ZUN",45}
}

// std::map 的插入，如果下标不存在，则新建，若存在则修改。
nameAgeMap["Linus"] = 52;
// 上述语法与下式等价
nameAgeMap.insert(std::pair<std::string,int>("Linus",52));

// std::map 的取值
auto buffer0 = nameAgeMap["Linus"];
// 也可以这样写
auto buffer1 = nameAgeMap.at("Linus");
// 需要注意的是，map.at() 只会尝试读取，若找不到则报错
// 而map[]找不到则会创建，只是值未设置

// std::map 的查找
auto iter = nameAgeMap.find("Linus");
if(ite == nameAgeMap.end()) abort();
auto value = iter->second;

// std::map 的遍历
// 作为STL的一部分，std::map提供了迭代器，可供迭代器循环或增强for使用。
// 迭代器语法
for(auto item = nameAgeMap.begin();item != nameAgeMap.end();item++)
{
    // ...
}
// 增强for
for(auto& item : nameAgeMap)
{
    // ...
}

// std::map 的清除
// 通常情况下使用 map.clear() 就好
nameAgeMap.clear();

// 至于 std::unordered_map，与 std::map 的接口都是一样的
// 两者只在内部实现有区别
// 通常情况下，std::map 内存使用更少，而 std::unordered_map 查找更快 

2. Java

// Java标准库中提供了一些常用的哈希算法（如MD系和SHA系），并且统一了接口
import java.math.MessageDigest;
public class Main {
    public static void main(String[] args) throws Exception {
        // 此处示例使用了MD5算法，修改该处的字符串即可切换算法
        MessageDigest md = MessageDigest.getInstance("MD5");
        // 下述代码向哈希算法连续输入值，实际上等于输入"HelloWorld"
        md.update("Hello".getBytes("UTF-8"));
        md.update("World".getBytes("UTF-8"));
        // 获取UTF-8编码的"HelloWorld"的哈希值
        byte[] result = md.digest();
    }
}

// String类实际上提供了一个快速的哈希函数
// 我没有查到String.hashCode()所使用的具体哈希算法，还望各位相告
public class StringFastHash {
    public static void main(String args[]) {
        String str = "Hello world!";
        System.out.println("The hash code is:" + str.hashCode());
    }
}

// Java标准库中提供了两个哈希表：Hashtable和HashMap
// 两者都实现了Map接口
// 值得一提的区别是HashMap不能线程同步且键值可为null，Hashtable反之
// 其余的虽然也有区别，但是相差不大，只需要记得HashMap单线程里比另一者快就是
import java.util.HashMap;
public class HashMapTest {
    public static void main(String[] args) {
        HashMap<String,Integer> ages = new HashMap<String,Integer>();
        // 添加键值对示例
        ages.put("Hatsune Miku",15);
        ages.put("ZUN",45);
        // 访问元素示例
        System.out.println(ages.get("ZUN"));
        // 删除元素示例
        ages.remove("ZUN");
        // 清空元素示例
        ages.clear();
        // 计算元素数量示例
        System.out.println(ages.size());
        // 迭代键
        for(String name: ages.values()) {
            // ...
        }
        // 迭代值
        for(int age: ages.keySet()) {
            // ...
        }
        // 其余类方法略，请自行查表
    }
}

// 至于Hashtable，大体接口也与HashMap类似，略

使用C语言搓一个简单的哈希算法

这里用的是FNV-1a算法（32bit），真的很简单。

FNV-1a属于非加密哈希函数，支持32bit/64bit/128bit/256bit/512bit/1024bit的输出，根据输出长度的不同，其使用的常量不同，而算法不变。

wiki上有这样一段描述FNV-1a的伪代码

algorithm fnv-1a is
    hash := FNV_offset_basis

    for each byte_of_data to be hashed do
        hash := hash XOR byte_of_data
        hash := hash × FNV_prime

    return hash

可以看出这个算法非常简单，将初始哈希值循环进行乘法与异或运算即可得到哈希值。

查表可知，输出32bit的FNV-1a算法使用的两个常量FNV_offset_basi与FNV_prime分别有如下取值

static const uint32_t HASH_OFFSET_BASIS_32 = 0x811C9DC5;
static const uint32_t FNV_PRIME_32         = 16777619;

然后根据伪代码编写循环即可

uint32_t hash = HASH_OFFSET_BASIS_32;
for(int i = 0; i < strlen(data); i++)
{
    hash ^= data[i];
    hash *= FNV_PRIME_32;
}

完整代码

uint32_t fnv1a_32(char* data)
{
    // FNV-1a算法根据输出位数不同，各常量的值不同，此处为输出32bit的版本
    static const uint32_t HASH_OFFSET_BASIS_32 = 0x811C9DC5;
    static const uint32_t FNV_PRIME_32         = 16777619;

    uint32_t hash = HASH_OFFSET_BASIS_32;
    for(int i = 0; i < strlen(data); i++)
    {
        hash ^= data[i];
        hash *= FNV_PRIME_32;
    }

    return hash;
}

使用C语言搓一个简单的哈希表

哈希表（Hash table）是一种容器，实际上更像是一种加强版的数组，只不过数组是用数字下标映射地址，而哈希表通过哈希函数。

你可能听不懂，我们先来回顾一下传统的C-Style数组，是通过头指针+偏移量实现的，

int nums[3] = {1,2,3};
// 下述两段语句等价
printf("%d\n",nums[0]);
printf("%d\n",*nums);
// 下述两段语句等价
printf("%d\n",nums[2]);
// 头指针nums + 偏移量2
printf("%d\n",*(nums + 2));

这种方法简单粗暴但十分有效，无论数组中有多少个元素，索引总是一步就完成的（只需要按特定量偏移头指针），时间复杂度恒为O(1)。

假如我们需要建立一个数据结构，用于储存书名和对应的价格，按照上述思路可以这样写：

typedef struct {
    char name[32];
    float price;
} Book;

#define MAX_BOOK_COUNT 10;
Book books[MAX_BOOK_COUNT]
int count = 0;

// 初始化books
void initializeBooks()
{
    Book* book;
    for(int i = 0;i < MAX_BOOK_COUNT;i++)
    {
        book = books + i;
        book->price = 0;
    }
}

看起来不错，我们优雅地将书名和价格封装到了一个数据结构里，然后创建了他们的数组，一切看起来都很美好，只不过索引的方式有些许…弱智。

// 记录一本书的价格
void addBook(const char* name,float price)
{
    books[count].price = price;
    strcpy(books[count].name,name);
    count++;
}

// 获取一本书的价格
float getPrice(char* name)
{
    Book* book;
    for(int i = 0;i < MAX_BOOK_COUNT;i++)
    {
        book = books + i;
        if(strcmp(name,book->name) == 0) return book->price;
    }
    return -1.0f;
}

这个获取价格的操作的时间复杂度是O(n)，当BOOK_COUNT变大，耗时会线性增加。

想象一下你想要找到一本书的价格，然后翻遍了整个图书馆。

但你有没有想过，如果你有一个机器人，当你告诉它你要找的书的名字，它就会立即告诉你书的位置，于是你就能快速找到那本书的价格了。

像这样的带有”机器人“的图书馆，我们也许可以叫它，哈希图书馆。

这就是哈希结构，所谓的”机器人“，就是哈希函数。

来试试看吧。

#define MAX_BOOK_COUNT 10;
// 哈希表依然使用数组储存数据，和传统数组结构相比，只改变了索引方式
float bookPriceHashtable[MAX_BOOK_COUNT];

void initializeBooksHashtable()
{
    for(int i = 0;i < MAX_BOOK_COUNT;i++) bookPriceHashtable[i] = -1;
}

// 哈希函数，此处使用之前的FNV-1a算法+取余法以限定值域
// 虽然简单，但这样做会导致哈希碰撞（哈希冲突）的可能性增加
// 想要保证足够低的碰撞几率，就得提高数组容量，使用更多内存
// 可是哈希表的本质就是用内存换时间，不是吗？
unsigned int hash(char* str)
{
    return fnv1a_32(str) % MAX_BOOK_COUNT;
}

// 记录一本书的价格
void addBook(const char* name,float price)
{
    bookPriceHashtable[hash(name)] = price;
}

// 获取一本书的价格
float getPrice(char* name)
{
    return bookPriceHashtable[hash(name)];
}

可以看出，索引过程中仅仅在计算哈希时进入了循环，两个操作的时间复杂度都是O(1)，基本只需要考虑哈希算法的耗时，而获得哈希值后真正的索引耗时基本可以忽略不计。

上述哈希表的完整测试代码

#include <inttypes.h>
#include <stdio.h>
#include <string.h>

uint32_t fnv1a_32(char* data)
{
    // FNV-1a算法根据输出位数不同，各常量的值不同，此处为输出32bit的版本
    static const uint32_t HASH_OFFSET_BASIS_32 = 0x811C9DC5;
    static const uint32_t FNV_PRIME_32         = 16777619;

    uint32_t hash = HASH_OFFSET_BASIS_32;
    for(int i = 0; i < strlen(data); i++)
    {
        hash ^= data[i];
        hash *= FNV_PRIME_32;
    }

    return hash;
}

#define MAX_BOOK_COUNT 10
float bookPriceHashtable[MAX_BOOK_COUNT];

void initializeBooksHashtable()
{
    for(int i = 0;i < MAX_BOOK_COUNT;i++) bookPriceHashtable[i] = -1;
}

unsigned int hash(char* str)
{
    return fnv1a_32(str) % MAX_BOOK_COUNT;
}

void addBook(const char* name,float price)
{
    bookPriceHashtable[hash(name)] = price;
}

// 获取一本书的价格
float getPrice(char* name)
{
    return bookPriceHashtable[hash(name)];
}

int main(void)
{
    addBook("三体1", 1145.14f);
    addBook("三体2", 19198.10f);
    addBook("The Selfish Gene", 99.61f);

    printf("The price of 三体1 is %.2f\n",getPrice("三体1"));
    printf("The price of 三体2 is %.2f\n",getPrice("三体2"));
    printf("The price of The Selfish Gene is %.2f\n",getPrice("The Selfish Gene"));
    return 0;
}

你可以试试减小 MAX_BOOK_COUNT，然后添加更多的书本，感受一下哈希碰撞。

另外，哈希表其实是在用空间换取时间，在保证较小的碰撞概率的前提下，储存同样多元素的哈希表所占用的内存空间要明显大于数组。你可以编译并Debug上面的代码，查看 bookPriceHashtable 的内存，被修改过的非0数字散乱地分布在哈希表的内存片段中，这也是为什么哈希被称为”散列“。

不过话又说回来，除非是在搞嵌入式，有谁会在意那点内存呢？

哈希表与数组的性能对比

将上述代码的 MAX_BOOK_COUNT 修改为 30000000，向容器中填充 MAX_BOOK_COUNT/4 个元素，然后分别测试哈希表与数组索引一个插入于 MAX_BOOK_COUNT/8 位置的值，实验代码和结果如下。

1. 哈希表

#include <inttypes.h>
#include <limits.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

uint32_t fnv1a_32(char* data)
{
    // FNV-1a算法根据输出位数不同，各常量的值不同，此处为输出32bit的版本
    static const uint32_t HASH_OFFSET_BASIS_32 = 0x811C9DC5;
    static const uint32_t FNV_PRIME_32         = 16777619;

    uint32_t hash = HASH_OFFSET_BASIS_32;
    for(int i = 0; i < strlen(data); i++)
    {
        hash ^= data[i];
        hash *= FNV_PRIME_32;
    }

    return hash;
}

#define MAX_BOOK_COUNT 30000000
float bookPriceHashtable[MAX_BOOK_COUNT];

void initializeBooksHashtable()
{
    for(int i = 0;i < MAX_BOOK_COUNT;i++) bookPriceHashtable[i] = -1;
}

unsigned int hash(char* str)
{
    return fnv1a_32(str) % MAX_BOOK_COUNT;
}

void addBook(const char* name,float price)
{
    bookPriceHashtable[hash(name)] = price;
}

// 获取一本书的价格
float getPrice(char* name)
{
    return bookPriceHashtable[hash(name)];
}

int main(void)
{
    char name[5] = "3体1";
    float price = 0.0f;
    for(int i = 0;i < MAX_BOOK_COUNT / 4;i++)
    {
        if(i == MAX_BOOK_COUNT / 8)
        {
            addBook("C为什么是神", 114.51f);
            continue;
        }

        for(int j = 0;j < 3;j++) name[j] += 1;
        addBook(name, ++price);
    }

    clock_t begin,end;
    begin=clock();
    printf("《C为什么是神》的价格是: %.2f\n",getPrice("C为什么是神"));
    end=clock();

    printf("%lf\n",(double)(end-begin)/CLOCKS_PER_SEC);
    return 0;
}

2. 数组

#include <inttypes.h>
#include <limits.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

typedef struct {
    char name[32];
    float price;
} Book;

#define MAX_BOOK_COUNT 30000000
Book books[MAX_BOOK_COUNT];
int count = 0;

// 初始化books
void initializeBooks()
{
    Book* book;
    for(int i = 0;i < MAX_BOOK_COUNT;i++)
    {
        book = books + i;
        book->price = 0;
    }
}

// 记录一本书的价格
void addBook(const char* name,float price)
{
    books[count].price = price;
    strcpy(books[count].name,name);
    count++;
}

// 获取一本书的价格
float getPrice(char* name)
{
    Book* book;
    for(int i = 0;i < MAX_BOOK_COUNT;i++)
    {
        book = books + i;
        if(strcmp(name,book->name) == 0) return book->price;
    }
    return -1.0f;
}

int main(void)
{
    char name[5] = "3体1";
    float price = 0.0f;
    for(int i = 0;i < MAX_BOOK_COUNT / 4;i++)
    {
        if(i == MAX_BOOK_COUNT / 8)
        {
            addBook("C为什么是神", 114.51f);
            continue;
        }

        for(int j = 0;j < 3;j++) name[j] += 1;
        addBook(name, ++price);
    }

    clock_t begin,end;
    begin=clock();
    printf("《C为什么是神》的价格是: %.2f\n",getPrice("C为什么是神"));
    end=clock();

    printf("%lf\n",(double)(end-begin)/CLOCKS_PER_SEC);
    return 0;
}

3. 结果

使用Linux中的time命令计时，有如下结果

由此我们得到一个恐怖的结果，在该项测试中，哈希表的索引速度大约是数组的150倍，且随着 MAX_BOOK_COUNT 的增加，差距还会继续增大。

参考资料

散列函数 - 维基百科，自由的百科全书 (wikipedia.org)

哈希算法 - 廖雪峰的官方网站

【必备算法】哈希算法：七种应用及场景示例_A minor的博客-CSDN博客_哈希算法简单举例

哈希算法及其应用场景 - 知乎 (zhihu.com)

Fowler–Noll–Vo hash function - Wikipedia

常用Hash算法(C语言实现)_huangkangying的博客-CSDN博客_hash函数c语言实现

https://security.stackexchange.com/a/11841