访问对象中数据的复杂性

Question

在我日常工作的一些项目中，我需要访问非常大的 JS 对象中的数据（大约有数千个键值对）。我正在努力提高代码的效率，所以我提出了几个问题：

1. 访问此类对象中的字段时，JS 的运行时复杂度是多少？ 我最初的预感是 O(n)
2. 通过点表示法和括号表示法访问有区别吗？ （例如

   obj.field

   与

   obj[field]

   ）
3. 我猜不同的运行时引擎有不同的答案 - 有没有地方可以看到它们之间的区别？

Answer 1

Javascript 对象实际上是哈希，因此对于所有引擎来说复杂度都是

O(1)

。

obj.field

是

obj['field']

的别名，所以它们的性能是一样的。

您可以在这里找到一些 JS 哈希性能测试，不幸的是仅适用于您的浏览器引擎。

Answer 2

在最坏的情况下，JS 对象表示为 哈希表，并且具有相同的查找复杂度：平均为

O(1)

，但最坏的情况下为

O(n)

。我猜哈希表的实现就是你的情况，因为你的对象中有很多项目。访问属性的方式没有区别，obj.field

 和 

obj['filed']

 是相同的。

还值得一提的是，复杂性并不总是等于哈希表查找的复杂性，在很多情况下它更快。现代 JS 引擎使用称为“隐藏类”和“内联缓存”的技术来加速查找。这是一个相当大的问题，这些技术是如何工作的，我已经在

另一个答案中解释过。 一些相关资源： JavaScript 引擎基础知识：形状和内联缓存 以及

YouTube 视频

。

• V8 中的快速属性 V8 之旅：对象表示
• JavaScript 引擎隐藏类（以及为什么你应该记住它们）
• 其他答案对“JavaScript”做出了未经证实的声明 - 该规范本身并不保证键查找的任何时间复杂性。由于使用多个键访问对象是一种常见模式，因此大多数引擎可能会对其进行优化，并具有提供快速属性访问的对象表示。但很可能还有针对其他用例优化的其他表示，其查找复杂度为 O(n)。 如果您想要一个能够
保证

快速键查找的数据结构，您可能需要考虑使用

Answer 3

，其中

规范规定

：

映射必须使用哈希表或其他机制来实现，这些机制平均提供与集合中元素数量呈次线性关系的访问时间。本规范中使用的数据结构仅用于描述 Map 所需的可观察语义。它并不是一个可行的实施模型。