> 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 insertion order, aren’t lookups O(n) ?
What optimisations allow that? As sets in javascript maintain insertion order, aren’t lookups O(n) ?
0: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
1: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHa...
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