Complexity of accessing data in an object

user_3784762 0
Viewed 9304

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?
node.js time-complexity json javascript
2 Answers

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:

user_48587770
Related