60

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?

Parris
  • 17,121
  • 16
  • 86
  • 129
  • If you want to lookup for your object by some field why do you care about adding and removing? ID is not supposed to change after object instanciation. – aviad Sep 03 '12 at 03:42
  • @aviad I suppose adding and removing isn't as big of deal. I don't see a use case for more than a few million pairs, and even that is most likely ridiculous for this use case in particular. Then again, people may want to use this specific function for other things. I'd like to provide some guidance. – Parris Sep 03 '12 at 03:52
  • _"use the member variables in a object as key value pairs"_ - That's pretty much what the "member variables" are, isn't it? – nnnnnn Sep 03 '12 at 04:07
  • @nnnnnn well I haven't necessarily seen any guarantees made about the performance. They are key value pairs, but you can say that about any variable in any language. – Parris Sep 04 '12 at 00:15
  • _"They are key value pairs, but you can say that about any variable in any language"_ - No you can't: in most languages strings, numbers and booleans are just values with no associated keys. My point was that a JS object's job is to hold a collection of key/value pairs (where the value might be a reference to a function or other object). I realise this doesn't help you with your question about performance. – nnnnnn Sep 04 '12 at 03:46

3 Answers3

70

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.

Parris
  • 17,121
  • 16
  • 86
  • 129
  • 3
    It may not affect your statistics, but in the teardown function, `n` is undefined. You specified a global but jsPerf has wrapped the code in a function. So the function (if called) is throwing an error that seems to be ignored by jsPerf. – RobG Sep 04 '12 at 03:38
  • @RobG thanks for that catch. I made one update to: http://jsperf.com/objects-as-hashes-100k/2 It didn't seem to affect performance that much. Actually it was slightly faster in all ops. Constant time change. I think I'll just leave it for now. Although, I should definitely fix that. – Parris Sep 04 '12 at 19:04
  • So the summary is that it IS constant time for all CRUD operations ? – temporary_user_name Dec 22 '18 at 09:08
  • @temporary_user_name YES! see the below answer from Matt Ball. I don't know why this answer is the top one it doesn't really get to the meat of the question. – ICW Jul 03 '19 at 22:49
  • 1
    @yunggun at the time this post was created there was no guarantee that this was the case. In fact, all articles that existed out there said "objects are not hashes stop treating them like they are". To prove that this was the case, I ran some perf tests. It showed that it was indeed true that everything was constant time. There is no specification that says this must be true (at least none that I could find at the time). Objects are objects not dictionaries, it just so happens that the common implementation in JS is that they are hashes. – Parris Jul 11 '19 at 19:01
  • More over - I updated it to make it more useful. It was indeed overly wordy. – Parris Jul 11 '19 at 19:16
  • @Parris Good point - you proved that objects CRUD constant time which we had no guarantee of previously. Which means, we actually SHOULD be able to treat them like hashes, right? running counter to what the articles of the time said – ICW Jul 12 '19 at 15:44
  • @yunggun yup, you should be able to treat them as hashes. I think they're used that way very widely. While I am uncertain if there is a specification around it I think it would be a very crazy regression if various JS implementations changed this behavior. It might make that engine the slowest JS implementation. Basically, in practice, yes it's a hash and should always be a hash. – Parris Jul 12 '19 at 21:52
13

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?

Matt Ball
  • 344,413
  • 96
  • 627
  • 693
  • No performance issues yet. I'll run a larger test soon, and as @David mentioned in the comments I'll make a benchmark. I suppose part of this question was just curiosity. I make the assumption that since it functions like a hash that it is a hash. Wasn't totally sure though. Also, I am not certain if there are upper bounds on how many member variables you could possibly have. – Parris Sep 03 '12 at 03:46
  • 4
    By the pigeonhole principle, there is a finite upper limit on the number of member variables you can have before degrading performance (for instance, due to hash collisions). However, unless you're deliberately picking pathologically bad object keys, and using a large number of them, you're just not going to see this degradation. – Matt Ball Sep 03 '12 at 03:48
  • I can imagine implementations might not necessarily represent Javascript objects as hashtables - JScript.NET, for example, used the CLR's typesystem, which meant that each field was accessed by a memory offset rather than a hashtable lookup, presumably per-object modifications were made using reflection or at least a reallocation. – Dai Sep 03 '12 at 03:50
  • Thanks! I'll accept this answer (at least for now, unless someone else has more specifics). I believe @David is right in suggesting some performance analysis. I'll comment back if I have any interesting finds across environments. – Parris Sep 03 '12 at 03:57
  • Don't forget to post your results in this question - I'm personally interested in your findings! – Dai Sep 03 '12 at 03:58
  • 1
    @MattBall—ECMAScript objects are specified to be simple name/value pairs, the term "hash" may well infer much more functionality to some. Perhaps javascript objects are implemented as hashes underneath, who knows? David's comment is fair — test it and see. It may be that different aspects have different performance in different browsers. Testing should include a *hasOwnProperty* filter too if that is relevant to the OP. – RobG Sep 03 '12 at 04:20
  • 2
    I posted my results from the analysis! Thanks again! – Parris Sep 03 '12 at 23:32
  • One should be careful with a statement like "JavaScript objects are hashes". They are not a hash table known from many other programming languages (e.g. `dict` in python). In case keys are coming from untrusted input, one should definitely give http://www.devthought.com/2012/01/18/an-object-is-not-a-hash a read. – Dr. Jan-Philip Gehrcke Nov 10 '14 at 18:32
  • Thank you... This answer is infinitely more useful than the top answer. Conceptually, when I think of hash tables I think constant time lookups and inserts, although I know there is more to the story. All I needed to know was whether these would actually be constant time. This answer answers that, unlike the top answer. @Jan-PhilipGehrcke They're not hashes technically, but they can always effectively function as one, since they provide constant CRUD operations. – ICW Jul 03 '19 at 22:48
-1

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

Sateer
  • 306
  • 2
  • 14
  • 3
    This isn't a good explanation... You could have any data structure under the hood, just because the interface is key/value based does not guarantee O(1) lookup – Cody E May 12 '21 at 22:43