News for hackers. Stuff that matters.
Re:New JavaScript Set Methods by orangepanda on Monday June 24, 2024 @09:30AM (#40775824)
> 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) ?

Re:New JavaScript Set Methods by Fishkins on Monday June 24, 2024 @10:42AM (#40776651)
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...

Re:New JavaScript Set Methods by chiefjosh on Monday June 24, 2024 @09:45AM (#40775981)
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