LeetCode 706. 设计哈希映射

Categories:

题目描述
思路分析
1. 解法一：链地址法（推荐）
相似题目

题目描述

✅ 706. 设计哈希映射

思路分析

解法一：链地址法（推荐）

核心思路：

使用固定大小的数组作为哈希桶，桶的数量选取质数（如 1009）以减少哈希碰撞。

哈希函数：hash = key % BUCKET_SIZE，将 key 映射到对应桶的下标。

每个桶存储一条链表，链表节点保存 (key, value) 键值对。

put：先查找链表中是否存在相同 key，有则更新，无则头插或尾插新节点。

get：遍历对应桶的链表，找到匹配 key 则返回 value，否则返回 -1。

remove：遍历链表找到目标节点并将其从链表中摘除。

复杂度分析：

时间复杂度：O(n/b)，其中 n 为元素总数，b 为桶数量；平均情况下每条链表长度为 n/b，查找/插入/删除均为 O(n/b)

空间复杂度：O(n+b)，其中 n 为存储的键值对数量，b 为桶数量

class MyHashMap {

    // 桶数量，选取质数以减少哈希碰撞
    private static final int BUCKET_SIZE = 1009;

    // 链表节点定义
    private static class Node {
        int key;
        int value;
        Node next;

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

    // 哈希桶数组，每个桶使用虚拟头节点简化边界处理
    private final Node[] buckets;

    public MyHashMap() {
        buckets = new Node[BUCKET_SIZE];
        // 初始化每个桶的虚拟头节点
        for (int i = 0; i < BUCKET_SIZE; i++) {
            buckets[i] = new Node(-1, -1);
        }
    }

    // 计算 key 所在桶的下标
    private int hash(int key) {
        return key % BUCKET_SIZE;
    }

    // 在指定桶的链表中查找 key 的前驱节点
    private Node find(Node head, int key) {
        Node prev = head;
        Node cur = head.next;
        while (cur != null && cur.key != key) {
            prev = cur;
            cur = cur.next;
        }
        return prev;
    }

    public void put(int key, int value) {
        int idx = hash(key);
        Node prev = find(buckets[idx], key);
        if (prev.next == null) {
            // key 不存在，插入新节点
            prev.next = new Node(key, value);
        } else {
            // key 已存在，更新 value
            prev.next.value = value;
        }
    }

    public int get(int key) {
        int idx = hash(key);
        Node prev = find(buckets[idx], key);
        if (prev.next == null) {
            return -1;
        }
        return prev.next.value;
    }

    public void remove(int key) {
        int idx = hash(key);
        Node prev = find(buckets[idx], key);
        if (prev.next != null) {
            // 将目标节点从链表中摘除
            prev.next = prev.next.next;
        }
    }
}

const bucketSize = 1009

// node 链表节点
type node struct {
    key   int
    value int
    next  *node
}

// MyHashMap 链地址法实现的哈希映射
type MyHashMap struct {
    // 每个桶使用虚拟头节点简化边界处理
    buckets [bucketSize]*node
}

func Constructor() MyHashMap {
    m := MyHashMap{}
    // 初始化每个桶的虚拟头节点
    for i := range m.buckets {
        m.buckets[i] = &node{}
    }
    return m
}

// hash 计算 key 对应的桶下标
func (m *MyHashMap) hash(key int) int {
    return key % bucketSize
}

// find 返回链表中 key 的前驱节点，若不存在则返回最后一个节点
func (m *MyHashMap) find(head *node, key int) *node {
    prev := head
    cur := head.next
    for cur != nil && cur.key != key {
        prev = cur
        cur = cur.next
    }
    return prev
}

func (m *MyHashMap) Put(key int, value int) {
    idx := m.hash(key)
    prev := m.find(m.buckets[idx], key)
    if prev.next == nil {
        // key 不存在，插入新节点
        prev.next = &node{key: key, value: value}
    } else {
        // key 已存在，更新 value
        prev.next.value = value
    }
}

func (m *MyHashMap) Get(key int) int {
    idx := m.hash(key)
    prev := m.find(m.buckets[idx], key)
    if prev.next == nil {
        return -1
    }
    return prev.next.value
}

func (m *MyHashMap) Remove(key int) {
    idx := m.hash(key)
    prev := m.find(m.buckets[idx], key)
    if prev.next != nil {
        // 将目标节点从链表中摘除
        prev.next = prev.next.next
    }
}

相似题目

题目	难度	考察点
705. 设计哈希集合	简单	哈希表、链地址法
706. 设计哈希映射	简单	哈希表、设计
146. LRU 缓存	中等	哈希表、双向链表
460. LFU 缓存	困难	哈希表、链表、设计
1396. 设计地铁系统	中等	哈希表、设计
1166. 设计文件系统	中等	哈希表、字典树
380. O(1) 时间插入、删除和获取随机元素	中等	哈希表、数组、设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/96724142