哈希表 · Zwing's blog

如果只考虑查找、插入和删除操作，有无比搜索树更快的算法？

概念

哈希表（Hash Table）是一种以键值对（key-value）存储数据的结构，主要思想是使用 哈希函数 将键映射到存储桶（bucket）上，从而实现快速访问

哈希函数将键转换为哈希值，哈希值用于确定键值对在哈希表中的位置

当两个不同的键映射到同一个哈希值时，称为哈希冲突，解决哈希冲突的方法有链表法和开放寻址法

放个例题:【模板】哈希表

但如果手搓的话，就先止步于链表法与开放寻址+线性探测了（…）

无论链表还是开放寻址，最坏的情况下查找和插入的时间复杂度均会从 \(O(1)\) 退化至 \(O(n)\)

链表法

链表法将哈希值相同的键值对存储在同一个桶中，桶中存储一个链表，链表中的每个节点存储一个键值对

示例代码，具体情况可以根据要求灵活更改

// 哈希表桶的个数，可根据内存限制灵活分配
const int HASH_SIZE = 2000003;

struct node
{
    // 如果是数到数的映射，一般用 ll 或 ull
    long long key;
    long long val;
};

class HashTable
{
    vector<list<node>> v; // 数组的元素是链表（也可以为数组等）
    static long long hashFunc(long long key)
    {
        // 因为 vector 下标非负，这种写法可以处理负数问题
        return (key % HASH_SIZE + HASH_SIZE) % HASH_SIZE;
    }
public:
    HashTable()
    {
        v.resize(HASH_SIZE);
    }

    bool find(long long key)
    {
        long long hash = hashFunc(key);
        for(auto &x : v[hash])
        {
            // hash 只是确定桶，还要根据桶内 key 决定是不是
            if(x.key == key) return true;
        }
        return false;
    }

    void insert(node node)
    {
        long long hash = hashFunc(node.key);
        for(auto &x : v[hash])
        {
            if(x.key == node.key)
            {
                // 键相同则为修改
                x.val = node.val;
                return;
            }
        }
        v[hash].push_back({node.key, node.val});
    }

    bool remove(long long key)
    {
        long long hash = hashFunc(key);
        auto &bucket = v[hash];  // 避免拷贝，提高效率
        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
            if (it->key == key) {
                bucket.erase(it);
                return true;
            }
        }
        return false;
    }
};

常用的 HASH_SIZE 有 100003、1000003、2000003 等，注意要选取质数

其实也可以把链表换成其他数据结构（如平衡树），但也有相应的代价，一般用链表即可

开放寻址法

开放寻址法（Open Addressing）是另一种解决哈希冲突的核心方法，其核心思想与链表法完全不同：不引入额外数据结构，所有键值对直接存储在哈希表的数组（桶数组）中

当发生哈希冲突时，通过特定的「探测策略」在数组中寻找下一个空闲的桶，直到找到空位或遍历完数组

一定程度上性能可能优于链表法，但大小固定不能扩容，且删除操作较为复杂

线性探测

线性探测法（Linear Probing）是最简单的开放寻址法，当发生哈希冲突时，线性探测法会依次「向后」探测相邻的桶，直到找到一个空闲的桶为止

无删除操作版

这一版代码在洛谷模板题上运行速度远大于链表法

constexpr int HASH_SIZE = 1e7+19;

struct Node
{
    long long key{};
    long long val{0};
    bool occupied{false};
};

class HashTable
{
    vector<Node> v;
    static long long hashFunc(const long long num)
    {
        return (num + HASH_SIZE) % HASH_SIZE;
    }
public:
    HashTable()
    {
        v.resize(HASH_SIZE);
    }

    bool find(const long long key)
    {
        long long hash = hashFunc(key);
        long long start = hash;
        // 线性探测查找 key
        while (v[hash].occupied)
        {
            if (v[hash].key == key)
            {
                return true;
            }
            hash = (hash + 1) % HASH_SIZE; // 循环式
            // 如果回到起点，说明已经遍历了整个表
            if (hash == start) break;
        }
        return false;
    }

    void insert(const long long key, const long long val)
    {
        long long hash = hashFunc(key);
        long long start = hash;
        while (true)
        {
            // 如果位置为空或者 key 相同
            if (!v[hash].occupied || v[hash].key == key)
            {
                v[hash].key = key;
                v[hash].val = val;
                v[hash].occupied = true;
                return;
            }
            hash = (hash + 1) % HASH_SIZE;
            if (hash == start) return;
        }
    }
};

有删除操作版

constexpr int HASH_SIZE = 1e7 + 19;

struct Node
{
    long long key{};
    long long val{0};
    bool occupied{false}; // 是否被占用（含有效/已删除状态）
    bool deleted{false};  // 标记是否删除（仅occupied=true时有效）
};

class HashTable
{
    vector<Node> v;
    static long long hashFunc(const long long num)
    {
        return (num + HASH_SIZE) % HASH_SIZE;
    }

public:
    HashTable()
    {
        v.resize(HASH_SIZE);
    }

    bool find(const long long key)
    {
        long long hash = hashFunc(key);
        long long start = hash;
        do
        {
            Node& node = v[hash];
            if (!node.occupied)
            {
                return false; // 遇到未占用节点，探测链终止
            }
            if (!node.deleted && node.key == key)
            {
                return true; // 找到有效节点（未删除且key匹配）
            }
            hash = (hash + 1) % HASH_SIZE;
        } while (hash != start);

        return false;
    }

    // 插入/更新 key-value：复用已删除节点，覆盖相同 key
    void insert(const long long key, const long long val)
    {
        long long hash = hashFunc(key);
        long long start = hash;
        long long first_deleted = -1; // 记录第一个遇到的已删除节点（优先复用）
        do
        {
            Node& node = v[hash];
            // 情况1：找到未占用节点或已删除节点，直接插入/复用
            if (!node.occupied || node.deleted)
            {
                if (first_deleted == -1)
                {
                    first_deleted = hash; // 记录首个可复用位置
                }
                break;
            }
            // 情况2：找到相同key的有效节点，直接更新val
            if (node.key == key)
            {
                node.val = val;
                return;
            }
            hash = (hash + 1) % HASH_SIZE;
        } while (hash != start);

        // 插入到首个可复用位置（未占用或已删除）
        if (first_deleted != -1)
        {
            Node& node = v[first_deleted];
            node.key = key;
            node.val = val;
            node.occupied = true;
            node.deleted = false; // 标记为有效占用
        }
    }

    // 删除key：返回是否删除成功（仅标记deleted=true，懒删除）
    bool erase(const long long key)
    {
        long long hash = hashFunc(key);
        long long start = hash;
        do
        {
            Node& node = v[hash];
            if (!node.occupied)
            {
                return false; // 遇到未占用节点，无此 key
            }
            if (!node.deleted && node.key == key)
            {
                node.deleted = true; // 标记为删除，保留occupied=true（不中断探测链）
                return true;
            }
            hash = (hash + 1) % HASH_SIZE;
        } while (hash != start);
        return false;
    }
};

二次探测

所谓 “二次” 即进行三种操作时手动记录当前步长 i（从 0 开始，可使用 for 循环或定义一个新变量），然后使用 (hash + c_1 * i * i + c_2 * i) % HASH_SIZE 的方式探测下一个位置，其余操作与线性探测相同

一定程度上能优化聚集问题，但无法完全避免

在洛谷交了一发，但没有通过

双重哈希

双重哈希是开放寻址法中一种高效的冲突探测策略，通过两个独立的哈希函数确定探测序列，从而避免线性探测和二次探测的聚集问题

h(k,i)=(h_1(k)+i*h_2(k))\mod\ m

\(h_1(k)\)：主哈希函数，用于确定键 k 的初始位置
\(h_2(k)\)：辅助哈希函数，用于确定每次探测的步长
\(m\)：哈希表大小

哈希函数要求：为保证探测序列能遍历哈希表所有位置，\(h_1(k)\)需满足与 \(m\) 互质

常见设计示例：

h_2(k) = 1 + (k\mod (m-1))

因 \(m\) 是质数，\(m-1\) 与 \(m\) 互质，故该式返回值与 \(m\) 互质

优势：解决聚集问题

探测方法	问题类型	双重哈希的改进
线性探测	主聚集（连续冲突）	双重哈希的步长由 \(h_2(k)\) 动态决定，避免连续位置的重复探测
二次探测	次聚集（周期冲突）	两个独立哈希函数的结合使探测序列更“随机”，打破固定周期的聚集模式

constexpr int HASH_SIZE = 2000003;

struct Node
{
    long long key{};
    long long val{0};
    bool occupied{false};
};

class DoubleHashTable
{
    vector<Node> v;

    // 主哈希函数：确定初始位置
    static long long h1(long long key)
    {
        return (key % HASH_SIZE + HASH_SIZE) % HASH_SIZE;
    }

    // 辅助哈希函数：确定步长，保证与HASH_SIZE互质
    static long long h2(long long key)
    {
        return 1 + (key % (HASH_SIZE - 1));
    }

public:
    DoubleHashTable()
    {
        v.resize(HASH_SIZE);
    }

    // 查找操作
    bool find(long long key)
    {
        long long initHash = h1(key);
        long long step = h2(key);
        long long hash = initHash;
        int i = 0;
        while (v[hash].occupied)
        {
            if (v[hash].key == key)
            {
                return true;
            }
            // 计算下一个探测位置：(h1 + i*h2) % m
            hash = (h1(key) + i * step) % HASH_SIZE;
            i++;
            if (hash == initHash)
            {
                break;
            }
        }
        return false;
    }

    // 插入操作
    void insert(long long key, long long val)
    {
        long long initHash = h1(key);
        long long step = h2(key);
        long long hash = initHash;
        int i = 0;
        while (true)
        {
            if (!v[hash].occupied || v[hash].key == key)
            {
                v[hash].key = key;
                v[hash].val = val;
                v[hash].occupied = true;
                return;
            }
            // 计算下一个探测位置
            hash = (h1(key) + i * step) % HASH_SIZE;
            i++;
            if (hash == initHash) // 哈希表已满，无法插入
            {
                return;
            }
        }
    }
    // 删除操作（需标记删除以维持探测链，逻辑类似开放寻址法，略）
};

在洛谷交了一发，但没有通过，且失败的测试点和二次探测相同有坑？后续再填吧… // todo