数据结构: 哈希表

Posted on 2024-11-16 Edited on 2025-12-31 In Algorithm , Data Structure Word count in article: 1.4k Reading time ≈ 5 mins.

哈希表

概述

在FTP与HTTPS中，粗略介绍了哈希算法加密数据的概念；它用哈希算法将无限的数据转换成唯一的、用数字描述的值；对一个合格的哈希函数而言：

哈希函数尽可能是单射，但哈希冲突不可避免
哈希函数不能是双射，即不可逆

在哈希表这种数据结构中，利用了哈希函数的转换，使传入的每一个键都对应一个唯一的值，便可以通过键快速地查找到数组中的存储的数据，它的应用场景很多：

检索：键可以是多样的，例如纯数字的学号、纯字符串的姓名等，在开发中不能让用户通过数组下标来访问数据，就需要哈希表；在程序上的哈希表结构使用的算法一般较简单，不追求加密功能
文件加密：目前有特定的哈希算法，例如MD5,SHA-256等，算法复杂，但能生成更具有唯一性的摘要

它的特点有：

哈希表的优势在于，只要不发生哈希冲突，就可以靠快速的哈希函数，取得映射的下标，直接访问地址，达到查找、插入、删除的复杂度都为O(1)
然而任何哈希函数都可能造成哈希冲突，即传入不同数据却生成相同的值
哈希表是通过数组实现的，因此需要大容量的数组，且数据量大于数组容量后，效率急速下降
通常需要将大范围的键值缩小映射到小范围内

实现哈希算法

对键进行hash的过程，相当于给数组的整型索引添加更高级的信息，使索引不再是单纯的数字

设计原则

唯一性：不同的键映射后的值尽可能不同
简单性：计算过程应尽可能简单
均匀性：不同的键映射后的值应均匀分布在数组中

算法分类

哈希算法需要对输入数据有足够的敏感度，在许多做法中，通常会选择将输入的所有数据进行充分混合

一般来说，哈希算法有以下类型的实现：

位运算(常用移位和异或，用于混合整数的部分信息)
加法、乘法、除法(通常选择一个素数，例如(prime * x)%size对x进行哈希)
取模(通常是必要的)

整数键

这种情况很少，也较为简单，通常为了节省空间，不会采用直接取址，而是混合位运算、乘法、素数、模运算来实现，例如：

1
2
3

size_t hash(int _val, size_t _scope) {
    return (((size_t(_val) >> 16) ^ _val) * 0x5F58E29) % _scope;
}

其中，0x5f58e29是任取的素数，_scope是映射的范围

位运算的选择(右移和异或搭配)原理：

一般来说，预设的存储空间相对于无穷的数据来说，是较小的一方；因此在直接取模法中，高位的信息将丢失，哈希结果出现聚集现象(例如存储空间为5，11%5=21%5=1，十位的数据未参与哈希运算)
为了使高位信息参与运算，采用右移运算符
异或运算的结果集中，1和0是平均分配的(分别占一半)，比其它位运算更能保证高低位信息均匀混合

指针类型的数据实际上以十六进制整数存储，可以通过整数的逻辑设计哈希函数，只需要在计算时通过reinterpret_cast<size_t>(重新解释转换，较底层，有风险)强制类型转换即可

字符串键

字符串所带信息更多，例如长度、下标、字符本身，每个字符都是一个整数

最简单的字符串哈希：

size_t hash(char* _val, size_t _scope) {
    size_t ans = 0;
    for (int i = 0; i < strlen(_val); ++i) {
        ans += (i + 1) * _scope[i]; // 混合了下标和字符.
    }
    return ans % _scope;
}

经典的字符串哈希算法：

BKDR Hash(Java采用)：将字符串视为P进制数，转换成十进制后取模即可

const int P = 131; // 通常取13/31/131/13131..., 实验证明它们最合适.
size_t hash(char* _val, size_t _scope) {
    size_t ans = 0;
    for (int i = 0; i < strlen(_val); ++i) {
        // 采用从高位到低位的转换方式, 运算更快.
        ans = ans * P + _val[i]; // 隐含自然溢出,即超出ull范围后自动取模
    }
    return ans % _scope;
}

通过位运算进行哈希：RS、AP、FNV等算法
在算法竞赛中，单哈希也许是不够的，常见的解决办法是进行双哈希(分别有不同的P和模数)，组成序偶

BKDR算法还能快速地得到子串的哈希值(需要存储每一步的计算结果)：

size_t hash(char* _val, size_t _scope, size_t _left, size_t _right) {
 size_t hashCode[_right + 1] {0};
 for (int i = 1; i < _right + 1; ++i) {
        hashCode[i] = hashCode[i - 1] * P + _val[i];
    }
    // 相减后可能是负数, 加上一周进行补偿.
    return (hashCode[_right] - hashCode[_left - 1] * power(P, _right - _left + 1) + _scope) % _scope;
}

浮点数键

自定义键

在C++中，默认提供的哈希函数只有以上几种，如果希望能在unordered_map等std的哈希结构中使用自定义类型，那么该类型应满足：

实现哈希函数hash()
实现重载运算符==(便于处理哈希冲突)

实现哈希函数并不难，通常使能进行哈希运算的成员数据的哈希结果互相进行位运算而得，依靠std中的哈希结构解决哈希冲突

哈希表

概述