TNotes.leetcode

Appearance

0706. 设计哈希映射【简单】

0706. 设计哈希映射【简单】 ​

1. 📝 题目描述 ​

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

  • MyHashMap() 用空映射初始化对象
  • void put(int key, int value) 向 HashMap 插入一个键值对 (key, value)。如果 key 已经存在于映射中，则更新其对应的值 value。
  • int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1。
  • void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value。

示例：

txt
输入：
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出：
[null, null, null, 1, -1, null, 1, null, -1]

解释：
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1);    // 返回 1，myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3);    // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值）
myHashMap.get(2);    // 返回 1，myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]]
myHashMap.get(2);    // 返回 -1（未找到），myHashMap 现在为 [[1,1]]

提示：

  • 0 <= key, value <= 10^6
  • 最多调用 10^4 次 put、get 和 remove 方法

2. 🫧 评价 ​

  • 题目要求中禁止使用内置的哈希结构，比如在 JS 中，这就意味着你无法使用内置的对象、Map 这些结构来实现。
  • 让我们了解日常开发中使用的 key-val 键值对这样的数据结构的内部实现原理，也正是本题的考查目的之一。
  • s.1 链地址法中的关键：
    • 理解为什么将 size 设置为 10000 -> 可以参考笔记中记录的 AI 回复
    • 理解为什么需要 next 指针 -> 解决哈西冲突

3. 🎯 s.1 - 链地址法实现哈希表 ​

js
// 链表节点类
class ListNode {
  constructor(key, value) {
    this.key = key
    this.value = value
    this.next = null
  }
}

var MyHashMap = function () {
  this.size = 10000 // 哈希表大小
  this.buckets = new Array(this.size).fill(null) // 初始化桶数组

  // 提示中提到最多调用 10^4 次 put、get 和 remove 方法
  // 因此这里最多可能会需要开辟 10^4 个空间
  // 但是 key, value 的范围大于 10^4，这意味着会存在哈希冲突的问题，可以通过 ListNode 中的 next 来解决。
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
MyHashMap.prototype.put = function (key, value) {
  const index = key % this.size

  // 如果该桶为空，直接插入新节点
  if (this.buckets[index] === null) {
    this.buckets[index] = new ListNode(key, value)
    return
  }

  // 遍历链表查找是否已存在该key
  let curr = this.buckets[index]
  while (curr) {
    if (curr.key === key) {
      // 更新已存在的key的值
      curr.value = value
      return
    }
    if (curr.next === null) break
    curr = curr.next
  }

  // 在链表末尾添加新节点
  curr.next = new ListNode(key, value)
}

/**
 * @param {number} key
 * @return {number}
 */
MyHashMap.prototype.get = function (key) {
  const index = key % this.size

  let curr = this.buckets[index]
  while (curr) {
    if (curr.key === key) {
      return curr.value
    }
    curr = curr.next
  }

  return -1 // 未找到返回-1
}

/**
 * @param {number} key
 * @return {void}
 */
MyHashMap.prototype.remove = function (key) {
  const index = key % this.size

  // 如果该桶为空，直接返回
  if (this.buckets[index] === null) {
    return
  }

  // 如果要删除的是头节点
  if (this.buckets[index].key === key) {
    this.buckets[index] = this.buckets[index].next
    return
  }

  // 查找要删除的节点
  let prev = this.buckets[index]
  let curr = prev.next
  while (curr) {
    if (curr.key === key) {
      prev.next = curr.next // 删除节点
      return
    }
    prev = curr
    curr = curr.next
  }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * var obj = new MyHashMap()
 * obj.put(key,value)
 * var param_2 = obj.get(key)
 * obj.remove(key)
 */
  • 时间复杂度：O(n/k)，其中 n 是哈希表中元素的个数，k 是桶的数量，理想情况下为 O(1)
  • 空间复杂度：O(k+m)，其中 k 是桶的数量，m 是实际存储的键值对数量
  • 🤔 为什么需要 next 指针？
  • 为了解决哈希冲突的问题。
  • 当多个不同的键通过哈希函数（这里是取模运算 key % this.size）计算后得到相同的索引时，就会发生哈希冲突。例如：
js
// 假设 size = 10000
let key1 = 10001 // 10001 % 10000 = 1
let key2 = 20001 // 20001 % 10000 = 1
// key1 和 key2 都映射到索引 1
  • 为了解决冲突，使用链表将映射到同一索引位置的键值对串联起来：
txt
buckets[1]:
[10001, "value1"] -> [20001, "value2"] -> [30001, "value3"] -> null
       ↑                  ↑                  ↑
     节点1              节点2              节点3
  • next 的作用
    • 连接节点：next 指针将同一哈希桶中的多个节点连接成链表
    • 遍历链表：通过 next 可以遍历整个链表查找、更新或删除特定键值对
    • 动态扩展：允许在链表末尾添加新节点，动态处理冲突

4. 🤖 s.1 为什么将 size 设置为 10000？ ​

Qwen3-Max

将 size 设为 10000 是一个基于题目约束的合理工程选择，背后有明确的逻辑依据。下面我们详细解释为什么是 10000，而不是 100、1000 或 100000。

4.1. 📌 题目关键约束（来自 LeetCode 706） ​

  • 最多调用 10⁴ 次 put、get 和 remove 操作。
  • key 的范围是 [0, 10⁶]。
  • 每个 key 最多被 put 一次（或多次更新），所以最多有 10⁴ 个不同的键值对。

这意味着：

  • 哈希表中最多存储 10,000 个元素。

4.2. 🔢 负载因子（Load Factor）是关键 ​

负载因子 = 总元素数 / 桶的数量（size）

  • 如果 size = 100 → 负载因子 ≈ 10000 / 100 = 100 → 平均每个桶有 100 个元素 → 链表很长，性能差（O(100) ≈ O(n)）
  • 如果 size = 1000 → 负载因子 ≈ 10 → 平均链表长度 10，尚可，但仍有优化空间
  • 如果 size = 10000 → 负载因子 ≈ 1 → 平均每个桶只有 1 个元素 → 接近理想哈希表性能（O(1)）
  • 如果 size = 100000 → 负载因子 ≈ 0.1 → 内存浪费严重（90% 的桶是空的）

✅ 所以 10000 是一个“平衡点”：

  • 保证平均链表长度 ≈ 1
  • 内存开销合理（10000 个指针 ≈ 80KB，在现代计算机中微不足道）
  • 避免频繁冲突

4.3. ❓ 为什么不选质数（如 9973）？ ​

理论上，使用质数作为哈希表大小可以减少哈希冲突，尤其是当 key 有规律时（比如都是偶数、都是 10 的倍数等）。

例如：

  • 如果 size = 10000（合数），而所有 key 都是 100 的倍数 → key % 10000 只会落在 0, 100, 200, ..., 9900 这 100 个桶里 → 严重冲突！
  • 如果 size = 9973（质数），即使 key 有规律，模运算结果也会更均匀。

✅ 所以更严谨的做法是选一个接近 10000 的质数，比如：

js
this.size = 9973 // 最接近 10000 的质数之一

但在 LeetCode 的测试用例中：

  • 测试数据通常不会刻意构造最坏情况
  • 10000 已经足够快，能通过所有测试
  • 代码更直观（10⁴ 操作 → 10⁴ 桶）

所以很多题解直接用 10000，牺牲一点理论最优性，换取简洁性。

4.4. ✅ 总结：为什么是 10000？ ​

原因说明
匹配操作上限最多 10⁴ 次操作 → 最多 10⁴ 个元素 → size=10⁴ 使负载因子 ≈1
性能最优平均链表长度 ≈1，get/put/remove 接近 O(1)
内存合理10000 个指针 ≈ 80KB，完全可接受
简单直观数字与题目约束一致，易于理解和记忆
实际够用LeetCode 测试用例不会卡这种实现

💡 最佳实践建议：在面试或竞赛中，用 10000 完全没问题；在工业级代码中，建议用质数（如 9973）并支持动态扩容。

4.5. 🔧 附：如何选质数？ ​

你可以记住几个常用质数：

  • 接近 100 → 97
  • 接近 1000 → 997
  • 接近 10000 → 9973
  • 接近 100000 → 99991

所以更“专业”的写法是：

js
var MyHashMap = function () {
  this.size = 9973 // 质数，减少冲突
  this.buckets = new Array(this.size).fill(null)
}

但原题解用 10000 也完全正确且高效，无需担心。

Discussions