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

哈希表

原理简述

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

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

哈希函数

以下两种为整型数据的通用哈希方式，字符串哈希将会在单独的文章介绍：https://io.zouht.com/142.html。

取模法

$$f(x)=xmodp(p\in {\mathbb{N}}^{\mathbb{\ast }})$$

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

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

相乘法

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

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

冲突处理

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

单独链表法 (Separate Chaining)

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

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

0	1	2	3	4	5	6	7	8	9	10
11	1	2		312	27					12341
44	56	6547			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)=xmod11$，向哈希表中储存数据：$[1,2,19,56,23]$，那么如下表：

0	1	2	3	4	5	6	7	8	9	10
	1	2	56	23				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 数组指示元素的是否被删除）