当前位置：首页 > JavaScript

js hasmap实现

2026-03-14 05:30:00JavaScript

实现 HashMap 的基本结构

HashMap 的核心是键值对存储，通过哈希函数将键映射到数组索引。基本结构包含一个数组（桶）和哈希函数。

class HashMap {
  constructor(initialCapacity = 16, loadFactor = 0.75) {
    this.buckets = new Array(initialCapacity).fill(null).map(() => []);
    this.size = 0;
    this.loadFactor = loadFactor;
    this.capacity = initialCapacity;
  }
}

哈希函数设计

哈希函数将键转换为数组索引。常用方法是使用字符编码或多项式滚动哈希。

js hasmap实现

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

处理冲突

冲突通过链地址法（链表或数组）解决。每个桶存储一个键值对列表。

js hasmap实现

_set(key, value) {
  const index = this._hash(key);
  const bucket = this.buckets[index];
  for (let i = 0; i < bucket.length; i++) {
    if (bucket[i].key === key) {
      bucket[i].value = value; // 更新现有键
      return;
    }
  }
  bucket.push({ key, value }); // 新增键值对
  this.size++;
  if (this.size / this.capacity > this.loadFactor) {
    this._resize();
  }
}

动态扩容

当元素数量超过负载因子时，扩容数组并重新哈希所有元素。

_resize() {
  const oldBuckets = this.buckets;
  this.capacity *= 2;
  this.buckets = new Array(this.capacity).fill(null).map(() => []);
  this.size = 0;
  for (const bucket of oldBuckets) {
    for (const entry of bucket) {
      this._set(entry.key, entry.value);
    }
  }
}

完整方法实现

包含 get、delete 和 has 方法。

get(key) {
  const index = this._hash(key);
  const bucket = this.buckets[index];
  for (const entry of bucket) {
    if (entry.key === key) {
      return entry.value;
    }
  }
  return undefined;
}

delete(key) {
  const index = this._hash(key);
  const bucket = this.buckets[index];
  for (let i = 0; i < bucket.length; i++) {
    if (bucket[i].key === key) {
      bucket.splice(i, 1);
      this.size--;
      return true;
    }
  }
  return false;
}

has(key) {
  return this.get(key) !== undefined;
}