LeetCode 706. 设计哈希映射

约 6 分钟
文章信息 11 个分类 5 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 腾讯 字节 微软 拼多多 百度 携程
标签
数组 哈希表 链表 设计 哈希函数

题目描述

✅ 706. 设计哈希映射

image-20260928222346268

image-20260928222346269

题意分析

不使用内建哈希表，实现键值映射：put 插入或覆盖，get 查询并在键不存在时返回 -1，remove 删除指定键。键和值都非负，删除不存在的键不改变映射。

解法：数组桶 + 链地址法

核心思路

[!blue]

用长度为 BASE 的数组保存各个桶的链表头。键通过 key % BASE 定位到桶；不同键可能得到相同下标，这些冲突键就串在同一条链上。每个节点同时保存 key、value 和 next，因此找到桶后还要比较原始键，不能把桶下标当成键的身份。

put 先查找目标链：找到相同键就覆盖值并返回，走完整条链仍未找到才头插新节点。这样始终保持每个键只有一个节点，get 和 remove 找到一次就可以结束。

删除节点需要让前驱跳过它。给目标链临时接一个虚拟头 dummy，让 pre 始终指向 cur 的前驱，就能用同一句 pre.next = cur.next 删除链首或链中节点。删除后把桶头设为 dummy.next，保证桶数组仍指向正确入口。

解题步骤

  1. 构造 769 个空桶；题目保证键非负，取模结果可直接作为下标。桶数影响冲突多少，不影响映射的正确性。
  2. put：遍历目标链，命中键就更新值并返回；未命中则把新节点插到链头。
  3. get：遍历目标链，命中返回值；走到链尾仍未命中则返回 -1。
  4. remove：令 dummy.next 指向桶头，pre 指向 dummy。查找时同步推进 pre 和 cur；命中则摘链、更新桶头并返回，未命中则不做修改。

代码实现

class MyHashMap {
    private static final int BASE = 769;
    private Node[] buckets;

    public MyHashMap() {
        buckets = new Node[BASE];
    }

    public void put(int key, int value) {
        int index = hash(key);
        Node cur = buckets[index];

        while (cur != null) {
            if (cur.key == key) {
                // 已有键只覆盖值并返回，不能再插入第二个同键节点。
                cur.value = value;

                return;
            }

            cur = cur.next;
        }

        buckets[index] = new Node(key, value, buckets[index]);
    }

    public int get(int key) {
        Node cur = buckets[hash(key)];

        while (cur != null) {
            if (cur.key == key) {
                return cur.value;
            }

            cur = cur.next;
        }

        return -1;
    }

    public void remove(int key) {
        int index = hash(key);
        Node dummy = new Node(-1, -1, buckets[index]);
        Node pre = dummy;
        Node cur = buckets[index];

        while (cur != null) {
            if (cur.key == key) {
                pre.next = cur.next;
                // 删除原桶头时，也要同步更新桶数组保存的入口。
                buckets[index] = dummy.next;

                return;
            }

            pre = cur;
            cur = cur.next;
        }
    }

    private int hash(int key) {
        return key % BASE;
    }

    private static class Node {
        int key;
        int value;
        Node next;

        Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
}

type MyHashMap struct {
    buckets []*HashNode
}

type HashNode struct {
    key   int
    value int
    next  *HashNode
}

func Constructor() MyHashMap {
    return MyHashMap{buckets: make([]*HashNode, 769)}
}

func (this *MyHashMap) Put(key int, value int) {
    index := key % len(this.buckets)
    for cur := this.buckets[index]; cur != nil; cur = cur.next {
        if cur.key == key {
            // 已有键只覆盖值并返回，不能再插入第二个同键节点。
            cur.value = value
            return
        }
    }
    this.buckets[index] = &HashNode{key: key, value: value, next: this.buckets[index]}
}

func (this *MyHashMap) Get(key int) int {
    index := key % len(this.buckets)
    for cur := this.buckets[index]; cur != nil; cur = cur.next {
        if cur.key == key {
            return cur.value
        }
    }
    return -1
}

func (this *MyHashMap) Remove(key int) {
    index := key % len(this.buckets)
    dummy := &HashNode{next: this.buckets[index]}
    pre := dummy
    for cur := this.buckets[index]; cur != nil; cur = cur.next {
        if cur.key == key {
            pre.next = cur.next
            // 删除原桶头时，也要同步更新桶数组保存的入口。
            this.buckets[index] = dummy.next
            return
        }
        pre = cur
    }
}

复杂度分析

  • 时间复杂度：设当前键数为 n、桶数为 b。初始化为 $O(b)$；分布均匀时每次操作平均为 $O(1 + n / b)$，最坏为 $O(n)$。固定桶数和取模哈希不保证键均匀分布。
  • 空间复杂度：$O(n + b)$，分别用于链表节点和桶数组。

关键点总结

[!green]

  • 哈希函数只负责定位桶；节点中的原始 key 才能在发生冲突后确认身份。
  • put 必须先查重再插入，维持「一个键只对应一个节点」的不变量。
  • 桶内操作沿链查找，只有插入或摘链动作本身是 $O(1)$。
  • 虚拟头统一删除逻辑，删除后仍要同步桶数组中的入口。

易错点总结

[!yellow]

  • put 不查重会产生重复节点：更新后再删除一次，旧值可能重新暴露。
  • 节点只存值、不存键时，同一桶中的冲突键无法区分。
  • 删除链首后若没有同步 buckets[index]，桶仍指向已删除节点；虚拟头节点能统一处理。
  • get 未命中必须返回题目规定的 -1，不能用 0，因为 0 本身是合法值。

相似题目

题目 难度 关联与区别
705. 设计哈希集合 简单 哈希分桶与冲突处理结构相同，本题每个键还携带一个可更新值。
146. LRU 缓存 中等 LRU需要由键快速定位节点，哈希映射与双向链表组合后支持常数时间更新顺序。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/96724142
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！