当前位置：首页 > JavaScript

js实现hashmap

2026-03-14 17:27:39JavaScript

实现基础结构

在JavaScript中，可以通过对象或Map类实现哈希表。对象的方式简单但功能有限，Map则支持更复杂的操作（如任意类型的键）。

使用对象实现

class SimpleHashMap {
  constructor() {
    this.storage = {};
  }

  set(key, value) {
    this.storage[key] = value;
  }

  get(key) {
    return this.storage[key];
  }

  delete(key) {
    delete this.storage[key];
  }
}

使用Map类

js实现hashmap

const map = new Map();
map.set('key', 'value'); // 添加键值对
map.get('key');          // 获取值
map.delete('key');       // 删除键值对

处理冲突（对象方式）

对象的键只能是字符串或Symbol，需处理冲突和哈希计算。可通过以下方法改进：

哈希函数示例

js实现hashmap

_hash(key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + key.charCodeAt(i);
  }
  return hash % 37; // 假设桶大小为37
}

链地址法解决冲突

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

  set(key, value) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    const found = bucket.find(item => item[0] === key);
    found ? found[1] = value : bucket.push([key, value]);
  }

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

性能优化

动态扩容：当元素数量超过负载因子（如75%）时，扩大桶数组并重新哈希所有元素。
素数桶大小：使用素数作为桶大小可减少哈希冲突。

扩容示例

resize(newSize) {
  const oldBuckets = this.buckets;
  this.size = newSize;
  this.buckets = Array(newSize).fill(null).map(() => []);
  oldBuckets.forEach(bucket => {
    bucket.forEach(([key, value]) => this.set(key, value));
  });
}