JavaScript对象按键取值时间复杂度是否为O(1)？数组交集实现疑问

Your Core Confusion: Is obj[key] Truly O(1)? #

Great question—this is a super common point of confusion because while JavaScript objects act like hash tables, their underlying implementation (especially in modern engines like V8) has nuance that affects worst-case time complexity:

• Average Case: Yes, property access on objects is effectively O(1). Engines use optimized hash tables (or "fast properties" for small object sizes) to keep lookup times minimal.
• Worst Case: In rare scenarios—like thousands of keys with hash collisions, or keys that force the engine to fall back to slower property storage—lookups can degrade to O(n). Plus, objects inherit properties from their prototype chain: if your array includes values like toString or valueOf, obj[v] might accidentally return a prototype method instead of your stored true, leading to bugs and unexpected overhead.

Your original solution works for most cases, but your interviewer was right to push on this—relying on plain objects has edge cases that can break the O(1) assumption, or at least introduce avoidable risks.

Fixing the Solution: Use ES6 Set for Reliable Linear Time Complexity #

The ES6 Set structure was built explicitly for this kind of set operation, and it fixes all the flaws of plain objects:

• Set.has() is specified to have average O(1) time complexity (worst-case O(n) only in extreme collision scenarios, which engines actively mitigate).
• No prototype chain interference—keys are exactly the values you add, so no false positives from inherited properties.
• Code that clearly expresses the set intersection intent, making it easier to maintain.

Here's the revised implementation:

function findIntersection(ary1, ary2) {
  const valueSet = new Set(ary1);
  // Filter the second array to keep only values present in the set
  return ary2.filter(value => valueSet.has(value));
}

Why This Works Better: #

• Time Complexity: Building the set takes O(m) time (where m is the length of ary1), and filtering ary2 takes O(n) time (n is the length of ary2). Overall average time complexity is O(m + n)—exactly what you initially claimed.
• Correctness: Avoids bugs where array elements match prototype property names. For example, if ary1 didn't include 'toString', your original code would still return true for hash['toString'] (since it's inherited from Object.prototype), leading to false positives.
• Readability: The code directly communicates that you're working with set logic, which makes it easier for other developers (and future you) to understand.

Final Note on Time Complexity Assumptions #

It's key to distinguish between theoretical worst-case complexity and real-world performance. For almost all practical use cases, both plain objects and Set will deliver O(1) average lookup time. But Set is the safer, more idiomatic choice here—it eliminates edge cases and aligns perfectly with the intended use of hash-based set operations.

内容的提问来源于stack exchange，提问作者user1884378