JavaScript 如何向数组指定索引的元素中插入新元素以处理hash map碰撞

核心实现逻辑 #

• 哈希表底层使用数组存储数据，每个索引位置默认初始化为空数组，用于存放哈希计算后索引相同的所有元素
• 计算待插入元素的哈希值，取模后得到数组对应的索引位置
• 若需要支持同key覆盖，先遍历该索引对应的子数组检查是否存在相同key，存在则直接覆盖原值；不存在则将新元素插入子数组即可

完整代码实现 #

class HashMap {
  constructor(size = 16) {
    // 初始化底层桶数组，每个位置默认是空数组
    this.buckets = new Array(size).fill(null).map(() => []);
    this.size = size;
  }

  // 哈希函数，可根据需求替换为更均匀的工业级实现
  #hash(key) {
    let hash = 0;
    for (let i = 0; i < String(key).length; i++) {
      hash = (hash + String(key).charCodeAt(i) * i) % this.size;
    }
    return hash;
  }

  // 插入元素方法
  set(key, value) {
    const index = this.#hash(key);
    // 检查是否存在相同key，有则覆盖
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    // 无相同key则插入新元素
    this.buckets[index].push([key, value]);
  }

  // 取值方法，用于验证
  get(key) {
    const index = this.#hash(key);
    for (const item of this.buckets[index]) {
      if (item[0] === key) return item[1];
    }
    return undefined;
  }
}

使用示例 #

const map = new HashMap();
map.set('name', '张三');
map.set('age', 25);
// 若两个key计算出的哈希索引相同会触发碰撞，自动存入同一个索引的子数组
map.set('a1', '碰撞测试1');
map.set('2b', '碰撞测试2');

console.log(map.get('a1')); // 输出：碰撞测试1
console.log(map.get('2b')); // 输出：碰撞测试2

注意事项 #

• 对插入顺序有要求时，可以选择插入到子数组的头部或尾部，上述示例默认插入尾部，仅插入逻辑的时间复杂度为O(1)（不含同key查重环节）
• 哈希函数的均匀性直接影响碰撞概率，生产环境建议替换为成熟的哈希函数实现
• 当哈希表负载因子（存储元素总数/底层数组长度）超过0.75时，建议对底层数组进行扩容重哈希，降低碰撞概率

内容的提问来源于stack exchange，提问作者Pablo Carrero Garcia