JavaScript Objects as Hashes? Is the complexity greater than O(1)?

JavascriptPerformance

Javascript Problem Overview


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?

Javascript Solutions


Solution 1 - Javascript

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.

Solution 2 - Javascript

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?

Solution 3 - Javascript

Objects in JavaScript are an example of a Hash Table because object data is represented as keys & values.

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionParrisView Question on Stackoverflow
Solution 1 - JavascriptParrisView Answer on Stackoverflow
Solution 2 - JavascriptMatt BallView Answer on Stackoverflow
Solution 3 - JavascriptSateerView Answer on Stackoverflow