Document time complexity

[joebandenburg]

From my reading of the code, you're using arrays to store the keys and values and searching them linearly in get and set. I think you should document in your README that the polyfill has worst algorithmic complexity than a real Map implementation. The polyfill insert and lookup operations are O(n) whereas any decent native implementation will have O(1) (or perhaps O(log n)) operations. This difference may matter to your users.

[medikoo]

@joebandenburg this is how you would naturally implement it (without overthinking optimisation in first place). It's also how ECMAScript specifies the lookup, (it's O(n)). So it's not a deviation from spec we're doing here, or other lie that needs to be exposed.

Still, of course lookup can be internally more optimal, and there's already opened issue for that. See #2

[brianmhunt]

@medikoo : @joebandenburg is correct. See my question on point, including (for example, from the ES6 spec):

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

So using O(n) array lookup differs from the requirements of the spec, and so probably worth noting (IMHO).

Cheers

[medikoo]

@brianmhunt yes, but it's not possible to obey to that paragraph without altering the objects which are added as map keys, and for frozen objects it's not possible at all.

So if you look at it from right perspective, every Map polyfill should contain similar note :)

Anyway since v1 es6-map will do O(1) for most (not frozen of course) cases, I agree it's acceptable in ES5 world (it defnitely wouldn't in ES3 world, but this polyfil doesn't support ES3)

[medikoo]

I noticed many people trying to use this library expected O(1), therefore I added note as requested to the readme.
It'll be addressed with v1, but due to limited time I can devote into it, I'm not able to state any certain date when it'll happen