当前位置：首页 > JavaScript

js 实现hashtable

2026-02-02 06:10:50JavaScript

哈希表（HashTable）的基本实现

在 JavaScript 中，哈希表可以通过对象（Object）或 Map 实现。以下是两种常见的实现方式：

使用 Object 实现哈希表

JavaScript 的对象本质上是键值对的集合，可以直接作为哈希表使用。

const hashTable = {};

// 添加键值对
hashTable['key1'] = 'value1';
hashTable['key2'] = 'value2';

// 获取值
console.log(hashTable['key1']); // 输出: value1

// 删除键值对
delete hashTable['key1'];

// 检查键是否存在
console.log('key1' in hashTable); // 输出: false

使用 Map 实现哈希表

ES6 引入的 Map 提供了更强大的哈希表功能，支持任意类型的键（包括对象）。

const hashMap = new Map();

// 添加键值对
hashMap.set('key1', 'value1');
hashMap.set('key2', 'value2');

// 获取值
console.log(hashMap.get('key1')); // 输出: value1

// 删除键值对
hashMap.delete('key1');

// 检查键是否存在
console.log(hashMap.has('key1')); // 输出: false

// 获取大小
console.log(hashMap.size); // 输出: 1

手动实现哈希表

如果需要手动实现哈希表，可以基于数组和哈希函数构建。

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

  // 哈希函数（简单示例）
  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.size;
  }

  // 添加键值对
  set(key, value) {
    const index = this._hash(key);
    const bucket = this.table[index];
    const found = bucket.find(item => item[0] === key);
    if (found) {
      found[1] = value; // 更新值
    } else {
      bucket.push([key, value]); // 添加新键值对
    }
  }

  // 获取值
  get(key) {
    const index = this._hash(key);
    const bucket = this.table[index];
    const found = bucket.find(item => item[0] === key);
    return found ? found[1] : undefined;
  }

  // 删除键值对
  delete(key) {
    const index = this._hash(key);
    const bucket = this.table[index];
    const itemIndex = bucket.findIndex(item => item[0] === key);
    if (itemIndex >= 0) {
      bucket.splice(itemIndex, 1);
      return true;
    }
    return false;
  }
}

// 使用示例
const myHashTable = new HashTable();
myHashTable.set('name', 'Alice');
console.log(myHashTable.get('name')); // 输出: Alice
myHashTable.delete('name');
console.log(myHashTable.get('name')); // 输出: undefined

哈希冲突处理

手动实现时，哈希冲突通过链地址法（每个桶是一个链表或数组）解决。其他方法包括开放寻址法（线性探测、二次探测等）。

js 实现hashtable

开放寻址法示例

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

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

  set(key, value) {
    let index = this._hash(key);
    while (this.table[index] !== null && this.table[index][0] !== key) {
      index = (index + 1) % this.size; // 线性探测
    }
    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.size;
    }
    return undefined;
  }
}