该标准的ECMAScript 2015年，被称为ES6，有许多新的JavaScript的集合，例如
Map，Set，WeakMap和WeakSet。它们似乎是标准JavaScript功能的重要补充。它们被广泛用于Node.js核心的各种库，应用程序中。今天，我们将讨论该集合Map，尝试弄清其在V8中的实现细节，并基于所获得的知识得出一些实际的结论。
ES6标准没有明确说明应采用哪种方法来实现数据结构支持
Map。它仅给出了实现它的可能方法的一些提示。它还包含有关预期的信息Map性能指标：
必须使用哈希表或其他平均可提供对集合元素进行次线性访问的机制来实现Map对象。 Map规范中使用的数据结构仅用于描述Map对象的可观察语义。它们并不被认为是实现这些对象的真实模型。
如您所见，该规范为创建JS引擎的人员提供了很多自由。但是同时，对于用于实现的特定方法
Map，其性能和内存消耗特性，没有特定的指南。如果在应用程序的关键部分使用了数据结构Map如果您将大量信息写入此类数据结构，那么扎实的实施知识Map无疑将为您带来极大的好处。
我有Java开发经验，并且习惯于Java集合，您可以在其中选择不同的接口实现，
Map甚至在相应类支持的情况下微调所选实现。此外，在Java中，您始终可以阅读标准库中任何类的开放源代码并熟悉其实现（当然，它可能会在新版本中进行更改，但只会朝着提高效率的方向发展）。这就是为什么我无法抗拒学习对象Map在V8中的工作方式的原因。
在开始之前，我想指出的是，下面将要讨论的是V8 8.4引擎，该引擎内置在Node.js的最新开发版本中（更确切地说，我们正在谈论commit 238104c）。您无需期望超出规范。
Map实现基础的算法
首先，我要说的是数据结构是
Map基于哈希表的。下面我假设您知道哈希表如何工作。如果您不熟悉哈希表，则应首先阅读它们（例如，在此处），然后再继续阅读本文。
如果您对对象具有丰富的经验
Map，那么您可能已经注意到了一个矛盾。即，在哈希表上进行迭代时，不能保证它们以某种恒定顺序返回。 ES6规范指出，要实现一个对象，Map遍历该对象时，必须按照将元素添加到对象中的顺序返回这些元素。结果，“经典”算法得以实现Map不适合。但是有一种感觉，即使有一些更改，它仍然可以使用。
V8使用Tyler Close提出的所谓的“确定性哈希表”。以下基于TypeScript的伪代码演示了用于实现此类哈希表的基本数据结构：
interface Entry {
key: any;
value: any;
chain: number;
}
interface CloseTable {
hashTable: number[];
dataTable: Entry[];
nextSlot: number;
size: number;
}
这里的接口
CloseTable代表一个哈希表。它包含一个数组，hashTable其大小等于哈希容器的数量。具有索引的array元素N对应于第-N个哈希容器，并存储其位于array中的head元素的索引dataTable。并且此数组按插入表的顺序包含表的记录。条目由界面显示Entry。最后，每个条目都具有一个属性chain，该属性指向哈希容器条目链中的下一个条目（或更准确地说，是在单链列表中）。
每次将新记录插入表中时，该记录都会存储在
dataTable带有索引的数组元素中nextSlot...此过程还需要更新相应的哈希容器中的数据，这会使插入的记录成为单链列表的新的最后一个元素。
从表中删除记录时，会将其从中删除
dataTable（例如，通过写入其属性key和value值undefined）。然后，其前面的条目和其后面的条目直接彼此链接。您可能已经注意到，这意味着所有已删除的条目继续占据中的空间dataTable。
现在是我们难题的最后一部分。当一个表中充满了记录（当前记录和已删除记录）时，必须通过增加其大小来重新整理（重建）它。表格的大小可以向下更改。
使用这种方法，遍历数据结构
Map等效于遍历array dataTable。这样可以确保保留将记录插入表中的顺序，并确保符合标准。考虑到这一点，我希望大多数（如果不是全部）JS引擎都将确定性哈希表用作基础实现机制之一Map。
算法的实践研究
让我们看一些示例，以帮助我们在实践中探索该算法。假设我们有
CloseTable2个散列容器（hastTable.length），其总容量为4个元素（dataTable.length）。该表包含以下内容：
// , -,
// , , function hashCode(n) { return n; }
table.set(0, 'a'); // => - 0 (0 % 2)
table.set(1, 'b'); // => - 1 (1 % 2)
table.set(2, 'c'); // => - 0 (2 % 2)
在此示例中获得的表的内部表示可能如下所示：
const tableInternals = {
hashTable: [0, 1],
dataTable: [
{
key: 0,
value: 'a',
chain: 2 // <2, 'c'>
},
{
key: 1,
value: 'b',
chain: -1 // -1
},
{
key: 2,
value: 'c',
chain: -1
},
//
],
nextSlot: 3, //
size: 3
}
如果使用方法删除记录
table.delete(0)，则哈希表如下所示：
const tableInternals = {
hashTable: [0, 1],
dataTable: [
{
key: undefined, //
value: undefined,
chain: 2
},
{
key: 1,
value: 'b',
chain: -1
},
{
key: 2,
value: 'c',
chain: -1
},
//
],
nextSlot: 3,
size: 2 //
}
如果我们将更多记录添加到表中，则需要对其进行哈希处理。我们将在下面详细讨论此过程。
实现数据结构时可以应用相同的方法
Set。唯一的区别是这些数据结构不需要属性value。
现在我们已经弄清了
MapV8中的对象背后是什么，我们已经准备好继续。
实施细节
MapV8中
的数据结构实现是用C ++编写的，此后，将允许JS代码访问相应的机制。与之相关的大多数代码Map在OrderedHashTable和类中OrderedHashMap。我们已经知道这些类如何工作。如果您想自己看看他们的代码，那么可以在这里，这里和这里找到。
由于我们对
MapV8中的实现的实际细节特别感兴趣，因此我们首先需要了解如何设置表的容量。
工作台容量
在V8中，哈希表（数据结构
Map）的容量始终是2的幂。如果我们谈论哈希容器的利用率，那么它总是由数字2表示。也就是说，表的最大容量2 * number_of_buckets是哈希容器数量的2倍。创建空对象时，Map其内部哈希表中有2个哈希容器。结果，该对象的容量等于4个记录。
对对象的最大容量有限制
Map。在64位系统上，这大约是1670万条记录。此限制是由于Map在堆中表示数据结构的特性所致。我们稍后再讨论。
最后，增加或减少表的因素也总是用某个数字乘以2来表示。这意味着在将4个记录添加到所描述的表之后，下一个插入操作将导致需要重新清洗表，在此期间表的大小将增加2次。因此，随着桌子尺寸的减小，它可以减小2倍。
为了确保我在源代码中看到工程完全按照我的理解是，我修改了内置的Node.js的V8引擎代码，使得它，因此
Map新的属性buckets包含有关哈希容器数量的信息。您可以在此处找到此修改的结果... 在Node.js的特殊程序集中，可以运行以下脚本：
const map = new Map();
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
if (prevBuckets !== map.buckets) {
console.log(`size: ${i}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
prevBuckets = map.buckets;
}
map.set({}, {});
}
该脚本仅将
Map100条记录插入数据结构。这是启动后在控制台中显示的内容：
$ ./node /home/puzpuzpuz/map-grow-capacity.js
size: 0, buckets: 2, capacity: 4
size: 5, buckets: 4, capacity: 8
size: 9, buckets: 8, capacity: 16
size: 17, buckets: 16, capacity: 32
size: 33, buckets: 32, capacity: 64
size: 65, buckets: 64, capacity: 128
正如您所看到的，当表被填充时，每次改变大小，它都会增加2倍。现在，让我们尝试通过从表中删除元素来缩小表的大小：
const map = new Map();
for (let i = 0; i < 100; i++) {
map.set(i, i);
}
console.log(`initial size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
map.delete(i);
if (prevBuckets !== map.buckets) {
console.log(`size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
prevBuckets = map.buckets;
}
}
这是此脚本将输出的内容：
$ ./node /home/puzpuzpuz/map-shrink-capacity.js
initial size: 100, buckets: 64, capacity: 128
size: 99, buckets: 64, capacity: 128
size: 31, buckets: 32, capacity: 64
size: 15, buckets: 16, capacity: 32
size: 7, buckets: 8, capacity: 16
size: 3, buckets: 4, capacity: 8
size: 1, buckets: 2, capacity: 4
在这里，您可以再次看到，表的
number_of_buckets / 2元素每次减少时，表的大小都会减小。
哈希函数
到目前为止，我们还没有涉及V8如何为存储在object中的键计算哈希码的问题
Map。这是一个重要的问题。
对于可以归类为数值的值，使用了一些冲突概率较低的众所周知的哈希函数。
对于字符串值，将根据自己的值计算哈希码。之后，此代码将缓存在内部标头中。
最后，对于对象，基于随机数计算哈希，然后将发生的情况缓存在内部标头中。
使用Map对象进行操作的时间复杂度
对数据结构执行的大多数操作
Map（例如set或delete）都需要搜索这些数据结构。与“经典”哈希表一样，本例中搜索的时间复杂度为O(1)。
想象一个最坏的情况，当桌子满了，也就是说，它从座位上占据
N了N。在这种情况下，所有记录都属于单个哈希容器，并且所需记录位于记录链的最末端。在这种情况下，您将需要采取步骤来找到该条目N。
另一方面，在最佳方案中，当表已满并且每个哈希容器中只有2条记录时，查找一条记录仅需要2个步骤。
哈希表中的某些操作非常快，但哈希操作却并非如此。哈希运算的时间复杂度为
O(N)。它要求在堆上分配新的哈希表。此外，根据需要执行重新哈希处理，作为从表中插入或删除元素的操作的一部分。因此，例如，该呼叫map.set()可能比预期的要“昂贵得多”。幸运的是，很少执行哈希操作。
内存消耗
当然，基础哈希表
Map必须以某种方式存储在堆中。它存储在所谓的“辅助存储”中。在这里，另一个有趣的事实在等待着我们。整个表格（以及放置在中的所有表格Map）都存储在固定长度的单个数组中。下图显示了此数组的结构。
用于在内存中存储Map数据结构
的数组数组的各个部分具有以下目的：
- 标头：包含常规信息，例如哈希容器的数量或从中删除的项目数
Map。 - 哈希容器详细信息：这是我们在其中存储与
hashTable示例中的数组相对应的容器数据的地方。 - 哈希表条目：这是存储与数组对应的数据的位置
dataTable。即，它包含有关哈希表条目的信息。每个记录占用阵列中的三个单元。一个存储键，第二个存储值，第三个存储“指针”到链中的下一个记录。
如果我们讨论数组的大小，则可以将其粗略估计为
N * 3,5。这N是表格的容量。为了了解这在内存消耗方面的含义，让我们想象一下，我们有一个64位系统，并且V8的指针压缩功能被禁用。在这种情况下，需要8个字节来存储数组的每个元素。结果Map，需要29 MB的堆内存来存储大约100万条记录的数据结构。
结果
在本文中，我们讨论了很多与
MapJavaScript中的数据结构有关的内容。让我们总结一下：
- V8
Map使用确定性哈希表来实现。此数据结构很可能也在其他JS引擎中实现。 - 支持这项工作的机制
Map是用C ++实现的，之后将它们表示为可从JavaScript访问的API。 - 如果我们谈论使用对象执行操作的时间复杂性
Map，那么它们以及使用“经典”哈希表时都会具有复杂性O(1)。在这种情况下，哈希运算的时间复杂度为O(N)。 - 64-
Map1 29 , . - , ,
Set.
Map JavaScript-?
