js实现hashmap

实现基础结构

使用对象或Map类作为基础存储结构。对象方式适合简单键值对，Map类支持更复杂的键类型（如对象、函数）。

// 对象实现
const hashMap = {};

// Map类实现
const map = new Map();

处理哈希冲突

采用链表法解决冲突，每个哈希桶存储一个链表。当多个键映射到同一索引时，将新元素添加到链表末尾。

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

  _hash(key) {
    let hashCode = 0;
    for (let i = 0; i < key.length; i++) {
      hashCode = (hashCode << 5) - hashCode + key.charCodeAt(i);
    }
    return hashCode % this.buckets.length;
  }
}

实现核心方法

包含set、get、has、delete等基本操作，处理动态扩容逻辑。

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

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

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

动态扩容机制

当元素数量超过容量阈值时自动扩容，通常扩大为当前容量的两倍。

_resize() {
  const occupied = this.buckets.filter(b => b.length > 0).length;
  if (occupied / this.buckets.length > this.loadFactor) {
    const oldBuckets = this.buckets;
    this.buckets = new Array(oldBuckets.length * 2).fill(null).map(() => []);
    oldBuckets.forEach(bucket => {
      bucket.forEach(item => {
        const newIndex = this._hash(item.key);
        this.buckets[newIndex].push(item);
      });
    });
  }
}

完整实现示例

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

  _hash(key) {
    let hash = 0;
    const stringKey = String(key);
    for (let i = 0; i < stringKey.length; i++) {
      hash = (hash << 5) - hash + stringKey.charCodeAt(i);
    }
    return Math.abs(hash % this.buckets.length);
  }

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

    if (existing) {
      existing.value = value;
    } else {
      bucket.push({ key, value });
      this.size++;
      if (this.size / this.buckets.length > this.loadFactor) {
        this._resize();
      }
    }
    return this;
  }

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

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

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

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

  _resize() {
    const newCapacity = this.buckets.length * 2;
    const newBuckets = new Array(newCapacity).fill(null).map(() => []);

    this.buckets.forEach(bucket => {
      bucket.forEach(item => {
        const newIndex = this._hash(item.key);
        newBuckets[newIndex].push(item);
      });
    });

    this.buckets = newBuckets;
  }
}