哈希表：把键映射到存储位置-未完纪

哈希表（hash table，又称散列表）用键值对存储数据，可以看作更灵活的数组。数组通常以非负整数为下标，哈希表的键却可以是很大的整数、浮点数、字符串或结构体。它通过哈希函数把键映射到存储位置，再在对应位置保存值。

哈希函数

哈希函数应当容易计算，并尽量让键均匀地分布到不同位置。例如，只用身份证号码的后四位、前四位或者电话号码的后几位作为下标，都可能形成不同程度的集中。选取规则必须结合数据特征。

设哈希函数为 f，则键 key 对应的值存放在 a[f(key)]。由于可选键远多于存储位置，不同键可能得到相同结果，这称为哈希冲突。

整数键

当整数键的范围很大，例如达到 10^9，不能直接开同样大的数组。可以选择较大的模数 M，常用大质数，并计算：

f(x) = x mod M

这样结果落在 0 到 M-1 之间。负整数需要规范到非负余数范围。

字符串键

可以把字符串看作某种进位制的整数。例如把每个字符值作为一位，以 127 为基数。长度为 n 的字符串 s 可表示为：

x = s[0] * 127^0 + s[1] * 127^1 + ... + s[n-1] * 127^(n-1)

再对 M 取模。较长字符串对应的整数可能非常大，因此可在计算过程中逐步取模。也可使用无符号整数溢出的模运算；如果 unsigned long long 恰为 64 位，它按模 2^64 回绕，其最大值则是 2^64-1。

为降低冲突概率，还可以用两个较大的不同质数 a、b，分别计算两个哈希值。两个值一起匹配，比单一哈希更难碰撞，但哈希相同本身仍不能保证原始键相等。

冲突处理

拉链法

拉链法也称开放散列法。每个哈希位置维护一条链表，哈希值相同的元素放进同一条链。查询时先计算位置，再顺着链表比较原始键。

如果 N 个元素比较均匀地分布到 M 个位置，每条链的平均长度约为 N/M。因此在合适的负载下，查询很快；若大量元素集中到一个位置，则会退化为长链遍历。

下面是用数组模拟链表的 C++ 实现。head 保存链表头，节点的 next 保存下一节点编号，编号 0 表示空。这个示例用 -1 表示未找到。

constexpr int SIZE = 1000000;
constexpr int M = 999997;

struct HashTable {
  struct Node {
    int next, value, key;
  } data[SIZE];
  int head[M], size;

  int f(int key) { return (key % M + M) % M; }

  int get(int key) {
    for (int p = head[f(key)]; p; p = data[p].next)
      if (data[p].key == key) return data[p].value;
    return -1;
  }

  int modify(int key, int value) {
    for (int p = head[f(key)]; p; p = data[p].next)
      if (data[p].key == key) return data[p].value = value;
  }

  int add(int key, int value) {
    if (get(key) != -1) return -1;
    data[++size] = Node{head[f(key)], value, key};
    head[f(key)] = size;
    return value;
  }
};

对应的 Python 示例：

M = 999997
SIZE = 1000000


class Node:
    def __init__(self, next=None, value=None, key=None):
        self.next = next
        self.value = value
        self.key = key


data = [Node() for _ in range(SIZE)]
head = [0] * M
size = 0


def f(key):
    return key % M


def get(key):
    p = head[f(key)]
    while p:
        if data[p].key == key:
            return data[p].value
        p = data[p].next
    return -1


def modify(key, value):
    p = head[f(key)]
    while p:
        if data[p].key == key:
            data[p].value = value
            return data[p].value
        p = data[p].next


def add(key, value):
    if get(key) != -1:
        return -1
    size = size + 1
    data[size] = Node(head[f(key)], value, key)
    head[f(key)] = size
    return value

还可以写成更短的 C++ 容器形式，使用 operator[] 返回值的引用。SZ 需要在外部定义，memset 需要相应头文件；新键的默认值是 -1：

struct hash_map {
  struct data {
    long long u;
    int v, nex;
  };
  data e[SZ << 1];
  int h[SZ], cnt;

  int hash(long long u) { return (u % SZ + SZ) % SZ; }

  int& operator[](long long u) {
    int hu = hash(u);
    for (int i = h[hu]; i; i = e[i].nex)
      if (e[i].u == u) return e[i].v;
    return e[++cnt] = data{u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
  }

  hash_map() {
    cnt = 0;
    memset(h, 0, sizeof(h));
  }
};

开放寻址法

开放寻址法也称闭散列法。元素直接存放在表内，不另外维护链表。当原位置已被其他键占据，就按规则探测其他位置。

一种简单规则是线性探测：先检查 d，再检查 d+1、d+2 等，超过表尾则回到开头。查询必须沿插入时相同的探测序列继续，直到找到键或空位置。

下面的原文 C++ 示例按每一步递增的平方步长移动，并非上述线性探测。它以值为 0 表示空槽：

constexpr int N = 360007;

class Hash {
 private:
  int keys[N];
  int values[N];

 public:
  Hash() { memset(values, 0, sizeof(values)); }

  int& operator[](int n) {
    // 返回一个指向对应 Hash[Key] 的引用
    // 修改成不为 0 的值 0 时候视为空
    int idx = (n % N + N) % N, cnt = 1;
    while (keys[idx] != n && values[idx] != 0) {
      idx = (idx + cnt * cnt) % N;
      cnt += 1;
    }
    keys[idx] = n;
    return values[idx];
  }
};

以上实现用于说明数据结构，完整使用还须处理初始化、容量、空槽标志以及返回值约定。代码保留了原文示例，不宜直接视为生产容器。

例题

洛谷 P4305「JLOI2011」不重复数字要求去掉输入中重复出现的数字，并保留第一次出现的顺序。可以用哈希表记录数字是否已经出现：未出现则输出并登记，已出现则跳过。

来源：OI Wiki：哈希表。© 2016–2026 OI Wiki Team；中文整理。原页列出的贡献者包括 Ir1d、opsiff、HXLLL、ksyx、sshwy、Enter-tainer、iamtwz、Tiphereth-A、CCXXXI、cxc654321、Early0v0、HarumiKiyama、Henry-ZHR、ImpleLee、lhhxxxxx、LTHAndy、lyccrius、mcendu、memset0、Menci、ouuan、shawlleyw、StudyingFather、WASSER2545、Xeonacid、zirnc。页面内容采用 CC BY-SA 4.0 和 SATA；本整理稿遵循相同许可，保留署名并标明改编。

文章版权归作者所有，未经允许请勿转载。

THE END