JavaScript“in”运算符是否在幕后执行循环？

Question

我正在研究一些常见算法的解决方案，并且遇到了一些我很好奇的东西。我试图通过谷歌搜索和查看一些规格来自己找到答案，但我无法找到我的问题的答案。下面的算法主要检查第一个数组中的每个项目是否在第二个数组中都有对应的项目平方。天真的解决方案（正如他们所说）将具有某种嵌套循环并被视为 O(n2)。写出下面解决方案的人说这是 O(n)。

我不明白这怎么可能是 O(n) 因为他在循环内使用了 Javascript“in”运算符。据我所知，运算符检查它所比较的​​值是否存在于对象中。如果它没有循环遍历引擎盖下的对象，它是如何做到这一点的？这真的是线性时间复杂度吗？

function same(arr1, arr2) {

  if (arr1.length !== arr2.length) {
    return;
  }

  let frequencyMap1 = {};
  let frequencyMap2 = {};

  for (let val of arr1) {
    frequencyMap1[val] = (frequencyMap1[val] || 0) + 1;
  }

  for (let val of arr2) {
    frequencyMap2[val] = (frequencyMap2[val] || 0) + 1;
  }

  for (let key in frequencyMap1) {
    if (!(key ** 2 in frequencyMap2)) {
      return false;
    }

    if (frequencyMap2[key ** 2] !== frequencyMap1[key]) {
      return false
    }
  }

  return true;
}

console.log(same([1, 2, 3], [1, 4, 9])); // true

Answer 1

在对象中查找键的时间复杂度为 O(1)。for .. in只是in运营商不同。

无论对象中有多少个键，您都可以在恒定时间内访问它。Object或者Map有一个哈希表来查找密钥。