Map using tuples or objects

Question

I'm trying to use the new (ES6) Map objects in order to represent a map between properties and a value.

I have objects in a form similar to:

 {key1:value1_1,key2:value2_1},..... {key1:value1_N,key2:value2_N}

I want to group them based on both their key1 and key2 value.

For example, I want to be able to group the following by x and y:

[{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}]

And obtain a Map containing:

{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}

In Python, I'd use tuples as dictionary keys. ES6 map allow arbitrary objects as keys but use the standard equality algorithm (===) so objects are only equal by reference from what I can tell.

How can I accomplish this sort of grouping using ES6 maps? Alternatively, a solution using normal JS objects if there is an elegant way I overlooked.

I'd rather not use an external collections library - but if there is a better solution using one I'm interested in learning about it too.

Ewall

Answer 1

Ok, I've raised the issue on esdiscuss now and I got an answer from Mozilla's Jason Orendorff:

1. This is a problem with ES6 maps.
2. The solution will come in the form of ES7 value objects for keys instead of objects.
3. It was considered before to let people specify .equals and .hashCode but it was rejected in favor of value objects. (for good reasons in my opinion).
4. The only solution as of now is to roll your own collection.

A basic such collection (concept, don't use in production code) was offered by Bradley on the ESDiscuss thread and might look something like this:

function HashMap(hash) {
  var map = new Map;
  var _set = map.set;
  var _get = map.get;
  var _has = map.has;
  var _delete = map.delete;
  map.set = function (k,v) {
    return _set.call(map, hash(k), v);
  }
  map.get = function (k) {
    return _get.call(map, hash(k));
  }
  map.has = function (k) {
    return _has.call(map, hash(k));
  }
  map.delete = function (k) {
    return _delete.call(map, hash(k));
  }
  return map;
}

function TupleMap() {
  return new HashMap(function (tuple) {
    var keys = Object.keys(tuple).sort();
    return keys.map(function (tupleKey) { // hash based on JSON stringification
               return JSON.stringify(tupleKey) + JSON.stringify(tuple[tupleKey]);
    }).join('\n');
    return hashed;
  });
}

A better solution is to use something like MontageJS/Collections which allows for specification of hash/equals functions.

You can see the API docs here.

Ewall

Answer 2

It doesn’t seem conveniently possible. What can you do? Something horrible, as always.

let tuple = (function() {
    let map = new Map();

    function tuple() {
        let current = map;
        let args = Object.freeze(Array.prototype.slice.call(arguments));

        for (let item of args) {
            if (current.has(item)) {
                current = current.get(item);
            } else {
                let next = new Map();
                current.set(item, next);
                current = next;
            }
        }

        if (!current.final) {
            current.final = args;
        }

        return current.final;
    }

    return tuple;
})();

And voilà.

let m = new Map();
m.set(tuple(3, 5), [tuple(3, 5, 3), tuple(3, 5, 4)]);
m.get(tuple(3, 5)); // [[3, 5, 3], [3, 5, 4]]

Rastus

I’m not sure whether it’s possible to also abuse WeakMap to make this memory-efficient. Probably not. – Rastus

Did you just implement a tuple flyweight for this here :O . +1 for creativity but I really think this should be solved at the language level. – Ewall

Answer 3

More years have passed and this is still an issue with JavaScript. I improved on Jamesernator’s approach and created the package https://www.npmjs.com/package/collections-deep-equal. Now you can get what you want:

import { MapDeepEqual, SetDeepEqual } from "collections-deep-equal";

const object = { name: "Leandro", age: 29 };
const deepEqualObject = { name: "Leandro", age: 29 };

const mapDeepEqual = new MapDeepEqual();
mapDeepEqual.set(object, "value");
assert(mapDeepEqual.get(object) === "value");
assert(mapDeepEqual.get(deepEqualObject) === "value");

const setDeepEqual = new SetDeepEqual();
setDeepEqual.add(object);
assert(setDeepEqual.has(object));
assert(setDeepEqual.has(deepEqualObject));

Heinie

Answer 4

Benjamin's answer doesn't work for all objects, as it relies on JSON.stringify, which cannot handle circular objects and can map different objects to the same string. Minitech's answer can create huge trees of nested maps, which I suspect are both memory and CPU inefficient, especially for long tuples, as it has to create a map for each element in the tuple.

If you know that your tuples only contain numbers, then the best solution is to use [x,y].join(',') as the key. If you want to use tuples containing arbitrary objects as keys, you can still use this method, but have to map the objects to unique identifiers first. In the code below I generate these identifiers lazily using get_object_id, which stores the generated ids in an internal map. I can then generate keys for tuples by concatenating those ids. (See code at the bottom of this answer.)

The tuple method can then be used to hash tuples of objects to a string that can be used as the key in a map. This uses object equivalence:

x={}; y={}; 
tuple(x,y) == tuple(x,y) // yields true
tuple(x,x) == tuple(y,y) // yields false
tuple(x,y) == tuple(y,x) // yields false

If you're certain that your tuples will only contain objects (i.e. not null, numbers or strings), then you can use a WeakMap in get_object_id, such that get_object_id and tuple won't leak objects that are passed as argument to them.

var get_object_id = (function() {
  var generated_ids = 1;
  var map = new Map();
  return get_object_id;
  function get_object_id(obj) {
    if (map.has(obj)) {
      return map.get(obj);
    } else {
      var r = generated_ids++;
      map.set(obj, r);
      return r;
    }
  }
})();

function tuple() {
  return Array.prototype.map.call(arguments, get_object_id).join(',');
}

// Test
var data = [{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}];
var map = new Map();
for (var i=0; i<data.length; i++) {
  var p = data[i];
  var t = tuple(p.x,p.y);
  if (!map.has(t)) map.set(t,[]);
  map.get(t).push(p);
}

function test(p) {
  document.writeln((JSON.stringify(p)+' ==> ' + 
    JSON.stringify(map.get(tuple(p.x,p.y)))).replace(/"/g,''));
}

document.writeln('<pre>');
test({x:3,y:5});
test({x:3,y:4});
test({x:3,y:1});
document.writeln('</pre>');

Assignat

Please explain why you think my sentence about weakmaps is false. Also, if your answer can do without JSON.stringify, please update your answer to explain how. – Assignat

Using a WeakMap ensures that objects used in tuples remain eligible for garbage collection. I.e. if the WeakMap is the only thing that is referring an object, the garbage collector can destroy that object (and also remove it from the WeakMap). Thereby it avoids a memory leak. – Assignat

The objects are used as keys in the WeakMap, so it's fine if they're eligible for garbage collection. The map is used to extend the objects with a unique identifier, without actually changing the object. -- To replace JSON.stringify in your answer with another hash function, you also need to create such other hash function, which is difficult. My tuple() is such other hash function, with different (better) properties than JSON.stringify. Aside from the hash function, our answers are the same: map the tuple to something you can use as a key. – Assignat

No it's using WeakMaps exactly for what they're designed for. And yes, I know that for your question you should use .join(',') as the hash function. Though readers of your question might have different requirements. Your solution doesn't work for circular objects, or for objects that are mapped to the same string by JSON.stringify. And it is inefficient for complex objects. – Assignat

Let us continue this discussion in chat. – Assignat

Answer 5

While this question is quite old, value objects are still not an existing thing in JavaScript (so people might still be interested) so I decided to write a simple library to accomplish similar behaviour for arrays as keys in maps (repo here: https://github.com/Jamesernator/es6-array-map). The library is designed to be basically identical to map in usage except arrays are compared element-wise instead of by identity.

Usage:

var map = new ArrayMap();
map.set([1,2,3], 12);
map.get([1,2,3]); // 12

map.set(['cats', 'hats'], {potatoes: 20});
map.get(['cats', 'hats']); // {potatoes: 20}

Warning: The library however treats key elements by identity so the following doesn't work:

var map = new ArrayMap();
map.set([{x: 3, y: 5}], {x:3, y:5, z:10});
map.get([{x: 3, y: 5}]); // undefined as objects within the list are
                         // treated by identity

But as long as you can serialize the data into arrays of primitives you can use ArrayMap as follows:

var serialize = function(point) {
    return [point.x, point.y];
};
var map = new ArrayMap(null, serialize);
map.set({x: 10, y: 20}, {x: 10, y: 20, z: 30});
map.get({x: 10, y: 20}); // {x: 10, y: 20, z: 30}

Blackett

Answer 6

Another code for tuple.

const tuple = (() => {
  const tpls = [];
  return (...args) => {
    let val = tpls.find(tpl => tpl.length === args.length && tpl.every((v,i) => v === args[i]));
    if(val == null) {
      val = Object.freeze([...args]);
      tpls.push(val);
    }
    return val;
  };
})();

//Usage
console.assert(tuple(1, 2, 3, foo) === tuple(1, 2, 3, foo));
//But as bcmpinc says, different objects are not equal.
console.assert(tuple({}) !== tuple({}));

function foo() {}

const map = new Map();
map.set(tuple(1, 2, 3, foo), 'abc');
map.set(tuple(1, 2, 3, foo), 'zzz');
console.log(map.get(tuple(1, 2, 3, foo)));  // --> 'zzz'

Roose

Answer 7

You can use the keyalesce, which returns the same key for the same sequence of values, to solve this problem.

const keyOf = ({ x, y }) => keyalesce([x, y]) 

const map = new Map()
const values = [
  { 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 },
]
for (const value of values) {
  const key = keyOf(value)

  let group = map.get(key)
  if (!group) {
    group = []
    map.set(key, group)
  }
  
  group.push(value)
}

console.log(map.get(keyOf({ x: 3, y: 5 })))
//=> [ { x: 3, y: 5, z: 3 }, { x: 3, y: 5, z: 4 } ]

See this post for how keyalesce works internally.

Corral