Javascript ES6 computational/time complexity of collections

by

Right from that very paragraph your linked to:

Set objects must be implemented using [mechanisms] that, on average, provide access times that are sublinear on the number of elements in the collection.

You will find the same sentence for Maps, WeakMaps and WeakSets.

It looks the ECMA spec mandates that the implementations (e.g. Set.prototype.has) are to use a linear time (O(n)) algorithm.

No:

The data structures used in this Set objects specification is only intended to describe the required observable semantics of Set objects. It is not intended to be a viable implementation model.

The observable semantics are mostly related to the predictable iteration order (which still can be implemented efficient and fast). It is indeed expected by the specification that an implementation uses a hash table or something similar with constant access, though trees (with logarithmic access complexity) are allowed as well.

More Related Contents:

  1. How can I write a function that will format a camel cased string to have spaces?
  2. How do I check if an array includes a value in JavaScript?
  3. What do multiple arrow functions mean in JavaScript?
  4. Map vs Object in JavaScript
  5. Create object from class name in JavasScript ECMAScript 6
  6. What do square brackets around a property name in an object literal mean?
  7. What are the precise semantics of block-level functions in ES6?
  8. es6 Map and Set complexity, v8 implementation
  9. Keyword ‘const’ does not make the value immutable. What does it mean?
  10. How to extend a class without having to use super in ES6?
  11. ES6 arrow functions not working on the prototype?
  12. Declaring static constants in ES6 classes?
  13. Concatenating variables and strings in React
  14. Arrow Function in Object Literal [duplicate]
  15. How do I merge two javascript objects together in ES6+?
  16. Destructuring in Node.JS
  17. Is it possible to sort a ES6 map object?
  18. Merge two arrays with alternating values
  19. ES6 Class: access to ‘this’ with ‘addEventListener’ applied on method [duplicate]
  20. this value in JavaScript anonymous function
  21. Maps vs Objects in ES6, When to use?
  22. ES6 functions, arrow functions and ‘this’ in an ES6 class [duplicate]
  23. Extract certain properties from all objects in array
  24. What’s the purpose of allowing duplicate property names?
  25. map function not working in React
  26. How to get the first element of Set in ES6 ( EcmaScript 2015)
  27. Split a Javascript class (ES6) over multiple files?
  28. Binding context when calling ES6 method. How to access object from within method called as callback?
  29. functional way to iterate over range (ES6/7) [duplicate]
  30. ES6 module scope

Leave a Comment