【Leetcode 706 】设计哈希映射——数组嵌套链表（限制哈希Key）

题目

不使用任何内建的哈希表库设计一个哈希映射（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 。

示例：

输入：
["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 <= 106
• 最多调用 104 次 put、get 和 remove 方法

class MyHashMap {
  //创建哈希集合大小，其表现方式为数组
  BASE: number;
  //二维数组，其第二维表现方式为链表 [[[1,1],[2,2]]]
  data: [number, number][][];
  constructor() {
    //初始化集合大小为 1111，注意：该值最好是质数
    this.BASE = 1111;
    // 初始化集合，长度为 BASE，其中每一个值都是一个链表，存储着值
    this.data = new Array(this.BASE).fill(0).map(() => []);
  }

  //   哈希函数，将哈希的key控制在一定范围，如add一万个数据，则可能要有一万个key
  //   哈希函数通过 取模，将key控制在固定范围，相同key的，但不同值，则用链表的方式存储
  //   如 key = 1 ， BASE = 1111   则hashKey = 1
  //     key = 1112 ， BASE = 1111  则hashKey = 1
  getHashKey(key: number) {
    return key % this.BASE;
  }

  put(key: number, value: number): void {
    // 获取该值的 hashKey
    const hashKey = this.getHashKey(key);
    for (const ele of this.data[hashKey]) {
      // 找到则更新value
      if (ele[0] === key) {
        ele[1] = value;
        return;
      }
    }
    // 没找到，则新增
    this.data[hashKey].push([key, value]);
  }

  get(key: number): number {
    // 获取该值的 hashKey
    const hashKey = this.getHashKey(key);
    for (const ele of this.data[hashKey]) {
      // 找到则返回value
      if (ele[0] === key) {
        return ele[1];
      }
    }
    // 没找到，返回-1
    return -1;
  }

  remove(key: number): void {
    // 获取该值的 hashKey
    const hashKey = this.getHashKey(key);
    const d = this.data[hashKey];
    for (let i = 0; i < d.length; i++) {
      // 找到，则删除
      if (d[i][0] === key) {
        d.splice(i, 1);
      }
    }
  }
}