在数组/对象中查找项目的最快方法

Question

如何在Javascript/AS3中寻找列表或对象中元素的索引？由于这两种语言的语法相似，我需要同时了解这两种情况下的答案。

假设：

myArray = ["one", "two", "three"];
myObject = {one:1, two:2, three:3};

哪种方法最快？在什么情况下需要使用它或不需要使用它？

• Array.indexOf(x)（数组查找）
• myObject[x] != null（对象属性查找）
• x in myObject（对象键查找）
• 其他方法？

- Robin Rodricks

---

通常情况下，使用原始数组并使用方括号表示法访问是最快的。但我相信一个简单的谷歌搜索就能得出你的答案。 - kennypu

Answer 1

使用一个对象并不是一个好主意，因为重新索引将是一项繁重的操作，并且如果有任何访问性能增益，它们将被抹掉。Array.indexOf(x)似乎是正确的做法。

- Christophe

Answer 2

对象使用高效的哈希表实现，因此查找键将是O(1)。如果您要“查找”的值是字符串且它们的位置是静态的，则这将非常快。检查布尔存在性可以使用key in obj，获取存储的索引将是obj[key] || -1。

如果您正在搜索更复杂的对象（不易序列化为字符串），则需要使用数组。Array.indexOf使用O(n)进行搜索，如果不经常进行搜索，则可以接受。检查存在性将是arr.indexOf(item) != -1，仅获取索引arr.indexOf(item)。

- Bergi

Answer 3

我已经对所需索引的本地indexOf和二进制搜索进行了一些测试。以下是在10,000个项数组上的结果。

价值 | IndexOf | 二进制搜索 ---|---|--- 1 | 0.003 | 0.013 5000 | 1.546 | 0.016 9990 | 3.105 | 0.015

测试是在node v8环境中完成的，但似乎本地indexOf使用循环来查找所需的索引。这里有一个链接到二进制搜索 http://oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/

- Vayrex