21

In some of the projects I'm working on as part of my day job, I need to access data in very large JS objects (on the order of thousands of key-value pairs). I'm trying to improve the efficiency of my code, so I came up with a few questions:

  1. What is the runtime complexity of JS when accessing a field in such an object? My initial hunch is that it's O(n)
  2. Is there a difference when accessing through dot notation or bracket notation? (e.g. obj.field vs obj[field])
  3. I'm guessing there is a different answer for different runtime engines - is there a place where I can see the difference between them?
DanielR
  • 556
  • 2
  • 5
  • 19
  • 1
    On V8 also depends on how the object is threatened. If `delete` is used, the object is converted internally to another type which is way less performant, for example. Take a look into `Map`. Don't know performances but maybe is faster (In your situation, I mean). – Jorge Fuentes González Jul 23 '17 at 15:46

2 Answers2

40

Javascript objects are actually Hashes, so the complexity is O(1) for all engines.

obj.field is an alias for obj['field'], so they have the same performances.

You can find some JS hashes performance tests here, unfortunately only for your browser engine.

Marco Vanetti
  • 448
  • 5
  • 6
6

In the worst case an JS object is represented as a hash table and has the same lookup complexity: O(1) on average but O(n) at worst. The hash table implementation is your case I guess, because you have so many items in the object. There is no difference how you access a property, obj.field and obj['filed'] are the same.

It's also worth to mention that the complexity isn't always equal to complexity of a hash table lookup, it's faster in much cases. Modern JS engines use techniques called hidden classes and inline caching to speed up the lookup. It's a pretty big question, how these techniques work, I've explained it in another answer.

Some relative resources:

Valeriy Katkov
  • 33,616
  • 20
  • 100
  • 123
  • If it implemented with Hast Table. The worst case of time complexity would be O(n) or at least O(log n). How can it be O(1)? – tsh Mar 09 '21 at 01:22
  • @tsh Indeed, I put it wrong, thanks for correcting me! I've updated the answer. – Valeriy Katkov Mar 09 '21 at 08:37