有什么可以保证在 JavaScript 中访问对象属性的时间恒定吗?

IT技术 javascript data-structures time-complexity complexity-theory
2021-03-08 03:07:54

这是关于我在亚马逊面试时与面试官进行的辩论。

让我们创建一个对象:

var Obj = {};
Obj['SomeProperty'] = function ( ) { console.log("Accessed some property"); };
Obj[69] = true;

有没有在JavaScript任何保证荷兰国际集团,当我随后访问这些2个属性,如Obj['SomeProperty']Obj[69]相应的值function ( ) { console.log("Accessed some property"); };,并69在Ø抬头(1)的时间?我知道接入运营商[]提供了一个经验丰富的程序员的印象是,他处理一个O(1)查找结构,但不能将它有可能为一个JavaScript引擎来实现Object的方式,使得性能为O抬头(1 )?

1个回答

JavaScript 中是否有任何内容可以保证在 O(1) 时间内查找值?

。JavaScript不提供任何复杂性保证,除了 ES6 集合

我知道访问运算符[]给经验丰富的程序员的印象是他正在处理 O(1) 查找结构

是的,这是一个合理的期望。引擎采用各种优化,从哈希映射上的隐藏类到动态数组,以满足这些假设。

当然,永远不要忘记 JS 对象是复杂的野兽,访问一个简单的属性可能会触发一个 getter 陷阱,而这个陷阱又可以做任何事情。

JavaScript 引擎不能以某种方式实现 Object 使得属性不在 O(1) 中查找吗?

是的,这是可能的。

@Halcyon:哈希表是 O(1) 摊销的。也许还可以参见stackoverflow.com/q/6586670/1048572
2021-04-22 03:07:54
@Halcyon:有关超越了简单的“哈希表”对象的优化更多信息请参考developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/...developers.google.com/v8/design#prop_access,甚至google.com/patents/US8244775
2021-05-01 03:07:54
您能否详细说明属性查找的复杂性?我一直认为它们是 O(log n)(哈希表、二分查找之类的)。O(1)怎么可能是一回事?
2021-05-05 03:07:54