实现一个简单的哈希映射功能

说在前面

🎈哈希表大家应该都经常用到吧，那么大家有没有想过哈希表是怎么实现的呢？今天让我们一起从一道简单的题目来初步了解一个哈希表的简单原理。

目的

不使用任何内建的哈希表库设计一个哈希映射（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]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

实现思路

什么是哈希表

哈希表是一种通过将键映射到特定位置来实现快速查找的数据结构。它的设计原理主要包括以下几个关键概念：

• 哈希函数：哈希表的核心在于哈希函数，它能够将任意大小的输入数据转换成固定大小的输出值（通常是一个整数），并且应该尽可能地降低冲突的概率。一个好的哈希函数应该具有均匀分布性，即对于输入的改变，哈希值的变化应该是不可预测的。这样可以尽可能地避免键的碰撞，提高哈希表的性能。

• 数组存储：哈希表内部通常采用数组来存储数据。哈希函数会将键映射到数组的特定位置，这个位置通常被称为槽（slot）。在大多数情况下，哈希表的槽数量会远远大于实际存储的元素数量，以减少碰撞的概率。

• 解决碰撞：由于哈希函数的输出空间通常要小于输入空间，所以不同的键可能会映射到同一个槽中，造成碰撞（collision）。解决碰撞的常见方法包括链地址法（Chaining）和开放寻址法（Open Addressing）等。链地址法将同一个槽中的元素组织成链表、树或者其他数据结构；开放寻址法则在发生碰撞时寻找下一个可用的槽位。

• 性能分析：对于哈希表的性能分析包括哈希函数的设计、负载因子的管理、碰撞处理的效率等方面。良好的哈希函数和合理的负载因子管理能够有效地提高哈希表的性能。

总的来说，哈希表通过哈希函数将键映射到数组中的特定位置，从而实现了快速的查找、插入和删除操作。良好的哈希表设计能够在平均情况下获得较高的性能，成为计算机科学中重要的数据结构之一。

分配数组空间

var MyHashMap = function () {
  this.BASE = 2000;
  this.data = new Array(this.BASE)
    .fill(0)
    .map(() => new Array(2).fill(0).map(() => new Array()));
};
1
2
3
4
5
6

分配指定长度的数组作为存储空间，这里我们使用一个长度为2000的数组来进行存储。

获取key的哈希值

• 如果传入的键是数字类型，则直接使用取模运算符 % 将键与 this.BASE 相除取余数作为哈希键，并返回结果。
• 如果传入的键不是数字类型，首先将其转换为字符串类型。然后，函数会遍历字符串中的每个字符，获取每个字符的 Unicode 编码值并累加到 sum 变量中。
• 最后，将 sum 变量与 this.BASE 求余数得到最终的哈希键，并返回结果。

这种方法可以更均匀地分布字符串键的哈希键，提高哈希表在处理字符串键时的性能和均匀性。

/**
 * @param {string|number} key
 * @return {string}
 */
this.getHashKey = (key = "") => {
  if (typeof key == "number") {
    return key % this.BASE;
  }
  key += "";
  let sum = 0;
  for(let i = 0; i < key.length; i++){
      sum += key[i].charCodeAt();
  }
  return sum % this.BASE;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

put方法

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
MyHashMap.prototype.put = function (key, value) {
  const index = this.getHashKey(key);
  let keyInd = this.data[index][0].indexOf(key);
  if (keyInd == -1) {
    this.data[index][0].push(key);
    this.data[index][1].push(value);
  } else this.data[index][1][keyInd] = value;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

• 首先，通过调用 this.getHashKey(key) 方法获取键的哈希键 index。
• 然后，使用 key 在 this.data[index][0] 中查找键的索引 keyInd。如果返回值为 -1，表示该键不存在于哈希表中。
• 如果 keyInd 为 -1，说明该键在哈希表中不存在，需要将键和值分别添加到 this.data[index][0] 和 this.data[index][1] 中的相应位置。
• 如果 keyInd 不为 -1，说明该键已存在于哈希表中，只需将 value 替换掉 this.data[index][1] 中对应位置的值。

get方法

/**
 * @param {number} key
 * @return {number}
 */
MyHashMap.prototype.get = function (key) {
  const index = this.getHashKey(key);
  let keyInd = this.data[index][0].indexOf(key);
  if (keyInd == -1) {
    return -1;
  }
  return this.data[index][1][keyInd];
};
1
2
3
4
5
6
7
8
9
10
11
12

• 首先，通过调用 this.getHashKey(key) 方法获取键的哈希键 index。
• 然后，使用 key 在 this.data[index][0] 中查找键的索引 keyInd。如果返回值为 -1，表示该键不存在于哈希表中，直接返回 -1。
• 如果 keyInd 不为 -1，说明该键存在于哈希表中，直接返回 this.data[index][1][keyInd]，即该键对应的值。

remove方法

/**
 * @param {number} key
 * @return {void}
 */
MyHashMap.prototype.remove = function (key) {
  const index = this.getHashKey(key);
  let keyInd = this.data[index][0].indexOf(key);
  if (keyInd == -1) {
    return;
  }
  this.data[index][0].splice(keyInd, 1);
  this.data[index][1].splice(keyInd, 1);
};
1
2
3
4
5
6
7
8
9
10
11
12
13

• 首先，通过调用 this.getHashKey(key) 方法获取键的哈希键 index。
• 然后，使用 key 在 this.data[index][0] 中查找键的索引 keyInd。如果返回值为 -1，表示该键不存在于哈希表中，直接结束函数。
• 如果 keyInd 不为 -1，说明该键存在于哈希表中，通过 splice 方法将该键在 this.data[index][0] 和 this.data[index][1] 中的位置移除。

完整代码

var MyHashMap = function () {
  this.BASE = 2000;
  this.data = new Array(this.BASE)
    .fill(0)
    .map(() => new Array(2).fill(0).map(() => new Array()));
  /**
   * @param {string|number} key
   * @return {string}
   */
  this.getHashKey = (key = "") => {
    if (typeof key == "number") {
      return key % this.BASE;
    }
    key += "";
    let sum = 0;
    for(let i = 0; i < key.length; i++){
        sum += key[i].charCodeAt();
    }
    return sum % this.BASE;
  };
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
MyHashMap.prototype.put = function (key, value) {
  const index = this.getHashKey(key);
  let keyInd = this.data[index][0].indexOf(key);
  if (keyInd == -1) {
    this.data[index][0].push(key);
    this.data[index][1].push(value);
  } else this.data[index][1][keyInd] = value;
};

/**
 * @param {number} key
 * @return {number}
 */
MyHashMap.prototype.get = function (key) {
  const index = this.getHashKey(key);
  let keyInd = this.data[index][0].indexOf(key);
  if (keyInd == -1) {
    return -1;
  }
  return this.data[index][1][keyInd];
};

/**
 * @param {number} key
 * @return {void}
 */
MyHashMap.prototype.remove = function (key) {
  const index = this.getHashKey(key);
  let keyInd = this.data[index][0].indexOf(key);
  if (keyInd == -1) {
    return;
  }
  this.data[index][0].splice(keyInd, 1);
  this.data[index][1].splice(keyInd, 1);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。