JavaScript 哈希表

2025 年 3 月 2 日 | 6 分钟阅读

JavaScript 中的哈希表是什么？

在 JavaScript 中，哈希表（也称为散列映射）被认为是一种数据结构，可以帮助我们更有效地存储键值对。使用哈希函数，我们可以将键映射到数组中的索引，从而实现更快的插入和数据检索。

简而言之，它是一种可用于创建成对值列表的数据结构。使用哈希表，我们可以通过该值的键来检索特定值，而该值可以插入到表中。

哈希表是 JavaScript 中最重要且广泛使用的数据结构之一。JavaScript 内置的 Map 对象充当哈希表。它有一个 `set()` 方法用于添加新的键值对，以及一个 `get()` 方法用于根据键获取值。此映射还有一个 `has()` 方法用于检查键是否存在，以及一个 `delete()` 方法用于删除键值对。

哈希表由两部分组成

Object

一个用于存储数据的表对象。数组保存表中的所有键值条目。数组的大小应根据预期数据量进行设置。

哈希函数

此函数有助于确定键值对的索引。它应该是一个单向函数，并且为每个键生成不同的哈希值。

哈希表是如何工作的？

在 JavaScript 中，哈希表由数组和哈希函数组成。哈希函数以键作为输入，并返回存储或检索与键关联的值的索引。

让我们举一个简单的例子来帮助您理解哈希表的概念：现在，假设您有一个包含数千本书的大型图书馆。要找到一本书，我们需要搜索所有书架，直到找到我们想要的。这可能需要很长时间。

现在想象一下，如果您有一个魔术函数，可以准确地告诉您书在哪一层架子上。我们就再也不需要搜索所有书架了，可以直接找到架子并找到书。这个魔术函数就像哈希表中的哈希函数，而图书馆中的书架就像数组。

为什么哈希表有用？

在 JavaScript 中，哈希表因多种原因而成为有益且高效的数据结构

快速查找

在 JavaScript 中，借助良好的哈希函数，我们可以提供恒定时间 (O(1)) 的查找，这意味着查找值所需的时间不取决于表中的元素数量。

灵活的键

在 JavaScript 中，通过使用哈希表，我们可以允许您使用任何数据类型作为键，这使其非常灵活且通用。

无重复键

由于哈希表中的每个键都必须是唯一的，因此您不必担心重复的键会覆盖值。

这些功能使哈希表非常适合存储配置设置、缓存数据、计算文本中单词的频率或实现自动完成等功能。

示例

 
class HashTable {
    constructor(size = 53) {
      this.keyMap = new Array(size);
    }
  
    _hash(key) {
        let total = 0;
        let WEIRD_PRIME = 31;
        for (let i = 0; i < Math.min(key.length, 100); i++) {
          let char = key[i];
          let value = char.charCodeAt(0) - 96;
          total = (total * WEIRD_PRIME + value) % this.keyMap.length;
        }
        return total;
      }
      set(key, value) {
        let index = this._hash(key);
        if (!this.keyMap[index]) {
          this.keyMap[index] = [];
        }
        this.keyMap[index].push([key, value]);
      }
      get(key) {
        let index = this._hash(key);
        if (this.keyMap[index]) {
          for (let i = 0; i < this.keyMap[index].length; i++) {
            if (this.keyMap[index][i][0] === key) {
              return this.keyMap[index][i][1];
            }
          }
        }
        return undefined;
      }
      keys() {
        let keysArr = [];
        for (let i = 0; i < this.keyMap.length; i++) {
          if (this.keyMap[i]) {
            for (let j = 0; j < this.keyMap[i].length; j++) {
              if (!keysArr.includes(this.keyMap[i][j][0])) {
                keysArr.push(this.keyMap[i][j][0])
              }
            }
          }
        }
        return keysArr;
      }
      values() {
        let valuesArr = [];
        for (let i = 0; i < this.keyMap.length; i++) {
          if (this.keyMap[i]) {
            for (let j = 0; j < this.keyMap[i].length; j++) {
              if (!valuesArr.includes(this.keyMap[i][j][1])) {
                valuesArr.push(this.keyMap[i][j][1])
              }
            }
          }
        }
        return valuesArr;
      }
    }   

此实现包含以下方法

constructor(size): 它将使用给定的大小初始化一个新的哈希表。默认大小为 53。
_hash(key): 对给定的键进行哈希处理，并返回一个整数，表示键对应该存储在 keymap 数组中的索引。
set(key, value): 它在哈希表中存储一个键值对。
get(key): 它返回与给定键关联的值，如果哈希表中找不到该键，则返回 undefined。
keys(): 它返回哈希表中所有键的数组。
values(): 它返回哈希表中所有值的数组。

常见的哈希函数

有不同种类的哈希函数，用途也不同，例如

算术模运算：在此函数中，我们将键与列表/数组大小进行模运算：index= key MOD tableSize。因此，索引将始终保持在 0 和 tableSize -1 之间。
截断：在这里，我们选择键的一部分作为索引，而不是整个键。我们可以为此操作使用模函数，但它不一定基于数组大小。
折叠：通过这种方法，它将键分成小块，并在每个块上应用不同的算术策略。

哈希表冲突

在 JavaScript 中，有时哈希函数会为多个键生成相同的索引。此过程称为哈希冲突。在 JavaScript 中，冲突是一个问题，因为哈希表中的每个槽都应该存储一个元素。

我们可以使用四种常见策略来处理哈希冲突

线性探测

线性探测是一种通过跳过已填充的索引来工作的过程。我们可以通过向已计算的索引添加一个偏移值来实现线性探测。现在，如果该索引也已填充，则再次添加，依此类推。

但是，使用此策略有一个缺点是，如果我们没有明智地选择偏移量，我们可能会跳回到起点，从而错过数组中的许多可能位置。

链式调用：

在链式策略中，我们的哈希表的每个槽都保存一个指向另一个数据结构（如链表或树）的指针。该索引处的每个条目都将被插入到该索引的链表中。

正如您所见，链式方法允许我们在恒定时间内将多个键值对哈希到同一个索引。此策略极大地提高了性能，但以空间为代价。

调整数组或列表的大小

在 JavaScript 中，减少冲突的另一种方法是调整列表或数组的大小。在 JavaScript 中，我们可以设置一个阈值，一旦超过该阈值，我们就可以创建一个大小是原始大小两倍的新表。我们所要做的就是从上一个表中复制元素。

我们可以通过调整列表或数组的大小来显著减少冲突，但该函数本身成本很高。因此，我们需要注意设置的阈值。一个常见的约定是将阈值设置为 0.6，这意味着当表中有 60% 被填充时，就需要进行调整大小操作。

双重哈希

在双重哈希中，有两个哈希函数。第二个哈希函数用于在第一个函数导致冲突时提供偏移量。通过使用双重哈希，我们可以比线性探测方法更快地找到下一个可用槽。它适用于具有较小哈希表的应用程序。

下面的函数是双重哈希的一个示例

结论

哈希表是一种将键映射到值的结构，用于高效的搜索、插入和删除操作。

它包括一个用于存储数据的对象（数组）和一个用于确定键值对索引的哈希函数。

哈希表非常适合大型数据集，并且平均而言提供了恒定的搜索时间复杂度。

常见的哈希函数包括算术模运算、截断和折叠。

哈希冲突（当两个键具有相同索引时）通过线性探测、链式法、调整大小和双重哈希等策略进行处理。

下一主题JavaScript 中的组合

JavaScript 哈希表