使用JavaScript實現(xiàn)一個簡單的哈希映射功能

更新時間：2024年02月28日 08:27:43 作者：JYeontu

哈希表大家應(yīng)該都經(jīng)常用到吧,那么大家有沒有想過哈希表是怎么實現(xiàn)的呢,本文我們就來從一道簡單的題目來了解一下哈希表的簡單原理和實現(xiàn)吧

說在前面

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

目的

不使用任何內(nèi)建的哈希表庫設(shè)計一個哈希映射（HashMap）。

實現(xiàn) MyHashMap 類：

MyHashMap() 用空映射初始化對象
void put(int key, int value) 向 HashMap 插入一個鍵值對 (key, value) 。如果 key 已經(jīng)存在于映射中，則更新其對應(yīng)的值 value 。
int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
void remove(key) 如果映射中存在 key 的映射，則移除 key 和它所對應(yīng)的 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 現(xiàn)在為 [[1,1]]
myHashMap.put(2, 2); // myHashMap 現(xiàn)在為 [[1,1], [2,2]]
myHashMap.get(1);    // 返回 1 ，myHashMap 現(xiàn)在為 [[1,1], [2,2]]
myHashMap.get(3);    // 返回 -1（未找到），myHashMap 現(xiàn)在為 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 現(xiàn)在為 [[1,1], [2,1]]（更新已有的值）
myHashMap.get(2);    // 返回 1 ，myHashMap 現(xiàn)在為 [[1,1], [2,1]]
myHashMap.remove(2); // 刪除鍵為 2 的數(shù)據(jù)，myHashMap 現(xiàn)在為 [[1,1]]
myHashMap.get(2);    // 返回 -1（未找到），myHashMap 現(xiàn)在為 [[1,1]]

提示：

0 <= key, value <= 10^6

最多調(diào)用 10^4 次 put、get 和 remove 方法

實現(xiàn)思路

什么是哈希表

哈希表是一種通過將鍵映射到特定位置來實現(xiàn)快速查找的數(shù)據(jù)結(jié)構(gòu)。它的設(shè)計原理主要包括以下幾個關(guān)鍵概念：

哈希函數(shù)：哈希表的核心在于哈希函數(shù)，它能夠?qū)⑷我獯笮〉妮斎霐?shù)據(jù)轉(zhuǎn)換成固定大小的輸出值（通常是一個整數(shù)），并且應(yīng)該盡可能地降低沖突的概率。一個好的哈希函數(shù)應(yīng)該具有均勻分布性，即對于輸入的改變，哈希值的變化應(yīng)該是不可預(yù)測的。這樣可以盡可能地避免鍵的碰撞，提高哈希表的性能。
數(shù)組存儲：哈希表內(nèi)部通常采用數(shù)組來存儲數(shù)據(jù)。哈希函數(shù)會將鍵映射到數(shù)組的特定位置，這個位置通常被稱為槽（slot）。在大多數(shù)情況下，哈希表的槽數(shù)量會遠(yuǎn)遠(yuǎn)大于實際存儲的元素數(shù)量，以減少碰撞的概率。
解決碰撞：由于哈希函數(shù)的輸出空間通常要小于輸入空間，所以不同的鍵可能會映射到同一個槽中，造成碰撞（collision）。解決碰撞的常見方法包括鏈地址法（Chaining）和開放尋址法（Open Addressing）等。鏈地址法將同一個槽中的元素組織成鏈表、樹或者其他數(shù)據(jù)結(jié)構(gòu)；開放尋址法則在發(fā)生碰撞時尋找下一個可用的槽位。
性能分析：對于哈希表的性能分析包括哈希函數(shù)的設(shè)計、負(fù)載因子的管理、碰撞處理的效率等方面。良好的哈希函數(shù)和合理的負(fù)載因子管理能夠有效地提高哈希表的性能。

總的來說，哈希表通過哈希函數(shù)將鍵映射到數(shù)組中的特定位置，從而實現(xiàn)了快速的查找、插入和刪除操作。良好的哈希表設(shè)計能夠在平均情況下獲得較高的性能，成為計算機(jī)科學(xué)中重要的數(shù)據(jù)結(jié)構(gòu)之一。

分配數(shù)組空間

分配指定長度的數(shù)組作為存儲空間。

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為數(shù)字，所以我們可以簡單的通過求模來作為每個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);
}

到此這篇關(guān)于使用JavaScript實現(xiàn)一個簡單的哈希映射功能的文章就介紹到這了,更多相關(guān)JavaScript哈希映射內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: