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

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?

Answers:

Answer

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.

Answer

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?

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.