如何在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,_,_ ] // index113114115116

如你所见，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的基本哈希表实现原理，以及哈希表的冲突解决，然后是JavaScript实现HashMap的完整实现过程和实现代码。希望以上内容可以帮到你，如有问题，请在下方评论。