Search code examples
javascriptecmascript-6setcomplexity-theoryv8

es6 Map and Set complexity, v8 implementation

Is it a fair assumption that in v8 implementation retrieval / lookup is O(1)?

(I know that the standard doesn't guarantee that)

Solution

  • Is it a fair assumption that in v8 implementation retrieval / lookup is O(1)?

    Yes. V8 uses a variant of hash tables that generally have O(1) complexity for these operations.

    For details, you might want to have a look at https://codereview.chromium.org/220293002/ where OrderedHashTable is implemented based on https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables.