V8团队带你学编程语言のHashMap知多少

Map数据结构在编程时非常有用。我第一次使用Perl时，最让我印象深刻的是使用哈希值是多么容易，正如他们所说的那样。我用它们来做任何事情！Map也是Go中的一个核心功能——它是具有语法支持和泛型的内置对象类型之一。我认为大多数用Python编程的人都有类似的经历。他们称它们为字典，它们无处不在。在JavaScript中，每个对象都是一种哈希映射。当我在V8上工作时，我们不得不不遗余力地隐藏这个决定的性能后果，但我仍然喜欢语言中易于使用的HashMap。

但所有这些语言最初都有无序的HashMap。您可以将所有键值对放在HashMap中，但是当您想要浏览Map的内容时，您可以按照某种奇怪的顺序将它们取回。这不是你把它们放在里面的顺序，而且几乎可以肯定不是你想要的顺序。Go和Perl决定通过使哈希排序更加随机来解决这个问题。JavaScript和Python走了另一条路，并将顺序固定为与插入相同的顺序。（JS 对象中有一个例外 — 数字属性名称按数字排序，而不是按插入顺序排序。我们在V8的错误跟踪器上得到了很多仇恨！

使HashMap有效地插入排序的最佳方法是Python所谓的"紧凑字典"的一些变体，由Raymond Hettinger推广/重新发现。（根据Hettinger的说法，有一些现有技术是用Java实现的，它实际上类似于V8的内部对象实现，由Lars Bak发明，Lars Bak也是Toit的联合创始人之一。在紧凑字典中，键和值入到线性数组中，并且有一个更传统的 开放寻址哈希表 ，该表索引到线性数组中。它看起来像这样。

这也是HashMap在Toit中的样子。实际上，索引表中的哈希编号不是必需的，但它们可以加快查找速度。存储哈希代码的最后几位可以检测索引中的大多数冲突，而不必查看支持数组中的键。在索引中使用哈希代码的另一个优点是，当索引变得太满时，它会加快重新构建索引的速度。

如果用户从此类型的哈希映射中删除某个条目，我们将该键替换为指示此条目已被删除的标记。也许有点病态，我们称这些标记为"墓碑"。当这些墓碑足够多时，HashMap就会被重建，但这没关系。由于摊销常量时间的魔力，这平均不会减慢你的速度。

这一切都非常酷，因为现在有一种有效的方法来制作带有插入排序的HashMap。这些是不讨厌你的HashMap，这就是为什么我们在Dart项目中也使用它们的原因，现在可能最出名的是Flutter背后的引擎。（Dart的一些创始人后来创立了Toit。

您很快发现自己需要的另一个功能是能够在HashMap中使用任意对象作为键。在不支持此功能的语言中（直到最近才使用Perl，Python，Go，JavaScript），您可以使用字符串作为键，为每个键对象生成唯一的字符串。这并不是很优雅，你的程序创建了很多不需要存在的字符串。

更高级的是能够为映射中的键指定相等函数。例如，在 Java 和 Toit 中，您可以为集合中键的类指定自定义等于方法。相比之下，JavaScript 中的映射实现仅使用对象标识。您无法先创建新对象，然后发现映射中是否已存在等效键。同样，不雅的解决方法是让每个字符串生成字符串并将其用作键。

更进一步，有时需要为每个映射指定相等函数，而不是为每个键类型指定相等函数。这在C++以哈希和Pred模板参数的形式提供，unordered_map。（但正如名称unordered_map所示，标准C++集合讨厌你，所以这个高级功能没有什么安慰。目前，我们在 Toit 中不支持每个映射的相等函数，但它即将推出！在Java中，您必须将密钥包装在Map中或使用Trove。

即使你的语言有紧凑的词典，美中不足之处仍然有一只小苍蝇。在某些情况下，你的HashMap仍然会表现得好像他们讨厌你，但以一种新的方式！有些人喜欢使用哈希映射（和具有相同实现的集合）作为重复数据删除工作队列。您可以将"任务"添加到集合中，它将自动忽略重复项，因为它是一个集合。任务队列（也称为 FIFO）需要追加到末尾操作和从开始删除操作。我们已经有追加到末尾的操作，通过查看后备阵列的开头，很容易进行删除优先操作。如果 Toit 语言还没有这个功能，你可以按如下方式添加它：

使用这样的集合或Map一段时间后，问题就出现了。在支持开始时会有很多墓碑，突然之间，从开始删除操作就不那么快了。它需要跳过越来越多的逻辑删除，并且插入然后删除n个项目的运行时变为二次。此问题无法通过更频繁地重建哈希映射来解决，因为如果这样做，则会丢失摊销常量时间操作的属性。

一种即席解决方案是记录每个哈希映射，其中第一个条目位于支持数组中。不过这感觉就像创可贴一样。如果用户希望使用集合作为重复数据删除堆栈（或 LIFO）重复删除最后一个条目，该怎么办？可恶的二次哈希映射问题将会回来。如果他们想反复删除集合中的第二个条目，该怎么办？我在 V8 上学到的一件事是，很难预测你的用户会用你构建的编程语言实现做什么。

我们构建了Toit，以便在小型设备上工作。我们真的想在每个HashMap上多花一个单词来记录前导墓碑的数量吗？我们想出的解决方案是带有距离标记的墓碑。每个墓碑还记录了到下一个真实条目的距离，无论是在左侧还是右侧。我们在扫描支持时会懒惰地更新它，因此在其他操作上不会花费任何时间，但它允许我们跳过长长的逻辑删除，无论它们出现在何处。

对于没有删除或删除是随机分布的常见情况，没有任何变化，但对于有问题的情况，我们保留了摊销常量时间插入和删除的理想属性。

我编写了一个小程序来测试语言实现在将集合用作FIFO时是否具有二次减速。我只测试具有按插入顺序排列的语言。对于JavaScript，我使用new（ish）Set，而不是滥用普通对象作为哈希映射。在Java中，我使用了LinkedHashMap，它具有完全不同的内部表示形式。我怀疑LinkedHashMap在内存使用方面相当挥霍无度（我很快就会写关于这个问题的博客），但它是我测试过的最快的插入顺序集，特别是当自适应JIT启动时。

所以这里，为了你的享受，是各种语言的图表。目前，所有基于紧凑字典的实现（Toit 除外）都存在此问题。希望这篇博客文章能激励实施者修复它。