2

我从后端返回的数据包含大量参考数据，我需要有效地访问它，所以我正在考虑创建（对象的 id）=>（对象本身）类型查找。对象的 ID 作为字符串返回，我想知道整数作为哈希键是否比字符串快？

playerLookup = {};
for (var i = 0; i < players.length; i++) {
  var player = players[i];
  playerLookup[player.id] = player;
  // vs.
  playerLookup[parseInt(player.id)] = player;
}

根据 jsperf 测试http://jsperf.com/testasdfa，在 Chrome 上的整数查找要快得多（~25%）。不确定测试场景是否正确。你怎么看？

4

1 回答 1

1

我的观点是找到元素的最快方法是通过模块化哈希表。

使 playerLookup 成为一个包含 n 个元素的数组，数组的每个元素都设置为 -1（或某个值，让您知道该位尚未设置）。

当您存储 playerId 时，将其存储在playerLookup[parseInt(player.id) % n]

以这种方式从哈希表中查找项目的工作复杂度为 1，但您上面列出的方法的工作复杂度为 x 其中 x = playerLookup.length （无论您使用字符串还是数字作为键） .

要使哈希表更小，请选择更小的 n。n 越小，我们就越有可能发生冲突。

冲突

要处理冲突，请将 playerLookup 的每个元素设为数组。如果您在已经包含另一个玩家的位置将 playerId 添加到 playerLookup 中，请在该位置旁边列出新的（即现在两者都在同一个位置）。如果您查找一个玩家并在哈希表中找到一个包含多个玩家的位置，只需遍历此数组直到找到该玩家。此迭代将与您想到的第一个实现具有相同的工作复杂性，但有两个优点：

  1. 由于模块化哈希表，它甚至不太可能发生

  2. 当它确实发生时，我们正在迭代的数组平均比您实现的原始数组小 n 倍（其中 n 是我们的模变量）。

出于数学原因（使用模数），我建议为 n 选择一个素数。

于 2013-01-17T03:01:58.363 回答