Menu
For some algorithm I was writing recently I thought that a hash would be excellent. I thought that I could probably just use the member variables in an object as key value pairs. I am not sure if this is optimal since I don't really know what is going on behind the scenes. I also suppose that V8 does it differently than other environments. I do however imagine that looking up member variables would be pretty quick (hopefully)?
That all said, I am wondering if the run time complexity of writing, reading, creating and removing member variables in JavaScript objects are all O(1). If there are differences in environment (v8 vs others) what are they?
463
Objects are stored in the for of a key/value pair {key: value}. JavaScript objects are implemented using Hash tables under the hood. One thing about Hashing table is that — Hash tables Retrieve method have O(1), constant time complexity because of the use of a hashing function.
What is the time complexity? The methods an array uses to search for items has a linear time complexity of O(N). In other words, the run-time increases at the same rate as the size of the data increases.
Yes they are hashes. The implementation is different across browsers. Despite many articles that would claim that objects are not hashes they very much behave like hashes, and therefore could be used as such.
I had to prove this by running performance tests:
The way to read these tests is if there is no performance difference in ops/sec when the size of object grows then that means objects are hashes. The defining characteristic of a hash is that the complexity of each operation is O(1) regardless of it being faster or slower in comparison to other operations.
Tests:
http://jsperf.com/objectsashashes/2 (100 keys)
http://jsperf.com/objectsashashes/3 (100k keys)
http://jsperf.com/objectsashashes/ (1 million keys)
http://jsperf.com/objects-as-hashes-300-mil (10m keys)
Note: Each browser is faster/slower at different operations. This seems to change between releases and year to year.
135
JavaScript objects are hashes. I cannot imagine any sane implementation that would not provide constant-time CRUD operations on object properties.
Are you seeing specific performance issues with this approach?
36
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
