学习一下V8的Map对象，以下基本为对参考链接的文章的翻译转载。

引入

ECMAScript 2015，也被成为ES6，引入了很多内置类型，例如Map、Set、WeakMap、WeakSet。他们是对标准JS库的扩展并在其他库，应用以及Node.js Core中广泛使用。今天我们关注于Map类型并且尝试去理解V8中的该类型实现细节，同时做一些总结。
规范并没有规定用于实现Map类型的精确算法，而是为可能的实现以及预期的性能特征提供了一些建议：

Map object must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection. The data structures used in this Map objects specification is only intended to describe the required observable semantics of Map objects. It is not intended to be a viable implementation model.

可以看到，该规范为实现保留了很大的空间。在Java中的Map类型存在多种实现接口，甚至可以微调该类型。
声明：该文章针对V8版本对8.4，以及Node.js（commit 238104c）

底层算法概述

首先，V8的Maps是建立在hash tables基础上实现的。以下假设你已经理解了hash tables是如何工作的。如果你不熟悉该概念，那么可以参考wiki学习。
如果你对于Maps类型有足够的经验，那么你会发现一个矛盾。Hash tables不提供顺序保证，但是ES6规范要求提供插入顺序保证。因此经典的算法并不适合Maps，但是通过微调仍然可以实现。
V8使用“deterministic hash tables algorithm”来实现Maps。以下TypeScript伪代码展示了该算法的主要数据结构

1
2
3
4
5
6
7
8
9
10
11
12
interface Entry {
	key: any;
	value: any;
	chain: number;
}

interface CloseTable {
	hashTable: number[];
	dataTable: Entry[];
	nextSlot: number;
	size: number;
}

这里CloseTable接口表示hash table。其包含hashTable数组，其大小与buckets大小相同。数组第N个元素表示第N个bucket，并且在dataTable数组中维护了bucket头元素的index值。dataTable数组包含了以插入顺序排布的Entry元素。最终每个Entry有chain属性，其指向了在bucket链中的下一个entry。
每次一个新的entry插入到CloseTable时，其会存储在dataTable数组的nextSlot索引位置。还需要更新对应的bucket链，将插入的entry置于链末尾。
当一个entry从hash table中删除时，其从dataTable中删除（eg：将key和value设置为undefined）。注：删除元素仍然占据着dataTable的空间，不会进行释放回收。
最后一部分，当table装满时，会申请一个更大的空间，并进行重新哈希排布。
这样，遍历Map只需遍历dataTable数组。保证了Maps的有序性质。

实际算法

来一些例子来解释该算法是如何工作的。假设我们有一个包含两个buckets且总容量为4的CloseTable对象（hashTable.length=2，datatable.length=4）。

1
2
3
4
5
// let's assume that we use identity hash function,
// i.e. function hashCode(n) {return n;}
table.set(0, 'a'); // => bucket 0 (0 % 2)
table.set(1, 'b'); // => bucket 1 (1 % 2)
table.set(2, 'c'); // => bucket 0 (0 % 2)

在该例子中，内部table的内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const tableInternals = {
	hashTable: [0, 1],
	dataTable: [
	{
		key: 0,
		value: 'a',
		chain: 2 // index of <2, 'c'>
	},
	{
		key: 1,
		value: 'b',
		chain: -1 // means tail entry
	},
	{
		key: 2,
		value: 'c',
		chain: -1
	},
	// empty slot
	],
	nextSlot: 3, // points to the empty slot
	size: 3
}

如果我们删除一个entry（table.delete(0)），table内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const tableInternals = {
	hashTable: [0, 1],
	dataTable: [
	{
		key: undefined, // deleted entry
		value: undefined,
		chain: 2
	}
	{
		key: 1,
		value: 'b',
		chain: -1 // means tail entry
	},
	{
		key: 2,
		value: 'c',
		chain: -1
	},
	// empty slot
	],
	nextSlot: 3, // points to the empty slot
	size: 2
}

如果我们继续插入两个新的entry，hash table则需要进行rehash，申请更大内存。
Sets使用的算法与之类似。仅有的区别为Set类型不需要value属性。

算法实现细节

C++语言编写并暴露给JS代码使用。主要部分定义在OrderdHashTable和OrderedHashMap类中。
对应代码实现：

容量大小

在V8中，hash table（Map）的大小总是2的指数倍。即表的最大容量为2 * number_of_buckets。当你创建一个空Map对象时，其hash table有两个buckets。因此其大小为4个entry。
最大容量有限制，在64位系统中最大为2^27，即不能超过16.7M个entries。
grow/shrink因子则是2。每次double或除2.
作者添加了一些修改逻辑使得可以打印出Maps的容量。
运行以下script：

1
2
3
4
5
6
7
8
9
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({}, {});
}

输出结果如下，验证上述增长过程：

1
2
3
4
5
6
7
|$ ./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|

map对象大小缩小也是同理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
|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;|
|}|
|}|
1
2
3
4
5
6
7
8
|$ ./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|

哈希函数

迄今为止，我们还没有讨论V8如何计算key键值的哈希值。
对于数值类变量而言（Smis，heap类数值，大整数等等），使用低碰撞概率的hash function
对于字符类值（字符串，符号），基于字符串内容计算hash
对于对象，基于一个随机数计算哈希值。

时间复杂度

大多数Map操作，set、delete，需要查表，类似于哈希表，时间复杂度为O(1)。
rehashing操作为O(N)时间复杂度。

内存占用

保存在堆上。整个Map对象保存在一个固定长度的数组（一个元素占用8字节）上。数组由如下布局：

头部包含了一些元数据信息。

参考链接