Map/Set.prototype.size is O(n)

Isiah Meadows isiahmeadows at gmail.com
Wed Mar 29 23:40:43 UTC 2017


The only part that matters is that it's *observably* equivalent
functionally. In theory, `indexOf` could be done in constant steps
provided there are no indexed getters or setters, and there's no
overriding proxy hook. It'd be impractical to ensure that, but it's
still theoretically possible to both do that and remaining conformant.
-----

Isiah Meadows
me at isiahmeadows.com


On Wed, Mar 29, 2017 at 11:31 AM, Oriol _ <oriol-bugzilla at hotmail.com> wrote:
> Not only `size`. All `get`, `set`, `has`, etc. algorithms in the spec are
> O(n).
>
> But as explained in
> http://www.ecma-international.org/ecma-262/7.0/index.html#sec-map-objects,
>
>> Map object 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.
>> The data structures used in this Map objects specification is only
>> intended to describe the required
>> observable semantics of Map objects. It is not intended to be a viable
>> implementation model.
>
>
> _______________________________________________
> es-discuss mailing list
> es-discuss at mozilla.org
> https://mail.mozilla.org/listinfo/es-discuss
>


More information about the es-discuss mailing list