“in”运算符或obj.hasOwnProperty(prop)的Big O表示法效率是多少？

Question

Mozilla的网站清楚地描述了hasOwnProperty()和in运算符。但是，在它们的效率方面，它并没有给出任何实现细节。我会怀疑它们是O(1)（常数时间），但很想看到任何可能存在的参考或测试。

- haknick

---

这是一个哈希表，所以应该是 O(1)。 - alex

使用某种哈希算法是有意义的，因为属性定义上应该是唯一的，但最好检查一些参考资料，特别是IE如何实现它们。 - haknick

我会说这可能与具体实现相关。建议查看你最喜爱的开源实现的源代码。 - alex

Answer 1

将我的评论转化为答案。

hasOwnProperty() 应该是 O(1)，因为它是一个键查找，但具体实现可能不同。

in 会更加复杂（如果属性存在于该对象上，则应该与 hasOwnProperty() 相同），因为它沿着原型链向上查找该属性。这就是为什么在使用 for (in) 迭代对象属性时通常建议使用 hasOwnProperty()。

要了解详情，请检查这些函数的源代码。使用源代码，卢克 :)

- alex

---

由于在n个元素的集合中查找其中1个元素的时间不依赖于其他n-1个元素，因此"in"仍然是O(1)。 - haknick

尽管检查源代码是绝对好的建议，但我只是想省点时间，看看是否已经有人遇到过这个问题 :）。谢谢。 - haknick

@haknick 我想你已经回答了自己的问题 :) - alex

哈希表的性能也取决于哈希函数和哈希冲突的频率。如果哈希冲突很多，最坏情况下时间复杂度可能会达到O(log(n))或O(n)。当然，这还取决于索引的大小以及重新索引的频率（例如从32位索引到64位索引）。 - Suroot

Answer 2

我的理论是in应该比hasOwnProperty()更快。 根据标准，in其实是代理了hasProperty()函数（参见第79页：http://www.ecma-international.org/publications/files/ECMA-ST/ECMA-262.pdf），它是一种在整个语言中广泛使用的内部函数（因此可能被隐式地高度优化）。实际上，测试表明in平均速度更快。

链接：http://jsfiddle.net/VhhzR/2/ 在Firefox浏览器中，in明显更快。在Chrome浏览器中，只有在处理复杂对象时in才更快（这令人困惑）。在Internet Explorer浏览器中，in再次领先。

希望这能帮到您 :)

- David Titarenco

Answer 3

我认为它与对象属性查找机制没有什么不同，因为它们实际上执行相同的操作，区别在于hasOwnProperty(prop)只查找对象本身，而o.prop会沿着原型层次结构向下查找。

- Novikov

---

感谢你的回答。实际上我并不是在比较这两个，而是想深入了解它们的细节。 - haknick