首先,对于 JavaScript 中可用的数据结构存在一些基本的混淆。
TL;DR
-
如果您想要对具有短原型继承链的对象进行最快的键查找,请使用in
.
-
如果您想要相同,但对于具有广泛继承链的对象,请使用Object.prototype.hasOwnProperty
-
如果您想要最快的值查找,请使用Array.prototype.indexOf
for Array
.
-
哈希表中没有用于查找值的内置函数。当然,您可以自己推出,但有许多库已经提供了这一功能。例如,Underscore 提供了一个(它称之为indexOf
).
JavaScript 没有数组
从根本上来说,JavaScript 只有哈希表。标准Array
函数构造哈希表(我将这些称为整数哈希表, or 整数哈希表) 其中键除了字符串键之外还可以是整数。它们的性能与数组类似,但它们在某些方面有所不同。有缺点也有优点。例如,从 int-hash-table 中删除一个元素是一个 O(1) 操作,而从数组中删除一个元素是一个 O(n) 操作(因为您需要将其余元素复制到新数组中)。这就是为什么Array.prototype.splice
JavaScript 中的函数非常快。缺点是实现的复杂性。
所以,当你说Array
在 JavaScript 上下文中,它被理解为 int-hash-table,以及与之相关的所有渐近复杂性。这意味着如果你想找到一个字符串value在 int-hash-table 中,那么这将是一个 O(n) 操作。有一个标准函数可以做到这一点:Array.prototype.indexOf
。但是,如果您想寻找key,则有两个函数:in
and Object.prototype.hasOwnProperty
.
有点违反直觉:
[1, 2, 3].hasOwnProperty(0); // true
0 in [1, 2, 3]; // true
两者的区别需要进一步解释。这与 JavaScript 中的所有事物都是对象这一事实有关,因此它们具有一些对象特性。其中之一的特点是prototype
,对象与其原型之间的链接。它是哈希表的分层结构,每个哈希表都包含对象的属性。
由于 JavaScript 的动态特性,所有函数调用都是动态的,并且环境必须非常小心以确保故障安全的代码执行。这意味着 JavaScript 中的函数调用非常昂贵。所以,经过Object.prototype.hasOwnProperty
可能比经历要贵很多in
,尽管理论上应该是相反的。然而,如果有足够高的继承树和足够的继承属性,最终,Object.prototype.hasOwnProperty
将接管。
一些获得更好直觉的例子:
>>> var array = [1, 2, 3];
undefined
>>> 3 in array;
false
>>> array.hasOwnProperty(3);
false
>>> 3 in array;
false
>>> array.__proto__ = [1, 2, 3, 4];
[1, 2, 3, 4]
>>> 3 in array;
true
>>> array.hasOwnProperty(3);
false