如何在JavaScript中实现HashMap？详细实现指南

在上一篇文章中，我们介绍了在Java中实现HashMap，这里我们开始介绍如何使用JavaScript实现HashMap。数组在根据特定索引查找元素方面非常出色，因为内存中的所有元素都是连续的，允许O(1)或常量时间查找。但是通常我们不会，或者不能，通过索引来执行查找。JavaScript HashMap和哈希表是解决这个问题的一种方法，使我们能够通过键来快速查找。

如何在JavaScript中实现HashMap？只需要两个方法——get和set。许多编程语言都有内置的散列或字典原语(如Javascript对象和{}表示法)，但我们不想在本练习中使用它。

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

Map对象可以按插入顺序遍历其元素，而JavaScript对象不保证顺序。此外，由于对象的原型有默认键，而Map没有默认键。以下是对这两者的详细分析：ES6 map介绍和用法，JavaScript的map，JavaScript对象。为了使用JavaScript实现HashMap，我们假设两者具有相同的功能。

对于你将定义的两个方法:

应该传给get(key: string)一个键，并返回该键的值。
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'))

让我们把这个新类称为Hashmap类，并像这样使用它:

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

让我们从回顾通用哈希表的工作方式开始，其理论是我们的Hashmap数据结构将基于什么。正如我们已经注意到的，在许多编程语言中，有一个Hashmap类基于遗留的哈希表。让我们逐步介绍这段代码的建议实现。

我们知道哈希表的工作原理是将数据存储在桶中。要访问这些桶，我们需要一种将密钥转换为桶号的方法。(存储桶可以使用数组和二叉搜索树建模（二叉树实现，JavaScript二叉树实现），但为了保持简单和最大化速度，我们将继续使用数组。)

使用键使我们不必知道数据在数组中的位置。因此，我们的数据结构需要一个散列函数(在本例中为hashStr提供)来计算存储所需值的桶的索引。我们实际上是通过hashStr哈希函数将键映射到数组下标。

hashStr('r')
// 114

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

如你所见，hashStr所做的就是获取JavaScript HashMap set()中提供的键，并为我们计算位置。因此，我们需要另一个数据结构用于实际存储和存放值的桶。当然，你已经知道它是一个数组！下面我们来看一下JavaScript实现HashMap中需要解决的两个问题：

1、哈希表的槽或桶通常存储在数组及其索引中。

编写这个类的一个好的开始是只使用存储数组来初始化它:

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

碰撞上的单词: 碰撞是指哈希函数为多个键返回相同的索引，并且超出了这个问题的范围。但是，有一些方法可以使用额外的数据结构来处理这些问题。

2、多项选择题：

下列哪一个是在哈希表实现中的冲突的解决方案?

对于冲突没有好的解决方案，哈希函数必须是唯一的
使用单独的链接，通常使用链表，数组的索引由一串值组成
使用try在每个索引处存储值
将所有的值连接成一个字符串

解决方案:使用单独的链接，通常使用链表，其中数组的索引由一串值组成

现在让我们继续使用JavaScript实现HashMap，我们已经有了构建块，所以让我们继续实现set方法。方法:

获取key
通过哈希函数运行它，然后
在这个特定的索引处设置我们存储中的值

注意我们存储它的方式:这里的每个索引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方法现在看起来很简单，对吧?

这与我们的JavaScript HashMap get方法是相同的概念。我们在这里所做的是通过hashStr方法运行传递的键，但不是设置，我们将转到生成的索引并检索值。

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

需要注意的一点是，传递一个不存在(或没有设置)的键是可能的，所以如果是这样的话，我们应该通过返回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];
    }
  }
}

那应该就是这样吧！我们来试一下，下面就是JavaScript实现HashMap的完整代码了：

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];
      }
    }
  }
}

如何在JavaScript中实现HashMap？以上就是使用JavaScript实现HashMap的完整指南了。首先我们介绍了JavaScript HashMap的基本哈希表实现原理，以及哈希表的冲突解决，然后是JavaScript实现HashMap的完整实现过程和实现代码。希望以上内容可以帮到你，如有问题，请在下方评论。

猜你喜欢