61

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,833
  • 17
  • 90
  • 133
  • 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

73

Performance wise, it seems safe to treat them as hashes. Historically there were a lot of articles that said not to trust this. From what I've experienced there are definitely cases where an Object may be more ergonomic than Map.

Benchmarked here - https://jsfiddle.net/soparrissays/Lt0znmxw/

You can see that that regardless of the size of the object each CRUD operation is able to perform around the same number of ops/sec indicating that each operation is O(1). The following run is in Chrome:

100 keys (create) x 13,326,160 ops/sec ±9.42% (34 runs sampled)
1k Keys (create) x 13,757,260 ops/sec ±9.15% (34 runs sampled)
100k Keys (create) x 12,434,691 ops/sec ±7.91% (34 runs sampled)
1M Keys (create) x 12,678,435 ops/sec ±13.12% (38 runs sampled)
100 keys (read) x 80,126,804 ops/sec ±0.24% (101 runs sampled)
1k Keys (read) x 80,333,384 ops/sec ±0.14% (102 runs sampled)
100k Keys (read) x 80,154,201 ops/sec ±0.17% (103 runs sampled)
1M Keys (read) x 80,259,463 ops/sec ±0.13% (98 runs sampled)
100 keys (update) x 71,771,379 ops/sec ±0.19% (100 runs sampled)
1k Keys (update) x 71,851,829 ops/sec ±0.13% (103 runs sampled)
100k Keys (update) x 71,804,254 ops/sec ±0.13% (103 runs sampled)
1M Keys (update) x 71,770,332 ops/sec ±0.13% (98 runs sampled)
100 keys (destroy) x 22,673,628 ops/sec ±0.52% (100 runs sampled)
1k Keys (destroy) x 20,852,449 ops/sec ±0.60% (93 runs sampled)
100k Keys (destroy) x 21,137,940 ops/sec ±0.86% (97 runs sampled)
1M Keys (destroy) x 21,436,091 ops/sec ±0.56% (96 runs sampled)

In the past, I had seen other browsers behave similarly.

2023 update

I should have just read the source code - If I'm reading this right, it's a map with more functionality around it https://github.com/v8/v8/blob/2b79cfd81f6acdfec29661ce2b39d60f4a45b14f/src/objects/js-objects.cc#L2391

MaybeHandle<JSObject> JSObject::New(Handle<JSFunction> constructor,
                                    Handle<JSReceiver> new_target,
                                    Handle<AllocationSite> site) {
  // If called through new, new.target can be:
  // - a subclass of constructor,
  // - a proxy wrapper around constructor, or
  // - the constructor itself.
  // If called through Reflect.construct, it's guaranteed to be a constructor.
  Isolate* const isolate = constructor->GetIsolate();
  DCHECK(constructor->IsConstructor());
  DCHECK(new_target->IsConstructor());
  DCHECK(!constructor->has_initial_map() ||
         !InstanceTypeChecker::IsJSFunction(
             constructor->initial_map().instance_type()));

  Handle<Map> initial_map;
  ASSIGN_RETURN_ON_EXCEPTION(
      isolate, initial_map,
      JSFunction::GetDerivedMap(isolate, constructor, new_target), JSObject);
  constexpr int initial_capacity = V8_ENABLE_SWISS_NAME_DICTIONARY_BOOL
                                       ? SwissNameDictionary::kInitialCapacity
                                       : NameDictionary::kInitialCapacity;
  Handle<JSObject> result = isolate->factory()->NewFastOrSlowJSObjectFromMap(
      initial_map, initial_capacity, AllocationType::kYoung, site);
  return result;
}

I'll speculate that Map may buy you some performance, but its clear objects are plenty fast, and their properties appear to belong to a hash under the hood. So of course choose the right tool for the job. If you need the all the tooling built up around Objects, its still safe to use them clearly!

Parris
  • 17,833
  • 17
  • 90
  • 133
  • 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
  • Could you please update the links. I am getting 500 server errors – Sean Nov 21 '22 at 11:39
  • @Sean updated - jsperf died at the some point. It's interesting revisiting this question 11 years later! – Parris Apr 07 '23 at 01:05
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
  • 354,903
  • 100
  • 647
  • 710
  • 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
  • 1
    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
-3

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

Sarwar Sateer
  • 395
  • 3
  • 16
  • 5
    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