JS实现简单哈希表：MyHashMap类设计与核心方法解析

前言

哈希表是开发者日常接触频繁的数据结构，但你是否思考过其内部实现机制？本文将通过一道基础题目，带你初步探索哈希表的实现原理。

目标

在不依赖任何内置哈希表库的前提下，设计并实现一个哈希映射（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 <= 10^6

方法调用次数上限为 10^4 次，涉及 put、get 和 remove 操作。

实现思路解析

哈希表概念

哈希表是一种通过哈希函数将键映射到特定存储位置，从而实现快速查找的数据结构。其核心设计包含以下关键要素：

哈希函数：作为核心组件，哈希函数将任意大小输入转换为固定大小的输出（通常为整数），并需尽可能降低冲突概率。优秀的哈希函数应具备均匀分布性，即输入微小变化导致哈希值大幅不可预测变化，从而减少键碰撞，提升性能。
数组存储：哈希表底层通常使用数组存储数据。哈希函数将键映射到数组的特定位置，称为槽（slot）。槽数量通常远大于实际元素数，以进一步降低碰撞概率。
冲突解决：由于哈希输出空间小于输入空间，不同键可能映射至同一槽，即发生碰撞。常见解决方案包括链地址法（Chaining）和开放寻址法（Open Addressing）。链地址法将同一槽元素组织为链表、树等结构；开放寻址法则在碰撞时寻找下一个可用槽位。
性能分析：哈希表性能取决于哈希函数设计、负载因子管理及碰撞处理效率。良好的设计与合理的负载因子管理能显著提升性能。

综上，哈希表通过哈希函数将键映射至数组特定位置，实现快速查找、插入和删除。优秀的设计能在平均情况下提供高性能，是计算机科学中至关重要的数据结构。

数组空间分配

分配指定长度的数组作为底层存储空间。

var MyHashMap = function () {
  this.BASE = 666;
  this.data = new Array(this.BASE)
    .fill(0)
    .map(() => new Array(2).fill(0).map(() => new Array()));
};

获取Key的哈希值

本题限制key为数字，因此可通过求模运算直接生成每个key的哈希值。

const index = key % this.BASE;

put方法实现

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
MyHashMap.prototype.put = function (key, value) {
  const index = key % this.BASE;//获取存储哈希
  let keyInd = this.data[index][0].indexOf(key);//获取该key所在位置
  if (keyInd == -1) {//不存在的话直接新增
    this.data[index][0].push(key);
    this.data[index][1].push(value);
  } else this.data[index][1][keyInd] = value;//存在则更新值
};

get方法实现

/**
 * @param {number} key
 * @return {number}
 */
MyHashMap.prototype.get = function (key) {
  const index = key % this.BASE;//获取存储哈希
  let keyInd = this.data[index][0].indexOf(key);//获取该key所在位置
  if (keyInd == -1) {//不存在的话直接返回-1
    return -1;
  }
  return this.data[index][1][keyInd];//存在则返回存储的值
};

remove方法实现

/**
 * @param {number} key
 * @return {void}
 */
MyHashMap.prototype.remove = function (key) {
  const index = key % this.BASE;//获取存储哈希
  let keyInd = this.data[index][0].indexOf(key);//获取该key所在位置
  if (keyInd == -1) {//不存在的话直接返回
    return;
  }
  //存在的话则将key和值都删除
  this.data[index][0].splice(keyInd, 1);
  this.data[index][1].splice(keyInd, 1);
};

完整代码展示

var MyHashMap = function () {
  this.BASE = 666;
  this.data = new Array(this.BASE)
    .fill(0)
    .map(() => new Array(2).fill(0).map(() => new Array()));
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
MyHashMap.prototype.put = function (key, value) {
  const index = key % this.BASE;
  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 = key % this.BASE;
  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 = key % this.BASE;
  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);
}

至此，关于使用JavaScript实现简单哈希映射功能的介绍已完成。如需了解更多JavaScript哈希映射相关内容，请查阅本站往期文章或继续浏览后续内容，感谢支持！

JavaScript 手写实现基础哈希映射（HashMap）

前言

目标