🗂️ 哈希表 Hash Table 可视化

哈希函数 O(1) 定位桶位置，冲突通过链地址法（链表）或线性探测解决

链地址法（Chaining）：哈希函数 h(key) = key % 10， 冲突的元素挂在同一个桶的链表上。装载因子 = 元素数 / 桶数。
欢迎！体验链地址法哈希表的插入、搜索、删除

开放寻址法：线性探测（Linear Probing）

线性探测：发生冲突时，依次检查 h+1, h+2, h+3...（循环）， 直到找到空槽。查找时沿同样路径，遇到空槽即停止（元素不存在）。
输入值体验线性探测的冲突解决过程

JavaScript 实现（链地址法）

class HashMap {
    constructor(size = 10) {
        this.buckets = Array.from({ length: size }, () => []);
    }

    // 哈希函数 - O(1)
    hash(key) {
        return key % this.buckets.length;
    }

    // 插入 - 平均 O(1)，最坏 O(n)
    put(key, value) {
        const idx = this.hash(key);
        const bucket = this.buckets[idx];
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i].key === key) { bucket[i].value = value; return; }
        }
        bucket.push({ key, value });
    }

    // 查找 - 平均 O(1)
    get(key) {
        const bucket = this.buckets[this.hash(key)];
        for (const item of bucket) {
            if (item.key === key) return item.value;
        }
        return undefined;
    }

    // 删除 - 平均 O(1)
    remove(key) {
        const bucket = this.buckets[this.hash(key)];
        const idx = bucket.findIndex(i => i.key === key);
        if (idx !== -1) return bucket.splice(idx, 1)[0];
        return null;
    }
}

// 线性探测（开放寻址）
class LinearProbingMap {
    constructor(size = 10) {
        this.table = new Array(size).fill(null);
    }

    // 插入：冲突则线性向下探测
    insert(key) {
        let idx = key % this.table.length;
        while (this.table[idx] !== null) {
            idx = (idx + 1) % this.table.length;
        }
        this.table[idx] = key;
    }
}

时间复杂度分析

操作平均最坏说明
插入 InsertO(1)O(n)冲突全集中时退化为 O(n)
查找 SearchO(1)O(n)依赖装载因子 α = n/m
删除 DeleteO(1)O(n)链地址：从链表移除
哈希计算O(1)O(1)取模运算

实际应用场景

  • 🗺️ 语言内置：JS 的 Object/Map、Java 的 HashMap、Python 的 dict
  • 💾 数据库索引：哈希索引加速等值查询
  • 🕸️ 缓存：Redis 核心就是哈希表
  • 🧮 去重：统计出现次数、布隆过滤器基础
  • 📚 编译原理：符号表、变量名查找