哈希表

定义

通过将键映射到一个固定大小的数组索引，来实现快速的数据存储、检索的数据结构。

哈希函数

将键映射到数组索引的函数称为哈希函数。

函数要对表长取模，防止越界。

直接定址法

通过线性函数，直接将键映射到数组索引。

适用于键基本连续的情况。

$H(key) = w \cdot key + b$

int hash(int key, int w, int b) {
    return (w * key + b) % len;
}

除留余数法

通过取模运算，将键映射到数组索引。

适用于键分散且较均匀的情况。

$H(key) = key \space \% \space p$

$p$ 通常取接近数组大小的质数。

int hash(int key, int p) {
    return key % p % len;
}

BKDR哈希

把键看作 $base$ 进制的整形，计算其十进制值为索引

适用于处理字符串、大数等。

$H(key) = \sum_{i=1}^{n} key_i \times base^{n-i}$

通常取大质数作为$base$，如$131$。

int hash(string key, int base){
    int res = 0;
    for(int i = 0; i < len; i++) 
        res = res * base + key[i];
    return res % len;
}

其他哈希方法

• 结构体系哈希：对各个字段的哈希值组合做BKDR
• 平方取中法：将键平方后取中间几位作为索引
• 折叠法：将键分割为多个部分，然后将各部分的哈希值组合
• 随机数法：将随机数作为索引

负载因子

定义

哈希表中元素数量与数组大小的比率。

公式

$n:$ 哈希表中元素数量 $m:$ 数组大小

$\alpha = \frac{n}{m}$

意义

反映哈希表的空间利用率

• $\alpha$ 大：利用率高，但哈希冲突增多
• $\alpha$ 小：利用率低，空间浪费

哈希冲突

当两个不同的键映射到同一个索引时，称为哈希冲突。

开放寻址法

发生哈希冲突时，寻找空闲位置。

• 线性探测：每次探测下一个位置（到末尾则返回开头）

容易出现聚集，且删除时需要额外标记

void insert(int key, int val){
    int pos = H(key), cnt = 0;
    // 找到空闲位置，或所有位置均已探测
    while(table[pos] && cnt < len) {
        // 向右移动一位
        pos = (pos + 1) % len;
        // 探测次数+1
        cnt++;
    }
    table[pos] = val;
}

• 平方探测：依次探测距离为 $\pm i^2$ 的位置

避免聚集，删除仍需额外标记

void insert(int key, int val){
    int pos = H(key), hash = pos;
    // 探测次数不超过表长的一半，因为每轮探测两次
    for(int i = 1;i < len / 2;i++){
        // 左侧探测
        pos = (hash + i * i) % len;
        if(!table[pos]) break;
        // 右侧探测
        pos = (hash - i * i) % len;
        if(!table[pos]) break;
    }
    table[pos] = val;
}

链地址法

每个索引对应一个链表，冲突元素存储在链表中

可直接删除，无需额外标记

// 节点定义
struct Node{
    int val, key;
    Node* next;
    Node(int v, int k, Node* n):val(v), key(k), next(n){}
};
// 哈希表（元素是链表头）
vector<Node*> table(len);
void insert(int key, int val){
    // 计算索引
    int pos = H(key);
    // 头插（尾插也可以）
    Node* node = new Node(val, key, table[pos]);
    table[pos] = node;
}

扩容（Rehash）

当哈希表的负载因子超过某个阈值时，需要扩容。

开放寻址rehash

void rehash(int new_len){
    // 新建哈希表
    vector<int> new_table(new_len);
    // 重新插入元素
    for(int i = 0; i < len; i++){
        int val = table[i];
        // 忽略空节点和删除节点
        if(!val || val == DEL) continue;
        // 用原来的寻址方式插入新表
        insert(key, val, new_len);
    }
    // 交换表
    table.swap(new_table);
    len = new_len;
}

链地址rehash

void rehash(int new_len){
    // 新建哈希表
    vector<Node*> new_table(new_len);
    // 重新插入元素
    for(int i = 0; i < len; i++){
        Node* node = table[i];
        // 遍历链表
        while(node){
            // 计算新索引
            int new_pos = H(node->key, new_len);
            // 插入新表（头插）
            Node* temp = node->next;
            node->next = new_table[new_pos];
            new_table[new_pos] = node;
            // 移动到下一个节点
            node = temp;
        }
    }
    // 交换表
    table.swap(new_table);
    len = new_len;
}

渐进式rehash

保留旧表，每次操作同时迁移到新表，直到所有元素都迁移完成。

struct HashTable{
    // 新表和旧表
    vector<int> table[2];
    // 旧表完成迁移的索引位置
    int rehash_idx;
    // 是否在进行rehash
    bool is_rehashing;
};