CODEWITHSUNDEEP
javascriptdictionaryecmascript-6
Sirko
Sirko

Reputation: 74076

Define a custom hash() method for use with ES6 maps

To illustrate the problem, consider the following simple object

function Key( val ) {
  this._val = val;
}

Now I create a ES6 Map instance and feed one entry into it like this

var map = new Map(),
    key1 = new Key( 'key' );

map.set( key1, 'some value' );

console.log( 'key1: ', map.has( key1 ) );
// key1:  true

So far everything is fine. The challenge, however, comes up, if I create a nearly identical object key2 like this

var key2 = new Key( 'key' );

So basically both keys are identical, but obviously key2 is not part of the map

console.log( 'key2: ', map.has( key2 ) );
// key2:  false

JavaScript uses the object references as a key here, so the two separate objects will not point towards the same value.

What I would like to do now is, to add something like a hash() method to key's prototype, so that both object would point to the same key. Is something like this possible?

I know, that there would be a way to circumvent the problem using a factory pattern for the Key generation together with some caching. However, this results in a lot of problem regarding immutability of the objects and the cache preventing old objects from being garbage collected. So I think that is not really an option.

Upvotes: 15

Views: 7276

Answers (2)

Mattias Martens
Mattias Martens

Reputation: 1647

I've created a class called CanonMap in my library big-m to encapsulate mapping by hash instead of reference.

By default, it works with tuples, Dates, and simple objects:

const { CanonMap } = "big-m";

const myMap = new CanonMap();
myMap.set(
  ["Farooq", "867-5309"],
  36.59
);

myMap.get(
  ["Farooq", "867-5309"]
) === 36.59;

myMap.set(
  {name: "Farooq", number: "867-5309"},
  36.59
);

myMap.get(
  {number: "867-5309", name: "Farooq"} // Insensitive to key ordering
) === 36.59;

myMap.set(new Date(2012, 6, 5), "Tuesday");
myMap.get(new Date(2012, 6, 5)) === "Tuesday";

It can also be extended with a custom "canonizer" function that determines how to hash values:

import {naiveCanonize, jsonCanonize, JsonCanonMap, CanonMap} from "big-m";

// Same as default canonizer, but with greater recursion depth (default is 2)
new CanonMap([], 6);

// Canonize by ID with fallback to naive
const customCanonMap = new CanonMap([
  [{id: "TEST1", x: 7}, 77],
  [{ x: 7 }, 88]
], lookup => lookup.id || naiveCanonize(lookup));

customCanonMap.get({id: "TEST1", x: 8}) === 77; // Ignores other values, uses ID
customCanonMap.get({x: 8}) === undefined; // Uses all fields, so lookup fails

// Default canonizer with JSON.stringify
new CanonMap([], jsonCanonize);
// equivalent to
new CanonMap([], lookup => JSON.stringify(lookup));
// also equivalent to
new JsonCanonMap();

Finally, to implement a CanonMap that makes use of a prototype hash function on the object itself, as you described, you could do something like this:

const selfHashingCanonMap = new CanonMap([], lookup => {
  if ("hash" in lookup) {
    return lookup.hash();
  } else {
    return naiveCanonize(lookup);
  }
});

Upvotes: 3

Bergi
Bergi

Reputation: 664599

Is something like this possible?

No, this is a known flaw of ES6 Collections. All they do is check for reference identity, and there is no way to change that.

The best thing you can do (if hash consing the instances is not an option as you say) is not to use objects for the keys. Instead, use strings that encode the Key values, and convert back and forth between the two representations. Given that you consider your keys to be immutable, this should not pose a problem.

Upvotes: 18

Related Questions