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

Question

我正在使用带有标题的数组。 每个标题索引对应于数据库中的一个 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_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)。

因此，第二种方法会更快，但当然会使用更多内存。 这是一个非常典型的权衡，获得更快的速度，但使用更多的内存，并且仅您可以决定是否要进行该交易。

Answer 2

考虑需要存储的键值对的数量也很重要。 如果它小于~50（取决于实现），那么由于计算哈希值和解决冲突的成本，执行线性搜索将与执行哈希表查找一样有效。 一个例外是 Google Chrome v8 JavaScript 引擎保留了所有对象的某种缓存版本，允许它直接查找对象上的属性，因此使用 Object 类作为哈希表可能会更快，尽管我不确定创建此缓存版本的成本是否会超过较小列表的好处。

Answer 3

您可以在第一个方法中使用 Array 的 indexOf 函数。

以下是来自 Mozilla 开发者的信息：
https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference： Objects:Array:indexOf

indexOf 是 ECMA-262 标准的 JavaScript 扩展； 因此，它可能不会出现在该标准的其他实现中。 您可以通过在脚本开头插入以下代码来解决此问题，从而允许在本机不支持的 ECMA-262 实现中使用 indexOf。 该算法正是 Firefox 和 SpiderMonkey 中使用的算法。

if (!Array.prototype.indexOf)
{
  Array.prototype.indexOf = function(elt /*, from*/)
  {
    var len = this.length >>> 0;

    var from = Number(arguments[1]) || 0;
    from = (from < 0)
         ? Math.ceil(from)
         : Math.floor(from);
    if (from < 0)
      from += len;

    for (; from < len; from++)
    {
      if (from in this &&
          this[from] === elt)
        return from;
    }
    return -1;
   };
}

Answer 4

Javascript 数组可以使用诸如标题“why-birds-fly”之类的值作为索引。

示例：
var title = "为什么鸟会飞";

var TitleArray[] = new Array();

TitleArray[标题] = id;

然后你可以通过标题直接访问id：

return TitleArray[title];