Javascript对象Big-O

Question

来自Java,Javascript对象让我想起了Java中的HashMap.

使用Javascript:

var myObject = {
    firstName: "Foo",
    lastName: "Bar",
    email: "foo@bar.com"
};

Java的:

HashMap<String, String> myHashMap = new HashMap<String, String>();
myHashMap.put("firstName", "Foo");
myHashMap.put("lastName", "Bar");
myHashMap.put("email", "foo@bar.com");

在Java HashMap中,它使用密钥的hashcode()函数来确定存储和检索的存储区位置(条目).大多数时候,对于诸如put()和get()之类的基本操作,性能是恒定时间,直到发生哈希冲突,这对于这些基本操作变为O(n),因为它形成链表以便存储相互冲突的条目.

我的问题是:

1. Javascript如何存储对象？
2. 运营的表现如何？
3. 是否会出现任何会像Java中那样降低性能的碰撞或其他情况

谢谢!

Answer 1

Javascript看起来像是将东西存储在地图中,但通常情况并非如此.您可以访问对象的大多数属性,就像它们是地图中的索引一样,并在运行时分配新属性,但支持代码比仅使用地图要快得多,也更复杂.

没有什么需要VM不使用映射,但是大多数尝试检测对象的结构并为该结构创建有效的内存中表示.在程序运行时,这可能会导致大量优化(和deopts),并且是一个非常复杂的情况.

这篇博客文章在@Zirak的问题评论中进行了链接,对公共结构以及VM何时可以从结构转换为地图进行了很好的讨论.它通常看起来不可预测,但主要基于VM中的一组启发式以及它认为它看到了多少个不同的对象.这主要与返回值的属性(及其类型)有关,并且往往以每个函数(尤其是构造函数)为中心.

有一些问题和文章深入细节(但希望在没有大量背景的情况下仍然可以理解):

• 当对不同对象中的函数使用相同的键时,在V8中调用慢函数
• 为什么比调用hasOwnProperty更快地获得成员？
• http://mrale.ph/blog/2013/08/14/hidden-classes-vs-jsperf.html(以及本博客的其他部分)

基于上述情况,性能差异很大.最坏的情况应该是地图访问,最好的情况是直接内存访问(甚至可能是deref).

有很多场景可能会对性能产生影响,特别是考虑到JITter和VM在运行时如何创建和销毁隐藏类,因为它们会看到对象的新变化.突然遇到一个被假定为单态的对象的新变体会导致VM切换回不太理想的表示并停止将对象视为内存中的结构,但是围绕它的逻辑非常复杂且很好- 在这篇博客文章中.

您可以通过确保从同一构造函数创建的对象倾向于具有非常相似的结构,并使事情尽可能可预测(对您,维护和VM有益)来提供帮助.拥有每个对象的已知属性,为这些属性设置类型,以及在构造函数中创建对象时,可以让您点击大多数可用的优化并拥有一些非常快速的代码.