Discuss
  • Maps with object keys

Maps with object keys

# Benjamin (Inglor) Gruenbaum (11 years ago)

I'm trying to work with ES6 Map objects and I ran into an interesting problem.

I want to index/group based on several key values. Let's say my original data is something like:

 [{x:3,y:5,z:3},{x:3,y:4,z:4},{x:3,y:4,z:7},{x:3,y:1,z:1},{x:3,y:5,z:4}]

I want to group it based on the x and y property values, so I want the result to look something like:

    {x:3,y:5} ==>  {x:3,y:5,z:3},{x:3,y:5,z:4}
    {x:3,y:4} ==>  {x:3,y:4,z:4},{x:3,y:4,z:7}
    {x:3,y:1} ==>  {x:3,y:1,z:1}

However, as the docs and draft say maps detect existence ( Map.prototype.has ( key )) for object the same way === works for objects (specified in SameValueZero(x, y)).

I really don't see how to solve this other than implementing my own form of hashing for these specific objects and 'rolling my own' logic here (instead of working directly with Maps).

For comparison - in Python for example I'd use a dictionary with tuple keys.

So I'm wondering, what's the point of being able to use object keys in Map objects if the equality check performed is reference equality?

I feel like I'm either missing something obvious here or we have a usability issue on our hands.

Benjamin

(Also asked in SO stackoverflow.com/questions/21838436/map-using-tuples-or-objects )

# Bradley Meck (11 years ago)

I understand the capability of python, but that is done through comprehensions that do not relate to the mapping of key to value. In ES6 the syntax comes out to:

let tuple = {x:3,y:5}
[for (value of map.entries()) if
(Object.keys(tuple).every((tupleKey)=>tuple[tupleKey] == value[tupleKey]))

value]

A quick comparator function for tuple like objects would be more clear than comprehension that does not relate to the mapping of key to value. Notice how the keys of map are never used in the comprehension.

# Benjamin (Inglor) Gruenbaum (11 years ago)

My issue here is that I want to index on "complex" values. I was under the impression ES6 maps solve amongst others the problem that with objects - keys are only strings.

I want to index on 2 (or 100) properties - in this example the x and y values. I don't want to iterate the whole collection and all the keys every time I check for existence - that's very inefficient.

Moreover, I don't want to write a for loop over the entries every time I check for existence - if I wanted that I'd just use an array. Also note, we're talking about the keys of the map and not the values.

BTW in Python (which I reiterate is just an example) it's done via a hash function ( python-git/python/blob/master/Objects/tupleobject.c#L290) that's not the issue though.

# C. Scott Ananian (11 years ago)

It is straightforward to implement a hash function based map as a subclass of Map. Something like:

var HashMap = function() { this._map = new Map(); };
HashMap.set = function(key, value) {
  var hash = key.hashCode();
  var list = this._map.get(hash);
  if (!list) { list = []; this._map.set(hash, list); }
  for (var i=0; i<list.length; i++) {
     if (list[i].key.equals(key)) {
        list[i].value = value;
        return;
     }
  }
  list[i].push({key: key, value: value });
};
// etc

(For simplicity I used delegation above, rather than a subclass, and I used ES5 syntax.)

Note that the above implementation makes a number of assumptions which the ES6 designers decided were not appropriate to hardcode into the language:

  1. All object used as keys must implement hashCode and equals with appropriate semantics.
  2. Hash code collisions cause the map to revert to linear search. (Alternatively you could implement a different variant of hashtable chaining.)

ES6 includes only the basic Map primitive, on top of which you can build the infinite variety of different Map variants.

I expect that we will begin to see helper libraries built on top of ES6 primitives. As an example, I wrote prfun to provide Promise-related helpers on top of the (similarly bare-bones) ES6 Promise. Presumably we'll eventually see some library with a name like javamap to provide java-style hashCode/equals maps on top of ES6 Map for those who want that.

# David Bruant (11 years ago)

Le 17/02/2014 22:55, Benjamin (Inglor) Gruenbaum a écrit :

My issue here is that I want to index on "complex" values. I was under the impression ES6 maps solve amongst others the problem that with objects - keys are only strings.

With maps, all native types (string, number, boolean, undefined, null, object) can be keys. For complex values, funnel your values down to one of these (by hashing or serializing or whatever fits your need). It's easy enough to write and enough use case specific to justify not being part of the language.

# Jason Orendorff (11 years ago)

On Mon, Feb 17, 2014 at 3:09 PM, Benjamin (Inglor) Gruenbaum <inglor at gmail.com> wrote:

I'm trying to work with ES6 Map objects and I ran into an interesting problem.

Yes! Well done.

We've noticed this too, and considered (a) allowing objects to provide their own hash and equals operations, as in Java and Python; (b) allowing the Map user to specify hash and equals operations for the Map at construction time. These were rejected partly because both ideas would make Map behavior observably nondeterministic, or else overspecify. Also because object hash codes would be exposed to users, and ensuring that those do not leak any information about object addresses would likely make them slow.

The solution that prevailed is (c) introduce value types in ES7. With value types, you'll be able to declare an aggregate value type, much like a Python namedtuple, to use as your Map key. Values of that type can be compared for equality with ===, like Python tuples, and Map will work accordingly.

Until value types are spec'd and implemented, the other workarounds already mentioned in this thread will have to do, I'm afraid.

# Benjamin (Inglor) Gruenbaum (11 years ago)

Thanks, I was starting to feel like I wasn't explaining my issue very well given the other replies. I'm glad we agree this is not something user-code should have to shim for language level collections.

I'm working on several projects that perform statistical analysis and I wanted to stick to JavaScript, this makes it really hard to do so. It effectively renders Maps useless for me exept for readability purposes. Also, thanks for the straight up 'this is still a problem now' - it probably saved me a considerable amount of time.

Value types do sound like a better solution than throwing equals and hash on every object, it is conceptually similar to the solution I've got so far (using a flyweight to enforce uniqueness and generate 'value objects'). (Of course the current solution has memory issues which I need to be careful about - but I hope I'll manage)

I do think there might be a problem with value types (or rather, value objects) for key though - if I followed correctly, value types do not allow you to specify === and !== yourself, they are a recursive structural equality test which limits your ability to ignore properties you do not care about. For example, getting points that are unique points on the R2 (x,y plane) by throwing R3 points (x,y,z) into a set with "x,y equality" and then extracting them. I'm not sure if this was discussed or if it's a big enough issue but I think it's worth talking about.

Thanks, Benjamin