概述

散列表（又称哈希表，Hash Table）是一种常用数据结构。它按照哈希特征分类存放，能够实现插入O(1)，查询均摊较低，几乎可做到O(1)，最差O(n)。本文中介绍的是HashMap的写法（即，散列表存放键值对）。

结构与实现

结构

散列表的结构为每个Hash值下挂一链表，存放属于该Hash值的元素。对于HashMap，我们对key进行Hash即可。

插入

先查找是否存在，存在则覆盖值，否则新建节点挂进链表中。

inline void insert(LL k, LL v) {
    int idx = k % MO;
    for(int i = head[idx]; ~i; i = nxt[i]) {
        if(key[i] == k) {
            value[i] = v;
            return;
        }
    }
    key[tot] = k; value[tot] = v; nxt[tot] = head[idx]; head[idx] = tot++;
}

查找

直接求Hash后对链表遍历即可。

inline LL query(LL k) const {
    int idx = k % MO;
    for(int i = head[idx]; ~i; i = nxt[i]) {
        if(key[i] == k) return value[i];
    }
    return -1;
}

代码

需要手动规定Hash的模数MO。

struct HashMap {
    LL head[MO + 5], key[MAXN], value[MAXN], nxt[MAXN], tot;
    inline void clear() {
        tot = 0;
        memset(head, -1, sizeof(head));
    }
    HashMap() {
        clear();
    }
    inline void insert(LL k, LL v) {
        int idx = k % MO;
        for(int i = head[idx]; ~i; i = nxt[i]) {
            if(key[i] == k) {
                value[i] = v;
                return;
            }
        }
        key[tot] = k; value[tot] = v; nxt[tot] = head[idx]; head[idx] = tot++;
    }
    inline LL operator[](const LL &k) const {
        int idx = k % MO;
        for(int i = head[idx]; ~i; i = nxt[i]) {
            if(key[i] == k) return value[i];
        }
        return -1;
    }
};