当前位置：首页 > JavaScript

js 实现hashtable

2026-04-06 23:27:53JavaScript

实现哈希表的基本结构

哈希表（HashTable）是一种通过键（Key）直接访问值（Value）的数据结构，核心在于哈希函数将键映射到存储位置。以下是用 JavaScript 实现哈希表的关键步骤：

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

哈希函数设计

哈希函数需将任意键转换为固定范围的索引。常用方法是结合字符编码和取模运算：

js 实现hashtable

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

处理键值对插入

使用链地址法解决冲突，将相同哈希值的键值对存储在同一个桶（Bucket）中：

js 实现hashtable

set(key, value) {
  const index = this._hash(key);
  const bucket = this.buckets[index];
  const existingEntry = bucket.find(entry => entry.key === key);

  if (existingEntry) {
    existingEntry.value = value; // 更新现有键
  } else {
    bucket.push({ key, value }); // 新增键值对
  }
}

获取键对应的值

通过哈希定位桶后，遍历桶内元素查找匹配的键：

get(key) {
  const index = this._hash(key);
  const bucket = this.buckets[index];
  const entry = bucket.find(entry => entry.key === key);
  return entry ? entry.value : undefined;
}

删除键值对

从桶中过滤掉指定键的元素：

delete(key) {
  const index = this._hash(key);
  const bucket = this.buckets[index];
  this.buckets[index] = bucket.filter(entry => entry.key !== key);
}

完整代码示例

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

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

  set(key, value) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    const existingEntry = bucket.find(entry => entry.key === key);
    if (existingEntry) {
      existingEntry.value = value;
    } else {
      bucket.push({ key, value });
    }
  }

  get(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    const entry = bucket.find(entry => entry.key === key);
    return entry ? entry.value : undefined;
  }

  delete(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    this.buckets[index] = bucket.filter(entry => entry.key !== key);
  }
}