亲宝软件园·资讯

展开

JavaScript 使用 Map

前端黑板报​​​​​​​ 人气:0

Map 用作 Hash Map

ES6 给我们带来了 Map,它更适合当做 hash map 的用例。

首先,它并不像 Object 那样只允许 key 为 string 和 symobol,Map 的 key 支持任何数据类型。

可是如果你使用 Map 为对象存储元数据,应该使用 WeakMap 取而代之以此避免内存泄漏。

更重要的是,Map 为用户自定义和内置对象属性提供了清晰的界限,使用一个额外的方法 Map.prototype.get 获取条目。

Map 同样也提供了更人性化的方法,Map 默认就可迭代,意味着你可以轻松的与 for...of 一起使用,同样使用嵌套的解构获取第一个条目。

const [[firstKey, firstValue]] = map

与 Object 对比,Map 为各种常见任务提供了具体的方法:

性能

在 JavaScript 社区中似乎有一种共同的认知:Map 比 Object 快,在多数情况下,有些人在从 Object 切换到 Map 时看到了性能的提升。

从我在磨人的 LeetCode 中刷题的经验中似乎更加确认了这个观点:LeetCode 使用了大量的数据来对你的解决方案做测试用例,若你的答案花费了太长时间则会超时。像这种问题一般在你使用 Object 时出现几次,而 Map 则没有。

可是,我相信只简单的说 Map 比 Object 快很笼统,肯定有一些细微的差别需要我去发现。因此,我创建了一个小应用来运行一些基准测试。

基准测试的实现细节

这个应用有一个表格用来展示分别对 Object 和 Map 作用插入、迭代和删除的速度。

插入和迭代的性能是以每秒来测量的,我写了一个工具方法 measureFor 用来重复执行目标函数,直到设定的最小阈值(就是传入的 duration 值)。它返回的是每秒函数执行的平均次数。

function measureFor(f, duration) {
  let iterations = 0;
  const now = performance.now();
  let elapsed = 0;
  while (elapsed < duration) {
    f();
    elapsed = performance.now() - now;
    iterations++;
  }

  return ((iterations / elapsed) * 1000).toFixed(4);
}

对于删除,我打算简单的对比一下从长度相同的 Object 、 Map 分别使用 delete 和 Map.protoype.delete 移除所有属性所花费时间的对比。我知道有 Map.protype.clear 但据我所知它非常的快,这有悖于设置基础测试的目的。

在这三种操作中,因为每天的工作中经常使用到插入操作,所以我更关心它。对于迭代的性能,因为有很多方法用于对象的迭代,所以很难包含所有的基准测试。我在这里只测试了 for ... in 循环。

我这里使用了三种类型的 key:

所有的 key 都是随机生成的,所以不会触发 V8 内部实现的缓存机制。在把属性添加到对象上之前,我还在显性的把整数和数值类型的 key 通过 toString 转换为字符串以此避免隐式开销。

最后,在基准测试开始之前,还有一个 100ms 的热身阶段,就是重复创建新的 object 和 map 并立即丢弃掉所耗费的时间。

代码放到了 CodeSandbox 如果你想试玩一下。

从 100 个属性/条目大小的 Object 和 Map 开始,一直到5000000,每种类型的操作都执行了 10000ms 来对比它们之间的表现,

如下:

为何把条目数达到 5000000时才停止? 这是 JavaScript 中能得到的最大对象,根据 StackOverflow 上一名活跃的 V8 工程师 @jmrk 所说:"如果 key 为字符串,当一个普通的对象元素达到 8.3M 时会各种对它的操作会变得非常慢(这是有技术原因的:某个位域有23位宽,当超过时采取非常缓慢的回退路径。)"

字符串类型的键

通常来说,当 key 为字符串(非数值型),在各种操作中 Map 的表现胜过 Object

但是当条目数并没有特别大的时候(100000 以下的时候),在插入操作的速度上 Map 基本是 Object 的两倍,但当大小超过 100000 时,性能差距会开始缩小。

我制作了一个图表来说明我的发现:

上面的图表演示了插入速率随着条目数(x-axis)的增加是如何下降的(y-axis)。可是,因为 x-axis 扩展的越来越大(从 100 到 1000000),很难区分出两条线之间的间隔差距。

然后我用对数比例来处理数据,做出了下面的图表:

你会清楚的分不出两条线渐渐地重叠。

我又用另一个图表来展示当插入操纵时 Map 比 Object 快多少。你可以看到期初 Map 比 Object 快 2倍,随着时间的推移性能差距开始缩小。最终,当大小达到 5000000 时,Map 只快了 30%。

我们的 object 和 map 的条目永远不可能多余 1百万。成百上千的条目,Map 至少比 Object 快 2 倍。因此,我们是否应该开始使用 Map 来重构我们的代码?

当然不是,至少不能期望我们的程序变得比之前快 2倍。记住我们还没有探索其它类型的 key,接下来让我们一起看看整数类型的 key。

整数类型的键

我特别想运行对象上键为整数类型的原因是 V8 内部为整数索引的属性做了优化以及把它们存储在一个分开的数组中,然后可以线性和连续的获取。可是我没有找到任何资料来证明 V8 对 Map 做了同样的优化。

我们先在 [0,1000] 之间尝试整数类型的 key。

就像我预期的一样,这次 Object 比 Map 做得好,在插入方面快 65%以及循环方面快 16%。

让我们把范围调整到最大 1200。

现在看起来 Map 在插入方面快一些以及循环方便快 5 倍。

现在我们仅仅增加了键的范围,而不是 Object 和 Map 的实际大小。让我们来增加它们的大小看看如何影响性能。

当大小为 1000 时,插入方面 Object 比 Map 快 70% 以及循环方面快 2 倍。

我尝试了很多种 Object / Map 大小与整数键范围的组合但没有得到一个清晰的模式。但我看到的一般趋势是,随着大小的增长,以一些相对较小的整数为键,对象在插入方面的性能比 Map 更强,在删除方面总是大致相同,迭代速度要慢 4 或 5 倍。对象在插入时开始变慢的最大整数键的阈值会随着对象的大小而增长。例如,当对象只有 100 个条目时,阈值是 1200 ;当它有 10000 个条目时,阈值似乎是 24000 左右。

数值类型的键

最后,我们一起看一看最后一种类型的键--数值型。

从技术上来说,前面的整数类型的键也是数值型,不过这里的数值型特指通过 Math.random().toString() 生成的数值字符串。

结果有点类似字符串类型的键:Map 开始时比 Object 快得多(插入和删除快2倍,迭代快4-5倍),但随着我们规模的增加,这个差距也越来越小。

嵌套的 Object / Map 呢? 你可能已经发现了我只讲了深度只有一层的 Object 和 Map。我确实增加了一些嵌套深度但是我发现只要总条目数相同性能特性大体一致,不管嵌套了多少层。

例如,我们有一个宽度为 100 和深度为 3 总数为 100 万的条目,结果与宽度为 1000000 深度为 1 的性能几乎相同。

内存使用

基准测试的另一个重要因素为内存利用。

由于我无法控制浏览器环境中的垃圾收集器,我决定在Node中运行基准测试。

我创建了一个小脚本来测量在每个测试中通过手动触发完全垃圾回收时各自的内存使用情况。

与 node --expose-gc 一起运行将会得到如下结果:

{
  object: {
    'string-key': {
      '10000': 3.390625,
      '50000': 19.765625,
      '100000': 16.265625,
      '500000': 71.265625,
      '1000000': 142.015625
    },
    'numeric-key': {
      '10000': 1.65625,
      '50000': 8.265625,
      '100000': 16.765625,
      '500000': 72.265625,
      '1000000': 143.515625
    },
    'integer-key': {
      '10000': 0.25,
      '50000': 2.828125,
      '100000': 4.90625,
      '500000': 25.734375,
      '1000000': 59.203125
    }
  },
  map: {
    'string-key': {
      '10000': 1.703125,
      '50000': 6.765625,
      '100000': 14.015625,
      '500000': 61.765625,
      '1000000': 122.015625
    },
    'numeric-key': {
      '10000': 0.703125,
      '50000': 3.765625,
      '100000': 7.265625,
      '500000': 33.265625,
      '1000000': 67.015625
    },
    'integer-key': {
      '10000': 0.484375,
      '50000': 1.890625,
      '100000': 3.765625,
      '500000': 22.515625,
      '1000000': 43.515625
    }
  }
}

很明显,Map 比 Object 消耗的内存少20%到50%不等,结果并不意外因为 Map 不存储属性的描述类似 Object 上的 writable 、enumerable 、configurable

总结

那么,我们从其中能得到什么?

如果你知道 V8 优化 Map 的细节,或者只是想指出我的基准测试中的缺陷,请与我联系。我很乐意根据你的信息来更新这个帖子。

浏览器兼容性笔记

Map 是 ES6 引入的特性,目前为止我们不需要担心其兼容性除非你的客户使用的旧浏览器。旧指比 IE11 版本低,即使 IE11 支持 Map 但它已经  了。默认情况下,我们不需要费尽心思的添加转换器和垫片来支持 ES5 ,因为那样会增加你的打包体积,同样与现代浏览器比更慢。最重要的是,那样会对 99.999% 使用现代浏览器的用户带来负担。

另外,我们不必放弃对传统浏览器的支持--通过 nomodule 提供回退包来服务传统代码,这样我们就可以避免降低使用现代浏览器的访问者的体验。如果你需要更多的说服力,请参考《过渡到现代JavaScript》。

JavaScript语言在不断发展,平台在优化现代JavaScript方面也不断完善。我们不应该以浏览器兼容性为借口,忽视所有已经取得的改进。

加载全部内容

相关教程
猜你喜欢
用户评论