JavaScript对象的大O表示法

Question

作为来自Java的人，Javascript中的对象让我想起了Java中的HashMap。

Javascript：

var myObject = {
    firstName: "Foo",
    lastName: "Bar",
    email: "[e-mail]"
};

Java：

HashMap<String, String> myHashMap = new HashMap<String, String>();
myHashMap.put("firstName", "Foo");
myHashMap.put("lastName", "Bar");
myHashMap.put("email", "[e-mail]");

在Java中的HashMap使用key的hashcode()函数来确定桶位置(条目)进行存储和检索。大多数情况下，像put()和get()这样的基本操作性能都是恒定的，直到发生哈希冲突，这些基本操作的性能变为O(n)，因为它形成了一个链表以存储冲突的条目。

我的问题是：

1. Javascript如何存储对象？
2. 操作的性能如何？
3. 是否会出现与Java类似的碰撞或其他情况，从而降低性能？

谢谢！

- user2712937

---

请查看此链接，它包含了关于你问题的一些好信息：https://github.com/benblack86/java-snippets/blob/master/resources/java_collections.pdf - Evan Bechtol

@EvanBechtol 那篇论文是关于 Java 的，而这个问题是关于 JavaScript 性能的。 - Pointy

对象存储是实现相关的。话虽如此，这个问题可以针对v8和spidermonkey进行回答，但这些都是很长的答案。 - Florian Margaine

好问题！不幸的是，答案取决于具体实现。基本上，所有js对象处理都是O(1)的。v8（Chrome引擎）首先为您的对象创建一个结构体，使您能够获得最快的访问速度。一旦超过键计数，它就会退回到基本的哈希表模式。更多信息请参见此处：http://jayconrod.com/posts/52/a-tour-of-v8-object-representation。 - Zirak

大多数浏览器实际上更像是LinkedHashMap而不是HashMap：http://code.google.com/p/v8/issues/detail?id=164。不过它的实际情况可能更加复杂。 - Adam Gent

Answer 1

Javascript看起来像是将数据存储在一个映射表中，但实际情况通常并非如此。虽然可以通过类似于在映射表中使用索引的方式访问对象的大多数属性，并在运行时分配新的属性，但底层代码比仅仅使用映射表要快得多且更为复杂。

虚拟机不一定需要使用映射表，但大多数虚拟机都试图检测对象的结构并为该结构创建有效的内存表示。这可能会导致许多优化（和反优化）在程序运行时发生，这是一种非常复杂的情况。

本博客文章由@Zirak在评论中提供，详细讨论了常见的结构以及虚拟机何时会从结构切换到映射表。它经常看起来难以预测，但在虚拟机内部基于一组启发式规则，以及它认为已经看到了多少不同的对象。这与返回值的属性（及其类型）密切相关，通常集中在每个函数（特别是构造函数）周围。

有一些问题和文章深入探讨了细节（但希望仍然可以在没有大量背景的情况下理解）：

• 不同对象中使用相同键调用函数时V8运行速度缓慢
• 获取成员比调用hasOwnProperty更快的原因是什么？
• http://mrale.ph/blog/2013/08/14/hidden-classes-vs-jsperf.html（以及这个博客的其余部分）

性能会根据以上因素而有很大差异。最坏情况应该是映射表访问，最好情况是直接内存访问（甚至是一次解引用操作）。

有许多场景可能会对性能产生影响，尤其是当JITter和虚拟机在运行时创建和销毁隐藏的类时，它们会看到对象的新变化。突然遇到以前被认为是单态的对象的新变体可能会导致虚拟机切换回较少优化的表示方式，并停止将对象视为内存结构。但这方面的逻辑相当复杂，在 此博客文章中得到了详细介绍。

您可以通过确保从同一构造函数创建的对象具有非常相似的结构，并尽可能使事情更可预测（有利于您、维护和虚拟机）。为每个对象设置已知属性，为这些属性设置类型，并在可能的情况下从构造函数创建对象，这样可以让您达到大部分可用的优化，并拥有非常快的代码。

- ssube