使用 Javascript 的哈希映射

介绍

• 哈希映射（Hash Map），也称为哈希表（Hash Table），是一种实现关联数组抽象数据类型的数据结构，是一种可以将键映射到值的结构。

• 它使用哈希函数来计算存储桶或槽数组的索引，从中可以找到所需的值。

• 哈希映射的主要优点是它的效率。插入新的键值对、删除键值对以及查找给定键的值等操作都非常快，通常平均需要恒定的时间。

在 JavaScript 中实现简单的哈希映射

let hashMap = {};
hashMap['key1'] = 'value1';
hashMap['key2'] = 'value2';
console.log(hashMap['key1']); // Outputs: value1

处理碰撞

• 处理冲突是实现哈希映射的一个重要方面。当两个不同的密钥产生相同的哈希值时，就会发生冲突。处理碰撞的策略有多种，但最常见的两种是单独的链接和线性探测。

单独链接：在单独链接中，哈希表数组中的每个槽都包含一个链接列表（或可以容纳多个项目的其他数据结构）。当发生冲突时，新的键值对会添加到链表相应索引的末尾。

这是在 JavaScript 中使用单独链接的哈希映射的简单实现：

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null).map(() => []);
  }

  put(key, value) {
    const index = this.hash(key);
    const chain = this.table[index];
    const existingPair = chain.find(([existingKey]) => existingKey === key);

    if (existingPair) {
      existingPair[1] = value;
    } else {
      chain.push([key, value]);
    }
  }

  get(key) {
    const index = this.hash(key);
    const chain = this.table[index];
    const pair = chain.find(([existingKey]) => existingKey === key);

    if (pair) {
      return pair[1];
    }

    return null;
  }

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

线性探测：在线性探测中，当发生冲突时，哈希映射会检查数组中的下一个槽（如果也已满，则继续到下一个槽，依此类推），直到找到一个空槽，可以存储新的键值对。

这是在 JavaScript 中使用线性探测的哈希映射的简单实现：

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null);
  }

  put(key, value) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      index = (index + 1) % this.table.length;
    }
    this.table[index] = [key, value];
  }

  get(key) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      if (this.table[index][0] === key) {
        return this.table[index][1];
      }
      index = (index + 1) % this.table.length;
    }
    return null;
  }

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

在这两个示例中，哈希方法都是一个简单的哈希函数，它将键转换为用作数组中索引的整数。在现实场景中，您可能会使用更复杂的哈希函数来减少冲突的可能性。

以上是使用 Javascript 的哈希映射的详细内容。更多信息请关注PHP中文网其他相关文章！