在Javascript数组中查找元素的有效方法

Question

我正在使用带标题的数组.每个标题索引对应于数据库中的id,该id包含该给定标题的html.

假设我有一个包含其中一个标题的字符串.

title = "why-birds-fly";
titles[] // an array which contains all the titles

要使用字符串"title"来获取相应的ID,我可以这样做:

for (i = 0; i < titles.length-1; i++) {
  if (titles[i] == title)
    return i+1;
}

我可以使用的另一种方法是创建一个关联数组和titles数组,这与titles完全相反.也就是说,它使用字符串作为索引并返回数字.

titles_id {blah:0,why-birds-fly:1,blah2:2}

然后我可以通过以下方式访问ID:

return titles_id[title]+1;

考虑到CPU,内存等,最有效的是什么？

另外,如果我的逻辑完全错误,请告诉我.

谢谢威廉

Answer 1

线性搜索方法具有O(n)的复杂性,我认为关联数组方法的最坏情况可能是O(log n),(如果JS引擎使用哈希并得到最好的情况可能是O(1)没有碰撞).它将取决于JS引擎通常如何实现关联数组/对象,但您可以确定它将超过O(n).

因此,第二种方法会更快,但当然会使用更多内存.这是一个非常典型的权衡,获得更快的速度,但使用更多的内存,只有你可以决定是否要进行交易.