使用JavaScript怎么实现哈希表

哈希表是一种常见的数据结构，可以在常数时间内（即 O（1）时间复杂度）插入、删除和查找元素。在哈希表中，元素存储在一种称为哈希表的数组中，这个数组是通过哈希函数将键映射到特定位置的。

在JavaScript中实现哈希表需要以下几个步骤：

1.创建哈希表类

我们需要定义一个哈希表类，其中包括一些基本的哈希表操作，如put（插入）, get（获取）和remove（删除）。

class HashTable {
  constructor() {
    this.storage = {}; //存储元素的数组
  }

  //插入
  put(key, value) {
    const hash = this.hashFunction(key);
    if (!this.storage[hash]) {
      this.storage[hash] = [];
    }
    this.storage[hash].push([key, value]);
  }

  //获取
  get(key) {
    const hash = this.hashFunction(key);
    if (this.storage[hash]) {
      for (let i = 0; i < this.storage[hash].length; i++) {
        if (this.storage[hash][i][0] === key) {
          return this.storage[hash][i][1];
        }
      }
    }
    return undefined;
  }

  //删除
  remove(key) {
    const hash = this.hashFunction(key);
    if (this.storage[hash]) {
      for (let i = 0; i < this.storage[hash].length; i++) {
        if (this.storage[hash][i][0] === key) {
          const removedValue = this.storage[hash][i][1];
          this.storage[hash].splice(i, 1); //从内部数组中删除元素
          if (this.storage[hash].length === 0) {
            delete this.storage[hash];
          }
          return removedValue;
        }
      }
    }
    return undefined;
  }

  //哈希函数
  hashFunction(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      const char = key.charCodeAt(i);
      hash = hash + char;
    }
    return hash % 37;
  }
}

在上面的示例中，我们使用对象实现哈希表。在构造函数中，我们初始化storage为对象，其中我们将要存储所有元素。我们还在类中包含3个方法，即put（插入）, get（获取）和remove（删除）。最后，hash函数用于将键转换为其在hash表中的索引。

2.测试哈希表

我们需要测试上面实现的哈希表。我们编写一个简单的测试函数，其中使用一些键和值，如下所示：

function testHashTable() {
  const hashTable = new HashTable();
  hashTable.put('apple', 1);
  hashTable.put('banana', 2);
  hashTable.put('cherry', 3);

  console.log(hashTable.get('apple')); // 应打印1
  console.log(hashTable.get('banana')); // 应打印2
  console.log(hashTable.get('cherry')); // 应打印3

  hashTable.remove('banana');

  console.log(hashTable.get('banana')); // 应打印undefined
}

在这个测试函数中，我们创建一个HashTable实例并插入三个键-值对。然后，我们对这些键执行get操作，并打印相应的值。接下来，我们删除一个键（banana）并再次尝试获取它的值，应该返回undefined。

完成上述测试后，就可以确保我们的哈希表代码正常运行。

总结

在JavaScript中实现哈希表需要以下基本步骤。首先，我们需要定义一个哈希表类，并实现基本的插入、获取、和删除操作。之后，我们需要实现一个哈希函数来将键映射到正确的数组索引上。最后，我们可以使用一个简单的测试函数来验证代码的正确性。