-1

According to my prior knowledge, JavaScript objects are basically hash maps (hash tables) which means -> set and get are done in O(1)

Lately I came across this article - https://javascript.info/object which points out the following example:

let codes = {
"49": "Germany",
"41": "Switzerland",
"44": "Great Britain",
// ..,
"1": "USA"
}

for (let code in codes) {
  console.log(code); // 1, 41, 44, 49
}

And the official MDN site:

const anObj = { 100: 'a', 2: 'b', 7: 'c' };
console.log(Object.entries(anObj)); // [ ['2', 'b'], ['7', 'c'], ['100', 'a'] ]

The explenation I came across is:

So what exactly is going on?

Here are the ordering rules: Numbers are ordered first, and they are ordered within themselves from smallest to largest as long as they are >=0 (see below for more details) Strings come second, and they are ordered within themselves by insertion order Symbols come last, and they are ordered within themselves by insertion order (note that we didn't use symbols in this example)

So I'm pretty confused here, and my question is:

When does the object keys ordering happens?

In case the object sort the keys itself, it means that the insert time is not O(1). Because every time I insert a new value, all the keys should be reordered.

The only case I think this behaviour could happens and keep the O(1) rule, is that the ordering happens only on display or in the use of Object.keys function.

Anyone got an idea when does the ordering process happens?

VLAZ
  • 26,331
  • 9
  • 49
  • 67
Eden Katabi
  • 271
  • 1
  • 2
  • 9
  • 3
    https://stackoverflow.com/a/5525820/3840840 – Sebastian Brosch Jun 28 '21 at 12:49
  • 1
    This is old (2017) but gives some good idea of the [implementation in V8](https://v8.dev/blog/fast-properties) – pilchard Jun 28 '21 at 12:51
  • 2
    What you're asking for would be implementation dependent. The standard just defines the observable behaviour. Different engines can implement it differently. This could only happen at iteration time, instead of insertion time. It's also entirely possible that insertion is *not* `O(1)`. Or iteration is not `O(n)`. – VLAZ Jun 28 '21 at 12:57

2 Answers2

0

You are using object literal to create the map. This is the historical way to create the map as there was no built-in alternative present in old days in the javascript world.

However, object literal and map have got the difference in the latest development of js engine. MDN describes this:-

Although the keys of an ordinary Object are ordered now, this was not always the case, and the order is complex. As a result, it's best not to rely on property order. The order was first defined for own properties only in ECMAScript 2015; ECMAScript 2020 defines order for inherited properties as well. See the OrdinaryOwnPropertyKeys and EnumerateObjectProperties abstract specification operations. But note that no single mechanism iterates all of an object's properties; the various mechanisms each include different subsets of properties. (for-in includes only enumerable string-keyed properties; Object.keys includes only own, enumerable, string-keyed properties; Object.getOwnPropertyNames includes own, string-keyed properties even if non-enumerable; Object.getOwnPropertySymbols does the same for just Symbol-keyed properties, etc.)

Reference:- https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

Manish Kumar
  • 595
  • 2
  • 15
  • I don't see how this answers the question of *when* the ordering happens. – VLAZ Jun 28 '21 at 12:58
  • @VLAZ, I have kept the reference text from the MDN. This describes the ordering process. It linked with the iterable/enumerable implementation. Please go through the link for more details. – Manish Kumar Jun 28 '21 at 13:06
0

So basicially after reading the v8 docs, and reviewing @VLAZ answer I think I found a decent answer. And it contains 2 parts.

First, like VLAZ mentioned it depends on the compiler. The implementarion can be different on differemt js compilers.

Second, in the V8 compiler, the ordering process happens only on the iteration amd not on the storing. Which means, the object has a "dictionary like" behaviour and it doesn't order the properties on set/get.

When you want to iterate/display the keys. The compiler arrange them based on some rules and return the keys.

Eden Katabi
  • 271
  • 1
  • 2
  • 9