6

This is in regards to a debate I had with an interviewer when I was interviewing at Amazon.

Let's I create an object: 

var Obj = {};
Obj['SomeProperty'] = function ( ) { console.log("Accessed some property"); };
Obj[69] = true;

Is there anything in the JavaScript guaranteeing that when I subsequently access those 2 properties like Obj['SomeProperty'] and Obj[69] the respective values function ( ) { console.log("Accessed some property"); }; and 69 are looked up in O(1) time? I know the access operator [] gives a seasoned programmer the impression that he's dealing with an O(1) lookup structure, but can't it be possible for a JavaScript engine to implement Object in a way such that properties are not looked up in O(1)?

user5648283
  • 5,913
  • 4
  • 22
  • 32
  • Map access is typically O(log(n)) - not sure why you say it is O(1) ? As per https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Working_with_Objects#Objects_and_properties, Objects are referred to as "associative arrays" – Wand Maker Dec 15 '15 at 14:48
  • 2
    A JavaScript engine can implement anything any way it wants, but if you get into that kind of territory then you may as well consider that we all use pre-emptive OS', so nothing of anything very much is really GUARANTEED in relation to real time then, even without considering what might not be guaranteed from running code on someone elses browser! Chances are slim that the JS implementation running your code is so poor that its major features will be suboptimal by an order of complexity though. – Michael Dec 15 '15 at 14:53
  • Agreed with @Michael. Very much this - if you can't trust the platform upon which you stand, then you can't really trust anything. It's definitely possible to build an engine that is as inefficient as possible - in fact, it's possible to build an engine that hangs, meaning it just plain doesn't work, which would satisfy the inefficiency clause. At some point, you just have to assume that it's [turtles all the way down](https://en.wikipedia.org/wiki/Turtles_all_the_way_down). –  Apr 30 '16 at 06:11

1 Answers1

9

Is there anything in the JavaScript guaranteeing that the values are looked up in O(1) time?

No. JavaScript does not give any complexity guarantees whatsoever, except for ES6 collections.

I know the access operator [] gives a seasoned programmer the impression that he's dealing with an O(1) lookup structure

Yes you are, this is a reasonable expectation. Engines employ all kinds of optimisations, from hidden classes over hashmaps to dynamic arrays, to meet these assumptions.

Of course, never forget that JS objects are complex beasts, and accessing a simple property might trigger a getter trap that in turn could do anything.

Can't it be possible for a JavaScript engine to implement Object in a way such that properties are not looked up in O(1)?

Yes, that's possible.

Community
  • 1
  • 1
Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • Can you elaborate on the complexity of the property lookups? I always assumed they were O(log n) (hash table, binary search, that sort of thing). How could O(1) ever be a thing? – Halcyon Dec 15 '15 at 15:25
  • @Halcyon: [Hash tables](https://en.wikipedia.org/wiki/Hash_table) are O(1) amortised. Maybe also see http://stackoverflow.com/q/6586670/1048572. – Bergi Dec 15 '15 at 15:28
  • 1
    @Halcyon: For more details on optimisations beyond simple "hash table" objects see https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Internals/Property_cache, https://developers.google.com/v8/design#prop_access and maybe even http://www.google.com/patents/US8244775 – Bergi Dec 15 '15 at 15:32