如何实现哈希映射

数组非常适合查找特定索引处的元素，因为内存中的所有元素都是连续的，从而可以实现O(1)常数时间或更短时间的查找。但通常情况下，我们不会（或无法）通过索引进行查找。哈希映射和哈希表提供了一种解决方案，使我们能够通过keys其他方式进行查找。

你能Map从头开始实现这个类吗？只需要两个方法——`get_hash()`get和set`get_distance()`。许多编程语言都有内置的哈希或字典原语（例如Javascript Object`s` 和 ` {}char` 表示法），但在这个练习中我们不想使用这些。

本文最初发表于https://algodaily.com，我在该网站上维护一个技术面试课程，并为有抱负的开发者撰写思考性文章。

注意：常规Javascript对象和Map类都是简单的键值哈希表/关联数组，但有一些关键区别：

对象Map可以按插入顺序遍历其元素，而 JavaScript 的Object`<div>` 元素则不保证顺序。此外，Object`<div>` 元素由于其原型而具有默认键，而Map`<div>` 元素则没有默认键。以下是对两者的详细分析。为了便于说明，我们假设两者的功能相同。

您将定义以下两种方法：

1. get(key: string)应该给定一个键，并返回该键对应的值。
2. set(key: string, val: string)应该接受一个键和一个值作为参数，并存储这对参数。

此外，我们还提供了以下哈希函数hashStr。它尽量避免哈希冲突，但并非完美无缺。它接收一个字符串值作为输入，并返回一个整数。

function hashStr(str) {
    let finalHash = 0;
    for (let i = 0; i < str.length; i++) {
        const charCode = str.charCodeAt(i);
        finalHash += charCode;
    }
    return finalHash;
}

console.log(hashStr('testKey'))

我们把这个新类命名为 `class` Hashmap，并像这样使用它：

const m = new Hashmap();
m.set('name', 'Jake');
console.log(m.get('name'));

我们先回顾一下通用哈希表的工作原理，我们的Hashmap data structure实现将以此为基础。正如我们所提到的，许多编程语言中都有一个Hashmap基于传统哈希表的类Hashtable。接下来，我们将逐步介绍我们建议的代码实现。

我们知道哈希表的工作原理是将数据存储在桶中。为了访问这些桶，我们需要一种方法将 a 转换key为桶号。（桶可以用数组和binary search树来建模，但为了简单起见并最大限度地提高速度，我们将使用数组。）

使用键可以让我们无需知道数据在数组中的具体位置。data structure因此，我们需要一个哈希函数（在本例中为 `hash_key`）hashStr来计算所需值的存储位置。本质上，我们通过哈希函数将 `hash_key` 映射index到数组索引。bucketskeyhashStr

hashStr('r')
// 114

// array = [  _  ,  X  ,  _  ,  _ ]
// index     113   114   115   116

如您所见，它hashStr所做的只是接收key传入的值set()，并为我们计算出一个位置。因此，我们需要另一个对象data structure来实际存储这些值，以及将它们放入哪个存储桶中。当然，您已经知道它是一个数组！

填写

哈希表的槽或桶通常存储在_______及其索引中。

解决方案：数组

编写该类的一个好方法是先用存储数组初始化它：

class Hashmap {
  constructor() {
    this._storage = [];
  }
}

我们将使用返回的索引hashStr来决定输入的值应该放在哪里this._storage。

关于哈希冲突：collisions哈希函数对多个键返回相同的索引时就会发生冲突，这超出了本问题的范围。不过，我们可以使用额外的数据结构来处理这类问题。

多项选择题

以下哪项是解决哈希表实现中冲突的方案？

• 对于哈希冲突没有完美的解决方案，哈希函数必须是唯一的。
• 使用分离链式结构，通常使用链表，其中数组的索引由一系列值组成。
• 使用 trie 树存储每个索引处的值
• 将该桶中的所有值连接成一个字符串。

解决方案：使用分离链式结构，通常使用链表，其中数组的索引由一系列值组成。

至此，我们已经有了构建所需的基本要素，接下来让我们实现这个set方法。该方法将：

1. 接受key通过
2. 将其输入哈希函数，然后
3. storage设置我们数据库中该特定索引处的值

还要注意我们存储它的方式：() 中的每个索引this._storage本身this._storage[idx]就是一个数组，从而从根本上解决了碰撞问题。

set(key, val) {
  let idx = this.hashStr(key);

  if (!this._storage[idx]) {
    this._storage[idx] = [];
  }

  this._storage[idx].push([key, val]);
}

set现在看来这个方法很简单，对吧？

我们的方法也遵循同样的概念get。我们所做的也是运行传递给方法的参数key，hashStr但不同之处在于，我们不是设置值，而是访问结果索引并检索值。

  for (let keyVal of this._storage[idx]) {
    if (keyVal[0] === key) {
      return keyVal[1];
    }
  }

需要注意的一点是，有可能传递一个不存在（或尚未存在）的键，因此如果出现这种情况，set我们应该返回该键来处理它。undefined

get(key) {
  let idx = this.hashStr(key);

  if (!this._storage[idx]) {
    return undefined;
  }

  for (let keyVal of this._storage[idx]) {
    if (keyVal[0] === key) {
      return keyVal[1];
    }
  }
}

应该差不多了！我们来试试。

class Hashmap {
  constructor() {
    this._storage = [];
  }

  hashStr(str) {
    let finalHash = 0;
    for (let i = 0; i < str.length; i++) {
      const charCode = str.charCodeAt(i);
      finalHash += charCode;
    }
    return finalHash;
  }

  set(key, val) {
    let idx = this.hashStr(key);

    if (!this._storage[idx]) {
      this._storage[idx] = [];
    }

    this._storage[idx].push([key, val]);
  }

  get(key) {
    let idx = this.hashStr(key);

    if (!this._storage[idx]) {
      return undefined;
    }

    for (let keyVal of this._storage[idx]) {
      if (keyVal[0] === key) {
        return keyVal[1];
      }
    }
  }
}

本文最初发表于https://algodaily.com，我在该网站上维护一个技术面试课程，并为有抱负的开发者撰写思考性文章。