说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。
题目描述
不使用任何内建的哈希表库设计一个哈希映射（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）。在大多数情况下，哈希表的槽数量会远远大于实际存储的元素数量，以减少碰撞的概率。
- 解决碰撞：由于哈希函数的输出空间通常要小于输入空间，所以不同的键可能会映射到同一个槽中，造成碰撞（collision）。解决碰撞的常见方法包括链地址法（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); };
AC代码
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); };
公众号
关注公众号『前端也能这么有趣』，获取更多有趣内容。
说在后面
🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
