3 ms·

> It's also typically faster to check if an element is in a set as opposed to in an Array What optimisations allow that? As sets in javascript maintain inserti

• chiefjosh 2y ago
  Probably a tree set, with O(log(n)) lookups
• Fishkins 2y ago
  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/Reference/Global_Objects/Set#description https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... 1: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashSet.html https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHa...
• augusto-moura 2y ago
  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