I was wondering how the new Set data structure is implemented in Javascript. In particular, what would be the Big O efficiency inserting, deleting, or checking if an item exists in a set.
Asked
Active
Viewed 59 times
0
-
1The standard actually specifies that the data should be stored in a list. So lookup would be `O(n)`. http://www.ecma-international.org/ecma-262/6.0/index.html#sec-set-iterable – Felix Kling Jun 01 '16 at 16:49
-
@FelixKling the spec says that the contents are iterable, but I would be stunned if real implementations did not use some sort of hash lookup. – Pointy Jun 01 '16 at 16:56
-
@FelixKling: No, the spec says it should *behave* as if it was a list. It also says that a list is not a valid implementation. – Bergi Jun 01 '16 at 16:58
-
Ah yeah, I missed that: "*Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection."* Though, it's interesting to me that they even use something like a list in the specification instead of leaving it abstract (like they do for object properties). – Felix Kling Jun 01 '16 at 16:59