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

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

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

JavaScript实现HashMap

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

Map对象可以按插入顺序遍历其元素,而JavaScript对象不保证顺序。此外,由于对象的原型有默认键,而Map没有默认键。以下是对这两者的详细分析:ES6 map介绍和用法JavaScript的mapJavaScript对象。为了使用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实现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的完整实现过程和实现代码。希望以上内容可以帮到你,如有问题,请在下方评论。

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?