我不知道的 V8（03）— 为什么字典是"非线性"数据结构

“字典是非线性数据结构”这句话在很多前端技术文章里出现，但很少有人解释清楚：这里的”非线性”是什么意思，和”线性”相比到底差在哪，以及 V8 为什么要在对象属性存储上区分线性和非线性。

一、先理清：线性 vs 非线性

线性数据结构的特征：元素按顺序存放，位置可预测。JavaScript 数组就是典型例子：

const arr = [10, 20, 30];
// arr[0] 在某个内存地址 addr
// arr[1] 在 addr + 8 字节（64 位系统下每个元素 8 字节）
// arr[2] 在 addr + 16 字节

访问 arr[n] 时，计算公式是 addr + n * elementSize，直接算出内存位置，不需要任何查找过程。时间复杂度 O(1)，且内存连续，对 CPU 缓存非常友好。

非线性数据结构的特征：元素存放位置由哈希函数决定，元素之间没有固定的顺序关系：

const obj = { name: 'V8', version: '8.4' };
// "name" 的哈希值 → 存到桶 5
// "version" 的哈希值 → 存到桶 3
// 两者在内存中不相邻，顺序不可预测

访问 obj.name 时，先计算 "name" 的哈希值，然后去对应的桶找，可能还要处理哈希冲突。虽然平均时间复杂度也是 O(1)，但有哈希计算的固定开销，内存不连续，CPU 缓存也没那么友好。

二、V8 对象的两种存储模式

V8 对对象属性的存储并不总是哈希表（字典），它默认使用快属性（Fast Properties）——线性存储：

const obj = { name: 'V8', version: '8.4' };

V8 内部结构（简化）：

隐藏类 C0:
  name    → offset 0
  version → offset 1

obj 的属性存储: [ "V8", "8.4" ]

访问 obj.name → 查隐藏类得 offset 0 → 直接读数组第 0 个元素。这是线性访问，速度和访问数组元素差不多。

只有当对象变得”不稳定”时，V8 才切换到**慢属性（Slow Properties）**模式，使用哈希表（字典）存储：

const obj = { name: 'V8' };
delete obj.name; // 删除操作破坏隐藏类
obj.version = '8.4'; // V8 决定：这个对象不稳定，切换到字典模式

切换后：

obj 的属性存储 (字典模式):
  哈希表: {
    桶 3: { key: "version", value: "8.4" }
    桶 5: <empty>
    ...
  }

为什么叫”字典”？ 因为这种结构的访问方式和字典一样——给一个 key，查出对应的 value，中间有一步哈希计算。

三、哈希表如何工作

V8 的字典模式基于哈希表实现（源码中为 NameDictionary）。工作原理：

1. 哈希计算

对属性名（键）计算哈希值，例如 "name" → 哈希值 42 → 存入桶 42 % 桶数量。

2. 冲突处理

不同属性名可能得到相同哈希值（哈希冲突）。V8 使用开放寻址法处理冲突：冲突时线性探测下一个空桶。

假设哈希表有 8 个桶，"name" 和 "age" 都映射到桶 3：

初始：
桶 3: { key: "name", value: "V8" }

添加 "age"：
桶 3 已被占用 → 探测桶 4
桶 4: { key: "age", value: 1 }

3. 扩容与缩容

当哈希表填充率（load factor）超过 70% 时，V8 触发扩容，分配更大的哈希表，重新散列所有键值对。填充率低于 30% 时触发缩容。扩容操作的开销不小，这也是频繁操作字典的代价之一。

四、字典模式的代价究竟是什么

字典模式的核心代价是访问开销大于快属性，且难以被内联缓存优化：

// 验证：对比快属性 vs 慢属性的访问模式
const fastObj = { x: 1, y: 2 }; // 快属性
const slowObj = { x: 1 }; // 即将变慢
delete slowObj.x;
slowObj.y = 2; // 变为字典模式

// 对 fastObj.x 的访问：
// 1. 查内联缓存，命中隐藏类 → 直接读 offset 0

// 对 slowObj.x 的访问（x 不存在，找 y）：
// 1. 查内联缓存，可能命中字典模式缓存
// 2. 计算 "x" 的哈希值
// 3. 找到对应桶，检查 key 是否匹配（还可能探测多个桶）

用 V8 内置工具验证属性模式：

// 需要 node --allow-natives-syntax your-script.js
const obj = { x: 1 };
console.log(%HasFastProperties(obj)); // true

delete obj.x;
obj.y = 2;
console.log(%HasFastProperties(obj)); // false

五、字典 vs 数组：哪个更适合你的场景

并不是说字典模式就一定差——对于某些场景，哈希表反而是更好的选择：

场景	推荐结构	原因
固定结构、频繁读取	普通对象（快属性）	线性访问，最快
频繁增删键值对	`Map`	专为动态操作设计，无隐藏类问题
大量属性（> 几十个）	`Map` 或字典模式对象	快属性对大量属性的收益递减
数字键、类数组	数组或 TypedArray	线性存储，完全发挥 CPU 缓存

// 频繁增删的场景，Map 比对象更合适
const fastCache = new Map();
fastCache.set('user:1', { name: 'V8' });
fastCache.delete('user:1');
// Map 的 set/delete 不会导致隐藏类变化，性能稳定

// 对比：用对象做同样的事
const slowCache = {};
slowCache['user:1'] = { name: 'V8' };
delete slowCache['user:1'];
// 每次 delete 都可能触发字典模式切换

六、总结

“字典是非线性数据结构”的意思：属性存储位置由哈希函数决定，元素在内存中不相邻，没有固定的索引关系。这和数组（元素位置由索引直接计算）的线性特性形成对比。

V8 优先让对象用快属性（线性存储）而非字典模式，是因为快属性配合隐藏类，能让属性访问退化为内存偏移量读取，比哈希查找快得多。只有当对象结构变得动态（频繁增删属性、属性过多），维持隐藏类的成本大于收益时，才切换到字典模式。

本系列其他文章：