标签: Hash

散列表(HashMap)原理与实现

散列表(HashMap)原理与实现

概述

散列表(又称哈希表,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;
    }
};