当前位置：首页 > JavaScript

js实现hashtable

2026-02-02 04:03:20JavaScript

实现哈希表的基本结构

哈希表（Hash Table）是一种通过键（key）直接访问值（value）的数据结构。在 JavaScript 中，可以使用对象或 Map 来实现哈希表的功能。以下是两种常见的实现方式。

使用对象实现哈希表

JavaScript 的对象本质上是键值对的集合，可以天然地作为哈希表使用。键通常是字符串或 Symbol 类型。

const hashTable = {};
hashTable["key1"] = "value1";
hashTable["key2"] = "value2";

console.log(hashTable["key1"]); // 输出: value1
console.log(hashTable["key2"]); // 输出: value2

使用 `Map` 实现哈希表

ES6 引入了 Map 数据结构，提供了更完整的哈希表功能，支持任意类型的键（包括对象）。

const hashMap = new Map();
hashMap.set("key1", "value1");
hashMap.set("key2", "value2");

console.log(hashMap.get("key1")); // 输出: value1
console.log(hashMap.get("key2")); // 输出: value2

自定义哈希表实现

如果需要更底层地实现哈希表，可以手动处理哈希函数和冲突解决。以下是一个简单的自定义哈希表实现示例。

定义哈希函数

哈希函数将键转换为数组索引。这里使用简单的取模运算。

function hash(key, size) {
  let hashValue = 0;
  for (let i = 0; i < key.length; i++) {
    hashValue += key.charCodeAt(i);
  }
  return hashValue % size;
}

处理冲突

冲突是指多个键映射到同一个索引。常用的冲突解决方法包括链地址法（使用链表存储冲突的键值对）和开放寻址法（寻找下一个空闲位置）。以下是链地址法的实现。

class HashTable {
  constructor(size = 10) {
    this.size = size;
    this.buckets = Array(size).fill(null).map(() => []);
  }

  set(key, value) {
    const index = hash(key, this.size);
    const bucket = this.buckets[index];
    const found = bucket.find(item => item.key === key);

    if (found) {
      found.value = value;
    } else {
      bucket.push({ key, value });
    }
  }

  get(key) {
    const index = hash(key, this.size);
    const bucket = this.buckets[index];
    const found = bucket.find(item => item.key === key);

    return found ? found.value : undefined;
  }

  delete(key) {
    const index = hash(key, this.size);
    const bucket = this.buckets[index];
    const itemIndex = bucket.findIndex(item => item.key === key);

    if (itemIndex >= 0) {
      bucket.splice(itemIndex, 1);
      return true;
    }
    return false;
  }
}

使用自定义哈希表

const table = new HashTable();
table.set("name", "Alice");
table.set("age", 25);

console.log(table.get("name")); // 输出: Alice
console.log(table.get("age"));  // 输出: 25

table.delete("age");
console.log(table.get("age"));  // 输出: undefined