哈希表 (散列表, Hash Table):根据键而直接访问在内存储存位置的数据结构。

哈希表

原理简述

如果我们使用朴素的方式储存数据,例如储存大量姓名,当我们要查找某个姓名时,只能够从头到尾遍历来查找,这样的查找效率非常低。但是我们可以将姓名进行分类储存,例如按姓氏分类,当查找时到对应姓氏的类别查找,这样就能大大提高查找效率。

哈希表的原理和上述例子类似,我们使用一个哈希函数(散列函数)$y=f(x)$,将建立原数据 $x$ 到类别 $y$ 的一个映射,这样便可找到数据对应的类别。上述例子的哈希函数即 $f(x)=x的姓氏$.

哈希函数

以下两种为整型数据的通用哈希方式。由于篇幅较长,字符串哈希的方式放置到文章结尾,以免打断思路。

取模法

$$ f(x)=x\bmod p\ (p\in\mathbb{N^*}) $$

我们可以非常简单地通过取模,将大范围的数据映射到 $[0,p)$ 的一个小范围内,从而实现哈希表。其中需要注意的是,$p$ 最好取为一个素数。因此若我们数据规模为 $x$ 时,$p$ 最好取为 $\geq x$ 的第一个素数。

另外 C/C++ 负数取模得非正数,需要特殊处理,即程序中哈希函数需要写为 $f(x)=(x\bmod p+p)\bmod p$ 来保证答案非负。

相乘法

$$ f(x)=\lfloor x\cdot p\cdot c\rfloor\bmod p\ (p\in\mathbb{N^*},c\in\mathbb{R}) $$

其中 $p$ 无特殊要求,$c$ 推荐取为黄金比例 $\varphi=\frac{1+\sqrt{5}}{2}$.

冲突处理

由于哈希函数将大范围数据映射到小范围内,因此冲突不可避免。如使用哈希函数 $f(x)=x\bmod 11$,$1$ 与 $12$ 均会映射到 $1$,产生冲突,我们通常使用两种冲突处理方式。

单独链表法 (Separate Chaining)

单独链表法即将同一位置的所有元素储存到一个链表内。用例子形象化表述:

使用哈希函数 $f(x)=x\bmod 11$,向哈希表中储存数据:$[1,2,11,56,23,12341,6547,312,27,44,654]$,那么如下表:

012345678910
1112 31227 12341
44566547 654
23

哈希表中 $0\sim 10$ 位均为一个链表,链表储存着对应位置的所有数据。

代码

/* 单独链表法 使用数组模拟链表实现 */

const int SIZE = 100003;
// SIZE为取模的数,同时也是数组大小
int hs[SIZE], val[SIZE], nxt[SIZE], idx;
// hs哈希表储存链表头指针,val链表节点数据域,nxt链表节点指针域,idx链表长度
// !!!hs每一字节需初始化为-1!!!

inline int f(int x) // 哈希函数
{
    return (x % SIZE + SIZE) % SIZE;
}

void insert(int x) // 将x插入表内
{
    int y = f(x);
    // 下面的操作为链表头插法
    val[idx] = x;
    nxt[idx] = hs[y];
    hs[y] = idx++;
}

bool query(int x) // 查询x是否在表内
{
    int y = f(x);
    for (int i = hs[y]; i != -1; i = nxt[i]) // 遍历链表
        if (val[i] == x)
            return true;
    return false;
}

(当需要删除操作时,通常不真正删除,而是使用一个 bool 数组指示元素的是否被删除)

开放寻址法 (Open Addressing)

开放寻址法当遇到冲突地址时,寻找下一个地址,直到找到可用地址储存数据。用例子形象化表述:

使用哈希函数 $f(x)=x\bmod 11$,向哈希表中储存数据:$[1,2,19,56,23]$,那么如下表:

012345678910
125623 19

可以发现奇怪的数据为 $56$ 和 $23$,它们本应该都储存到 $1$ 号位。但 $1$ 号位已经被 $1$ 占用,出现了冲突,那么开始寻找下一位。$2$ 号位已经被 $2$ 占用,寻找下一位。$3$ 号位可用,那么 $56$ 储存到 $3$ 号位。储存 $23$ 时同理,只不过找到了 $4$ 号位才发现可用。

我们也能很明显发现问题,当哈希表接近满时,会频繁地出现冲突,甚至需要遍历大部分数组才可找到可用位,最坏情况时间复杂度会和遍历整个数组一样低。因此当使用开放寻址法时,经验规律得出数组大小最好开到数据规模的 $2\sim 3$ 倍。上面数据规模为 $5$,数组长度为 $11$,目测可以发现查询效率还挺不错。

代码

// 开放寻址法
const int SIZE = 200003, NONE = 0x3f3f3f3f;
// SIZE为取模的数,同时也是数组大小,NONE为定义的代表空位的数字,需要不在哈希函数值域内
int hs[SIZE];
// hs哈希表 !!!hs每一字节需初始化为0x3f!!!

inline int f(int x) // 哈希函数
{
    return (x % SIZE + SIZE) % SIZE;
}

int find(int x) // 若x在表内,返回x的位置;若x不在表内,返回x应当插入的位置
{
    int y = f(x);
    while (hs[y] != NONE && hs[y] != x) // 当找到空位或找到了x就停下来
    {
        // 找不到就一直找下一位,找到最后一位再从第0位开始找
        y++;
        if (y == SIZE)
            y = 0;
    }
    return y;
}

void insert(int x) // 将x插入表内
{
    int k = find(x);
    hs[k] = x;
}

bool query(int x) // 查询x是否在表内
{
    int k = find(x);
    return hs[k] == x;
}

(当需要删除操作时,通常不真正删除,而是使用一个 bool 数组指示元素的是否被删除)

字符串哈希方式

字符串转整型

我们首先用进制转换举例。

$(1001)_2$ 这个二进制数转为十进制,即 $(1001)_2=1\cdot2^3+0\cdot2^2+0\cdot2^1+1\cdot2^0=9$

$(1234)_p$ 这个 $p$ 进制数转为十进制,即 $(1234)_p=1\cdot p^3+2\cdot p^2+3\cdot p^1+4\cdot p^0$

那么我们完全可以将字符串看为一个 $p$ 进制数,将其转换为十进制。该十进制数唯一对应这个字符串,这个字符串也唯一对应这个十进制数。如此我们将字符串转换为了一个整型数,接下来套用上面的整型哈希表即可。

经验规律得出,$p$ 的值取 $131$ 或 $13331$ 时冲突几率较小(字符串哈希处理冲突的开销较大,因此通常不进行处理,默认无冲突。所以冲突几率越小越好)

哈希函数

字符串往往较长,转换为的十进制数会极其庞大,此时我们就可以用哈希函数将极其庞大的数据范围映射到较小的数据范围。我们通常使用取模法的哈希函数,并且模数取 $2^{64}$,即哈希函数为 $f(x)=x\bmod 2^{64}$.

C/C++ 的 unsigned long long 数据类型范围为 $[0,2^{64})$,因此哈希函数可以直接忽略不写,让数据自然溢出则达到了取模效果。

字符串哈希的额外性质

如果我们将长为 $l$ 的字符串的 $0\sim i\ (i=0,1,\dots,l-1)$ 位的子串分别做哈希储存为一个表(比如字符串 $chris$,我们将 $c,ch,\dots,chris$ 的哈希值分别储存到 $h[0],h[1],\dots,h[4]$),那么会获得一个额外的性质,即我们可以在 $O(1)$ 内得到该字符串所有子串的哈希值。

原理我们仍然借助 $p$ 进制数来解释:

我们已知的是:第一行为 $p$ 进制数 $abcdef$ 的哈希值(仅作排版参考,实际用不上),第二行为 $0\sim2$ 子串的哈希值 $h[2]$ ,第三行为 $0\sim4$ 子串的哈希值 $h[4]$ 。

我们要求的是:第四行 $3\sim4$ 字串的哈希值。

$$ \begin{array}{r} (abcdef)_p & = & ap^5 & + & bp^4 & + & cp^3 & + & dp^2 & + & ep^1 & + & fp^0\\ (abc)_p & = & ap^2 & + & bp^1 & + & cp^0 & & & & & & \\ (abcde)_p & = & ap^4 & + & bp^3 & + & cp^2 & + & dp^1 & + & ep^0 & & \\ (de)_p & = & & & & & & & dp^1 & + & ep^0 & & \\ \end{array} $$

通过比对我们可以发现:$(de)_p=h[4]-p^2\cdot h[2]$

我们将结论普遍化,若子串左端点为第 $l$ 位,右端点为第 $r$ 位,则子串的哈希值 $h'$ 为:

$$ h'=h[r]-p^{r-l+1}\cdot h[l-1] $$

代码实现时,为了加快效率,通常将 $p$ 的幂次计算好保存到数组内,那么代码即为:

void init()
{
    p[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        p[i] = p[i - 1] * 131;
        h[i] = h[i - 1] * 131 + str[i];
    }
}

unsigned long long get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

标签: 哈希

添加新评论