According to the Mozilla docs, O(n) lookups would actually violate the spec [0]. As a sibling comment says, a tree set is one option to satisfy the spec. Another is a linked hash set, which would have O(1) lookups [1].
0: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
1: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHa...
Probably a tree set, with O(log(n)) lookups
Re:New JavaScript Set Methods
by augusto-moura on Monday June 24, 2024 @07:01PM
(#40782048)
It is usually implemented by a linked list + hash set (Java call this, drumroll... LinkedHashSet).
Because we are not adding elements in the middle of the list, only the end (we only care about insertion order), `add` is still O(1). `has` searches on the HashSet so it is also O(1). Delete is a bit more complex, you need to keep the list node reference on the set node, and then just splice it from the list. So O(1) as well
Of course this takes a lot more memory, but I think it usually pays off to have consistent ordering for sets, undefined/non-deterministic behavior is a virus and it spreads very quickly
What optimisations allow that? As sets in javascript maintain insertion order, aren’t lookups O(n) ?