使用 Javascript 的哈希映射

介紹

• 雜湊映射（Hash Map），也稱為雜湊表（Hash Table），是實現關聯數組抽象化資料類型的資料結構，是可以將鍵映射到值的結構。

• 它使用雜湊函數來計算儲存桶或槽數組的索引，從中可以找到所需的值。

• 雜湊圖的主要優點是它的效率。插入新的鍵值對、刪除鍵值對以及查找給定鍵的值等操作都非常快，通常平均需要恆定的時間。

在 JavaScript 中實作簡單的哈希映射

let hashMap = {};
hashMap['key1'] = 'value1';
hashMap['key2'] = 'value2';
console.log(hashMap['key1']); // Outputs: value1

處理碰撞

• 處理衝突是實作雜湊映射的重要面向。當兩個不同的金鑰產生相同的雜湊值時，就會發生衝突。處理碰撞的策略有多種，但最常見的兩種是單獨的連結和線性探測。

單獨連結：在單獨連結中，雜湊表數組中的每個槽都包含一個連結清單（或其他可以容納多個項目的資料結構）。當發生衝突時，新的鍵值對會加入到鍊錶對應索引的末端。

這是在 JavaScript 中使用單獨連結的雜湊映射的簡單實作：

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null).map(() => []);
  }

  put(key, value) {
    const index = this.hash(key);
    const chain = this.table[index];
    const existingPair = chain.find(([existingKey]) => existingKey === key);

    if (existingPair) {
      existingPair[1] = value;
    } else {
      chain.push([key, value]);
    }
  }

  get(key) {
    const index = this.hash(key);
    const chain = this.table[index];
    const pair = chain.find(([existingKey]) => existingKey === key);

    if (pair) {
      return pair[1];
    }

    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }
}

線性探測：在線性探測中，當發生衝突時，雜湊映射會檢查數組中的下一個槽（如果也已滿，則繼續到下一個槽，依此類推） ，直到找到一個空槽，可以儲存新的鍵值對。

這是在 JavaScript 中使用線性探測的雜湊映射的簡單實作：

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null);
  }

  put(key, value) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      index = (index + 1) % this.table.length;
    }
    this.table[index] = [key, value];
  }

  get(key) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      if (this.table[index][0] === key) {
        return this.table[index][1];
      }
      index = (index + 1) % this.table.length;
    }
    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }
}

在這兩個範例中，雜湊方法都是一個簡單的雜湊函數，它將鍵轉換為用作數組中索引的整數。在現實場景中，您可能會使用更複雜的雜湊函數來減少衝突的可能性。

以上是使用 Javascript 的哈希映射的詳細內容。更多資訊請關注PHP中文網其他相關文章！