发表更新数据结构/算法 / 哈希(Hash)20 分钟读完 (大约3030个字)

Hash

哈希(Hash)

[TOC]

哈希的基本概念

  • 哈希（Hash）在我的理解中是一种映射关系，例如，将学生映射到学号上、将口红的颜色映射到一个色号上。
  • 哈希函数（Hash Function）就是将一种你想要查询的关键字，比如说姓名、手机号码、数字或者字符串等，映射成便于查找的东西(一般来说是一个数字)的函数。
  • 一般而言，一个好的哈希函数可以帮我们将我们想要查找的东西，从一个较大集合映射到一个较小集合，然后我们可以将这个较小集合中的信息存储下来，例如存入一个数组，这个用于存储较小集合的数组就称之为哈希表。
    • 一张格式如下的表：
      学号 姓名
      0001 张三
      0002 李四
      0003 王五
      0004 赵六
      … …
    • 这张表就可以理解为一个姓名和学号的哈希表，我们通过学号就可以获得学号对应的人的姓名，即：学号[0001] -> "张三"，反映到代码中，可以理解为一个一维数组通过下标直接访问。
  • 而在一些加密工作中，可能需要将要简单的组合复杂化，比如密码组合，这时会有一种类似反向哈希（加密）的过程。
  • 比较常见的哈希函数的例子：
    $$H(x) = x ; mod ; 11$$
  • 这个函数可以让我们将任意的整数映射到 0 ~ 10 的范围中

哈希的基本操作

  • 定义哈希函数 
    1
    2
    3
    4
    5
    6
    7
    const int modnum = 11;
    int hashTable[modnum];

    // 定义哈希函数
    int hash(int x) {
        return x % modnum;
    }
  • 在哈希表中插入元素 
    1
    2
    3
    4
    5
    // 在哈希表中插入元素
    void insert(int x) {
        int addr = hash(x);
        hashTable[addr] = x;
    }
  • 在哈希表中查找元素 
    1
    2
    3
    4
    5
    // 在哈希表中查找元素
    bool isExist(int x) {
        int addr = hash(x);
        return hashTable[addr] == x;
    }

哈希表中解决冲突的方式

不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞，或者称为哈希冲突。
哈希表在存放数据时有可能出现冲突的情况，以上文中的哈希函数为例我们分别向其中插入元素，如下：

因为希望哈希表底层数组的容量小于实际要存储的关键字的数量，这就会导致一个问题：冲突的发生是必然的，我们能做的是尽量的降低冲突率。

冲突的解决方式一般有以下两种：

方式 1：顺延

一种很好想到的解决方式是将哈希表中插入时产生冲突的元素向后顺延，直到找到一个空位置再进行插入。这种方式称为顺延，也有说法称之为线性探测。

此时插入和查找的代码也要发生相应的改变，插入时需要我们需要找到一个空位置来执行插入操作；相对应的查找方式也要做出改变，当我们查询一个数时，也要查询哈希函数对应的位置，并依次比较连续的非空的哈希表中的值：

  • 插入操作 
    1
    2
    3
    4
    5
    6
    7
    void insert(int x) {
        int addr = hash(x);
        while(hashTable[addr] NOT NULL) { // 当哈希表的插入位置不为空
            addr = (addr + 1) % modnum;
        }
        hashTable[addr] = x;
    }
  • 查找操作 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void isExist(int x) {
        int addr = hash(x);
        while(hashTable[addr] NOT NULL) { // 当哈希表的查询位置不为空(查询一段连续的哈希表)
            if(hashTable[addr] == x) {    // 如果查询到指定元素, 返回 true
                return true;
            }
            addr = (addr + 1) % modnum;
        }
        return false;
    }
    可以定义多种解决冲突的顺延函数，即addr = (addr + 1) % modnum，实际使用中可以是每次$+k$，或者$+1^2$，$+2^2$，$+3^2$，…等。

但是这种顺延方式会存在一定的问题：插入时可能会出现多次冲突，当哈希表即将满的时候，插入操作的冲突可能会出现的更多，此时插入和查询操作都会变成一个非常耗时的操作。

方式 2：哈希链表

我们可以通过链表的方式，来实现在一个位置放置多个元素的操作。在 C++ 的 STL 库中，我们可以使用 STL 库中提供的 vector 来简单的替代链表。
通过这种方式，每次查找元素时，先找到对应的链表头，然后遍历这个位置的整张链表即可。

此时的哈希表的定义、插入操作和查询操作要发生相应的变化：

  • 定义哈希函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #include <iostream>
    #include <vector>

    const int modnum = 11;
    vector<int> hashTable[modnum];

    // 定义哈希函数
    int hash(int x) {
        return x % modnum;
    }

  • 插入操作

    1
    2
    3
    4
    void insert(int x) {
        int addr = hash(x);
        hashTable[addr].push_back(x);
    }

  • 查询操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void isExist(int x) {
        int addr = hash(x);
        int tableSize = hashTable[addr].size();
        // 这里不使用 for(int i = 0; i < hashTable[addr].size(); i++) 的写法, 而是首先计算出 hashTable[addr].size()
        // 因为 vector 的 size() 是一个比较耗时的操作, 他是通过将 vector 按照一个一个数出来的方式来进行计数的
        // 在数据量小的时候可能并不明显, 当数据量大的时候可能就会出现较为严重的耗时问题
        for(int i = 0; i < tableSize; i++) {
            if(hashTable[addr][i] == x) {
                return true;
            }
        }
        return false;
    }

    但是这种方式还是不能彻底解决我们的问题。对于插入操作来说，时间复杂度可以看作是$O(1)$，对于查询操作来说，时间复杂度和其冲突次数相关联。

哈希函数的设计

面对上面的问题，设计好哈希函数才是解决问题的关键。哈希函数在设计的时候，一般要注意几个原则：

  • 设计哈希函数时，我们需要尽可能让查询的值均匀地存储在哈希表中，或者说尽量分散再哈希表中。
  • 在手搓哈希函数时，我们会要求 $H(x) = x ; mod; p$，其中的 $p$ 为素数
  • 哈希函数中的对 $p$ 取摸的操作，会使得哈希值落在 $0 <= value <= p-1$ 的范围内，这个哈希表的长度 $p$，一般被称为哈希表的容量（Capacity）。
  • 插入哈希表的元素总数除以哈希表的容量得到的数，称为负载因子，这里可以用 $\alpha$ 表示，即：
    $$\alpha = ElumNum \div p$$
  • 当负载因子$\alpha$达到一定程度时（一般认为是$0.7\sim0.8$），则说明再对哈希表继续进行操作，就会面临大量冲突的情况，这时就要考虑增大哈希表的容量以避免出现更多的冲突。
  • 哈希函数的冲突率和负载因子的关系一般如下：

字符串哈希

字符串哈希是学习或者工作中经常遇到的一种操作，常用于比较两组字符串的内容等操作。通过比较两个字符串的哈希值就可以完成字符串的比较。当然这个操作也可以用于数组的哈希，因为字符串本质就是一个字符数组。
$$s = s_1s_2s_3 \dots s_n\qquad s_i \in a, b \dots z$$

一个字符串 $s$ 由 $n$ 个字符组成，每个字符 $s_i$ 属于 $a \sim z$。
其哈希函数为：
$$\begin{aligned}H(S)
&=(\sum_{i=1}^{n} c_i × base^{n-i});mod ;p\
&=(c_1 × base ^ {n-1} + c_2 × base ^ {n-2} + \dots + c_{n-1} × base ^ {1}) ; mod ; p\
&=base^{n-(n-1)}(base\dots(base(base × c_1 + c_2)));mod ;p\
&=base^{1}(base\dots(base(base × c_1 + c_2)+c_3)+\dots + c_n)\end{aligned};mod ;p$$

其中 $c_i$ 是一个和 $s_i$ 有关的数字，我们可以将字符映射到数字，例如：$a → 1$、$b → 2$ 等。这里不将 a 映射为 0，因为如果将 a 映射为 0，字符串 a 和 ab 的哈希值是相等的。
$base$ 是一个可以自己指定的数字，其值一般是大于字符集中的字符数量（$c_i$的最大值）的素数，这里可以取 31，常见的选择是 9999971。
$p$ 是一个素数，常见的选择是 101 或 137。

用代码实现为：

1
2
3
4
5
6
7
8
int hash(char s[], int n) {
    int res = 0;
    for(int i = 0; i < n; i++) {
        // 为什么是 res * base, 见上文的描述的公式推导
        res = (res * base + (s[i] - 'a' + 1)) % p;
    }
    return res;
}

当 $base$ 为 31，$p$ 为 101 时。
当 $s$ 为 $a$ 时，hash(char s[], int n) 的值为 1。
过程可以描述如下：

1
2
[1] res = (0 * base + ('a' - 'a' + 1)) % p
>>> res = 1

当 $s$ 为 $ab$ 时，hash(char s[], int n) 的值为 1。
过程可以描述如下：

1
2
3
4
[1] res = (0 * base + ('a' - 'a' + 1)) % p
>>> res = 1
[2] res = (1 * base + ('b' - 'a' + 1)) % p
>>> res = 33

当我们定义好一个良好的哈希函数之后，因为哈希函数的值相等的概率比较小，当两个字符串的哈希值相同的时候，我们可以认为两个字符串也相同，从而避免使用按位比较，节约时间。

$base$ 为什么一般是一个大于字符集中的字符数量（$c_i$的最大值）的素数呢？
当 $base$ 值过小时，此处假定为 $11$，会出现有可能两个字符运算完后还没有超过字母表的范围。如：字母表的范围为 $1 \sim 26$，字符串 ba 运算完成后的结果为 $23$，两个字符串的运算结果小于 $26$，字符串w运算完成后的结果为 $23$，可以发现 ba 和 w 出现了冲突。

我们字符串的定义方式有一种好处，可以使得我们借助类似前缀和的思想，快速得到任意一段字符串 $s$ 的字串的哈希值。

  • 我们可以使用一个数组 $a$ 来记录我们计算 hash(s) 的中间过程，即：
    1
    2
    3
    4
    a[1] = hash(c1)
    a[2] = hash(c1c2)
    ...
    a[i] = hash(c1c2...ci)
    那么字符串 $s$ 的任意子串 $s_{l, r} = s_ls_{l+1}\dots s_r$ 的哈希值为：
    $$hash(s_{l, r}) = (a[r] - a[l-1] × base^{r - l + 1});mod;p$$

双哈希

冲突往往是不可避免的，纵使我们的哈希函数再好，也有可能会出现冲突的情况，那么我们如何尽可能避免这个问题呢？这时候，我们可以使用双哈希的方法来避免冲突。
在上文字符串哈希中，我们的字符串哈希函数为：

$$H(S) = (\sum_{i=1}^{n} c_i × base^{n-i});mod ;p$$

那么如何实现双哈希呢？我们可以选取两组 $base$ 和 $p$，然后使用这分别使用这两组 $base$ 和 $p$，分别来求取哈希值。如果这两组参数得到的哈希值都相同，我们则认为两个字符串相等。在竞赛中，最好书写双哈希，甚至三哈希，因为这样出错误的概率会呈指数级的降低。

STL中的哈希 unordered_map

在 C++ 的STL库中，有一个非常好用的数据结构 unordered_map，可以帮助我们实现大多数哈希表的操作。

1
unordered_map<K, V> hash_table;

其中 K 为我们想要存储的关键字信息，V 表示与他关联的一些信息。例如：

1
unordered_map<string, int> hash_table;

这个表会以string作为K，int作为V进行存储，基于此我们可以很方便的实现一些功能。例如我们现在要保存一个班级上学生的年龄信息:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

using namespace std;

int query(string name) {
    if(hash_table.find(name) == hash_table.end()) {
        cout << "Cannot Find..." << endl;
    }
    return hash_table[name];
}

int main(void) {
    unordered_map<string, int> hash_table;
    hash_table["zhangsan"] = 2000;
    hash_table["lisi"] = 2001;
    query("zhangsan");
    
    return 0;
}
关注我

链接

分类

订阅更新

follow.it

最新文章

归档

标签

Annotation1
Axure RP 91
C++ 11 新标准2
CppDev7
Docker1
ECharts2
EasyX1
Fine-Tune(微调)1
GameDev1
Git1
HBase3
Hadoop3
JavaDev3
KAN1
Kaggle3
LLMs7
LM-Studio1
Linux3
Maven1
MyBatis-Plus1
PowerInfer1
PyTorch4
QT61
R1
RedHat1
SVN1
Scala1
Spark2
SpringBoot1
Stable Diffusion1
Tomcat1
VSCode1
ZooKeeper2
多线程编程1
大数据技术8
大模型1
开发工具4
数据结构5
机器学习4
深度学习12
算法5
网络编程1
计划1
语法点3
软件源1
闲聊1
项目1
×