Coming from Java, Javascript object reminds me of HashMap in Java.
Javascript:
var myObject = {
firstName: "Foo",
lastName: "Bar",
email: "[email protected]"
};
Java:
HashMap<String, String> myHashMap = new HashMap<String, String>();
myHashMap.put("firstName", "Foo");
myHashMap.put("lastName", "Bar");
myHashMap.put("email", "[email protected]");
In Java HashMap, it uses the hashcode() function of the key to determine the bucket location (entries) for storage, and retrieval. Majority of the time, for basic operations such as put() and get(), the performance is constant time, until a hash collision occurs which becomes O(n) for these basic operations because it forms a linked list in order to store the collided entries.
My question is:
Thanks!
-Big O Notation: It's the way of describing the relationship between the input of a function as it grows and how that changes the runtime of that function, it allows us to talk formally about how the runtime of an algorithm grows as the input grows.
Big O Notation is used in computer science to analyse the performance of an algorithm (an algorithm is just another name for a function – a set of instructions). Big O specifically looks at the worst-case scenario of an algorithm – looking at the big picture.
For objects with thousands of named properties, our implementation indeed uses a hash table (as the question guessed), and that means complexity of Object. keys() is O(n log n).
hasOwnProperty() should be O(1) , as it is a key lookup, but it will be implementation specific.
Javascript looks like it stores things in a map, but that's typically not the case. You can access most properties of an object as if they were an index in a map, and assign new properties at runtime, but the backing code is much faster and more complicated than just using a map.
There's nothing requiring VMs not to use a map, but most try to detect the structure of the object and create an efficient in-memory representation for that structure. This can lead to a lot of optimizations (and deopts) while the program is running, and is a very complicated situation.
This blog post, linked in the question comments by @Zirak, has a quite good discussion of the common structures and when VMs may switch from a struct to a map. It can often seem unpredictable, but is largely based on a set of heuristics within the VM and how many different objects it believes it has seen. That is largely related to the properties (and their types) of return values, and tends to be centered around each function (especially constructor functions).
There are a few questions and articles that dig into the details (but are hopefully still understandable without a ton of background):
The performance varies greatly, based on the above. Worst case should be a map access, best case is a direct memory access (perhaps even a deref).
There are a large number of scenarios that can have performance impacts, especially given how the JITter and VM will create and destroy hidden classes at runtime, as they see new variations on an object. Suddenly encountering a new variant of an object that was presumed to be monomorphic before can cause the VM to switch back to a less-optimal representation and stop treating the object as an in-memory struct, but the logic around that is pretty complicated and well-covered in this blog post.
You can help by making sure objects created from the same constructor tend to have very similar structures, and making things as predictable as possible (good for you, maintenance, and the VM). Having known properties for each object, set types for those properties, and creating objects from constructors when you can should let you hit most of the available optimizations and have some awfully quick code.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With