實現一個簡單的哈希映射功能

說在前面

🎈哈希表大家應該都經常用到吧，那么大家有沒有想過哈希表是怎么實現的呢？今天讓我們一起從一道簡單的題目來初步了解一個哈希表的簡單原理。

目的

不使用任何內建的哈希表庫設計一個哈希映射（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]]

實現思路

什么是哈希表

哈希表是一種通過將鍵映射到特定位置來實現快速查找的數據結構。它的設計原理主要包括以下幾個關鍵概念：

哈希函數：哈希表的核心在于哈希函數，它能夠將任意大小的輸入數據轉換成固定大小的輸出值（通常是一個整數），并且應該盡可能地降低沖突的概率。一個好的哈希函數應該具有均勻分布性，即對于輸入的改變，哈希值的變化應該是不可預測的。這樣可以盡可能地避免鍵的碰撞，提高哈希表的性能。
數組存儲：哈希表內部通常采用數組來存儲數據。哈希函數會將鍵映射到數組的特定位置，這個位置通常被稱為槽（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()));
};

分配指定長度的數組作為存儲空間，這里我們使用一個長度為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;
};

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;
};

首先，通過調用 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];
};

首先，通過調用 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);
};

首先，通過調用 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);
};

公眾號

關注公眾號『前端也能這么有趣』，獲取更多有趣內容。

說在后面

🎉 這里是 JYeontu，現在是一名前端工程師，有空會刷刷算法題，平時喜歡打羽毛球 🏸 ，平時也喜歡寫些東西，既為自己記錄 📋，也希望可以對大家有那么一丟丟的幫助，寫的不好望多多諒解 🙇，寫錯的地方望指出，定會認真改進 😊，偶爾也會在自己的公眾號『前端也能這么有趣』發一些比較有趣的文章，有興趣的也可以關注下。在此謝謝大家的支持，我們下文再見 🙌。