JS `Map` 与 `Set` 的 V8 内部优化：哈希表与快速查找

哟，大家好！今天咱们来聊聊 JavaScript 里 Map 和 Set 这俩哥们儿，看看 V8 引擎是怎么在它们身上动刀子，让它们跑得飞快的。咱们主要扒一扒哈希表，还有那些为了快速查找耍的小聪明。

一、Map 和 Set：不是亲兄弟，胜似亲兄弟

先简单回顾一下这俩货是干啥的：

• Map： 键值对的集合。就像一本字典，你可以通过一个“键”（key）快速找到对应的“值”（value）。键可以是任何数据类型，不限于字符串。

• Set： 唯一值的集合。就像一个不允许重复元素的数组。

它们俩最大的特点就是查找速度快，理论上是 O(1) 的时间复杂度。这多亏了它们的底层实现——哈希表。

二、哈希表：高效查找的秘密武器

哈希表，又叫散列表，是一种根据键（Key）直接访问内存存储位置的数据结构。简单来说，它通过一个哈希函数，把键转换成一个索引，然后根据这个索引去访问数组中的元素。

1. 哈希函数：指路明灯

   哈希函数的作用就是把各种类型的键转换成一个整数，这个整数就是数组的索引。好的哈希函数应该尽量让不同的键产生不同的索引，避免冲突。

   举个简单的例子，假设我们要存储一些字符串，可以用字符串的第一个字符的 ASCII 码作为哈希值。

   function simpleHash(key) {
     return key.charCodeAt(0);
   }
   
   console.log(simpleHash("apple")); // 输出 97 (a 的 ASCII 码)
   console.log(simpleHash("banana")); // 输出 98 (b 的 ASCII 码)

   这个 simpleHash 函数就很简单粗暴，但问题也很大。比如 "apple" 和 "ant" 的哈希值都是 97，这就发生了哈希冲突。

   V8 用的哈希函数肯定比这个复杂得多，它会考虑键的更多信息，力求让哈希值分布得更均匀。

2. 哈希冲突：冤家路窄

   再好的哈希函数也无法完全避免冲突。当两个不同的键产生了相同的哈希值时，就发生了哈希冲突。解决冲突的方法有很多，常见的有：

   • 链地址法： 把哈希值相同的元素放到一个链表里。这样，每个数组元素都指向一个链表，链表里存放着哈希值相同的元素。

   • 开放寻址法： 如果哈希值对应的位置已经被占用，就寻找下一个空闲的位置。寻找的方法有很多，比如线性探测、二次探测等。

   V8 里面，Map 和 Set 的实现会根据键的数量和类型，动态地选择合适的冲突解决方法，以达到最佳性能。

3. 哈希表的动态扩容：未雨绸缪

   随着元素的增多，哈希表会变得越来越拥挤，查找效率也会下降。为了保持高效，哈希表需要动态扩容。当哈希表达到一定的负载因子（load factor）时，就会自动增加数组的大小，然后重新计算所有元素的哈希值和位置。

   V8 会根据实际情况调整负载因子，以平衡内存占用和查找效率。

三、V8 如何优化 Map 和 Set？

V8 为了让 Map 和 Set 跑得更快，可是下了不少功夫。

1. Smi（Small Integer）优化：小整数的福音

   Smi 是 V8 内部对小整数的一种特殊表示方式。Smi 直接把整数的值存储在指针里，而不需要额外的内存分配。这样可以大大提高小整数的访问速度。

   如果 Map 的键或 Set 的元素是 Smi，V8 就可以直接使用 Smi 的值作为哈希值，避免了哈希函数的计算，从而提高了查找速度。

   const map = new Map();
   map.set(1, "one"); // 键是 Smi
   map.set(2, "two"); // 键是 Smi
   
   const set = new Set();
   set.add(3); // 元素是 Smi
   set.add(4); // 元素是 Smi

2. 专用哈希函数：量身定制

   V8 会根据键的类型，选择不同的哈希函数。比如，对于字符串，V8 会使用一种高效的字符串哈希函数；对于对象，V8 会使用对象的内存地址作为哈希值。

   这样可以最大限度地减少哈希冲突，提高查找效率。

3. 内联缓存（Inline Caching）：缓存加速

   内联缓存是一种优化技术，V8 会把经常访问的对象的类型信息和属性信息缓存起来。当下次访问相同的对象时，V8 就可以直接从缓存中读取信息，而不需要重新查找。

   内联缓存在 Map 和 Set 的查找过程中也发挥了重要作用。V8 会缓存键的类型信息和哈希值，这样可以避免重复计算哈希值，提高查找速度。

   const map = new Map();
   const obj = { name: "Alice" };
   map.set(obj, "Alice's value");
   
   // 第一次访问 map.get(obj)，V8 会缓存 obj 的类型信息和哈希值
   console.log(map.get(obj));
   
   // 第二次访问 map.get(obj)，V8 直接从缓存中读取信息，速度更快
   console.log(map.get(obj));

4. 隐藏类（Hidden Classes）：对象的秘密身份

   隐藏类是 V8 内部用来描述对象结构的一种机制。V8 会把具有相同属性的对象归为同一个隐藏类。

   隐藏类可以帮助 V8 快速访问对象的属性。当 Map 的键是对象时，V8 可以利用隐藏类来加速查找过程。

   function Person(name, age) {
     this.name = name;
     this.age = age;
   }
   
   const alice = new Person("Alice", 30);
   const bob = new Person("Bob", 25);
   
   const map = new Map();
   map.set(alice, "Alice's info");
   map.set(bob, "Bob's info");
   
   // alice 和 bob 具有相同的隐藏类，V8 可以利用隐藏类来加速查找
   console.log(map.get(alice));
   console.log(map.get(bob));

5. 树形结构优化：当哈希表不再是最佳选择

   虽然哈希表在大多数情况下表现出色，但当键的数量非常少时，哈希表的性能优势并不明显。此外，哈希表需要额外的内存开销来维护哈希函数和处理冲突。

   V8 针对这种情况进行了优化。对于键的数量较少的 Map 和 Set，V8 可能会选择使用更简单的数据结构，如线性列表或树形结构（例如红黑树）。这些数据结构在小规模数据下具有更低的内存开销和更快的查找速度。

   具体来说，V8 会根据键的数量动态地切换数据结构。当键的数量超过某个阈值时，V8 会将数据结构从线性列表或树形结构切换到哈希表。这种动态切换机制可以确保 Map 和 Set 在各种情况下都能保持最佳性能。

   例如，以下代码演示了 Map 可能发生的结构切换 (注意：这只是一个简化的说明，实际V8的实现要复杂得多)：

   const map = new Map();
   
   // 键的数量很少，V8 可能使用线性列表或树形结构
   map.set('a', 1);
   map.set('b', 2);
   map.set('c', 3);
   
   // 键的数量超过阈值，V8 可能会切换到哈希表
   for (let i = 0; i < 100; i++) {
      map.set(i, i);
   }
   
   console.log(map.get('a')); // 查找操作

6. 垃圾回收优化：保持内存健康

   Map 和 Set 存储着大量的键值对或元素，如果这些键值对或元素不再使用，就会占用大量的内存。为了释放这些内存，V8 的垃圾回收器会定期扫描 Map 和 Set，回收不再使用的键值对或元素。

   V8 的垃圾回收器采用了多种优化技术，比如增量标记和并发标记，以减少垃圾回收对程序性能的影响。

四、Map vs Object：该选谁？

很多人会问，既然 Object 也能存储键值对，那 Map 还有什么用？

特性	Object	Map
键的类型	只能是字符串或 Symbol	可以是任何数据类型
键的顺序	不保证键的顺序	保证键的插入顺序
性能	在键的数量较少时，性能可能更好	在键的数量较多时，性能更好
原型链	会继承原型链上的属性	不会继承原型链上的属性
迭代	需要手动迭代	可以直接使用 for...of 迭代
大小	需要手动计算大小	可以使用 size 属性获取大小

简单来说，如果键的类型不确定，或者需要保证键的顺序，或者需要存储大量的键值对，那么 Map 是更好的选择。如果键的类型是字符串，而且键的数量较少，那么 Object 也是可以的。

五、代码示例：感受一下性能差异

const size = 100000;

// Object
const obj = {};
console.time("Object set");
for (let i = 0; i < size; i++) {
  obj[i] = i;
}
console.timeEnd("Object set");

console.time("Object get");
for (let i = 0; i < size; i++) {
  obj[i];
}
console.timeEnd("Object get");

// Map
const map = new Map();
console.time("Map set");
for (let i = 0; i < size; i++) {
  map.set(i, i);
}
console.timeEnd("Map set");

console.time("Map get");
for (let i = 0; i < size; i++) {
  map.get(i);
}
console.timeEnd("Map get");

在我的机器上，Map 的 set 和 get 操作都比 Object 快。当然，这只是一个简单的测试，实际性能会受到很多因素的影响。

六、总结：V8 的良苦用心

V8 为了优化 Map 和 Set，采用了多种技术，包括哈希表、Smi 优化、专用哈希函数、内联缓存、隐藏类、结构切换优化和垃圾回收优化。这些优化技术使得 Map 和 Set 在各种情况下都能保持高效的性能。

希望今天的分享能让你对 Map 和 Set 的内部实现有更深入的了解。下次使用它们的时候，就能更加自信地掌控它们的性能了。

好了，今天的讲座就到这里，谢谢大家！有问题可以随时提问。