How Javascript compare key of Map

Question

I am using Javascript ES6 features in a node.js application:

class pairKey {
constructor(x_pos, y_pos) {
 this._X = x_pos;
 this._Y = y_pos;
}
get x() {
 return this._X;
}
set x(x_pos) {
 this._X = x_pos;
}
get y() {
 return this._Y;
}
set y(y_pos) {
 this._Y = y_pos;
}
var allElem = new Map();
allElem.set(new pairKey(1,2), 'a');
allElem.set(new pairKey(2,3), 'b');
console.log(allElem.has(new pairKey(1,2))); //Should return true instead return false

In this code I want to use a pair of Int as key of my map (allElem).
The problem is that I don't know how Map compare objects in javascript.
Someone can help me?

Answer 1

Map does use the SameValueZero algorithm for comparing the keys. This means that reference equality is used for objects, so if you have a = new PairKey(1, 2) and b = new PairKey(1, 2) they are not the same object - a !== b.

So what can you do to solve this? There are basically two ways to solve this:

• use not the object itself as a key, but rather a primitive (e.g. string) representation of it, which can be created from distinct instances with the same value
• use hash consing for your key objects, so that new PairKey always returns the same object if called with the same arguments

Also you might be able to subclass Map where all methods are overwritten so that they handle PairKeys specially, relying on one of the above techniques.

Unfortunately, hash consing is impossible to implement without weak references and without leaking memory, so we'll have to resort to the first technique:

class Pair {
 constructor(x, y) {
 this.x = x;
 this.y = y;
 }
 toKey() {
 return `Pair(${this.x}, ${this.y})`;
 }
 static key(x, y) {
 return new Pair(x, y).toKey();
 }
}
var allElem = new Map(); // string -> string
allElem.set(Pair.key(1, 2), 'a');
allElem.set(Pair.key(2, 3), 'b');
console.log(allElem.has(Pair.key(1, 2))); // true

Answer 2

The reason your code fails is that Map uses same-value algorithm to match keys. An object instance is not the same value as another object instance, even if both share the same intrinsic value (for examle, try ({a:1} === {a:1}) -> it's false). One way you could make that work for you is to add a key property to your object such that the same intrinsic values generate the exact same key (1 to 1). Then use that key when setting Map entries. See example (Utilizes Symbol.for to generate a reproducable key):

'use strict'
class pairKey {
 constructor(x_pos, y_pos) {
 this._X = x_pos;
 this._Y = y_pos;
 }
 get x() {
 return this._X;
 }
 set x(x_pos) {
 this._X = x_pos;
 }
 get y() {
 return this._Y;
 }
 set y(y_pos) {
 this._Y = y_pos;
 }
 get key() {
 return Symbol.for(`pairKey[${this.x}:${this.y}]`);
 }
}
var allElem = new Map();
allElem.set(new pairKey(1, 2).key, 'a');
allElem.set(new pairKey(2, 3).key, 'b');
console.log(allElem.has(new pairKey(1, 2).key));

• Stefan Monov: What is the benefit of using Symbol.for here, as opposed to using a string?
• Amit: @StefanMonov 5+ years ago it seemed to make sense :-D
• Dmitriy Sintsov: This is quite horrible idea that map object keys ({a:1} === {a:1}) -> it's false are not compared deeply, but via the reference. This may lead to all kind of bugs, because the keys mostly are queried from db or user input values, not via the original references. There is no point to have object keys, when these are compared by reference. Very poor language decision.

Answer 3

Your map key is an object. console.log returns false because you're creating a new object to retrieve they key. It doesn't matter that it has the same pair. What matters is that it is a different new object.

If you want to retrieve the value corresponding to new pairKey(1,2) you have to do the following:

let key = new pairKey(1,2);
allElem.set(key, 'a');
console.log(allElem.has(key));

In other words if you use object as a key, make sure to use the same object to retrieve the value.

Answer 4

I apologize for bringing up the old question, but I found a very interesting solution, inspired by the Bergi's answer and the hash consing mentioned as impossible.

class PairKey {
 private static cache: Record<string, PairKey> = {};
 constructor(
 private _x: number, private _y: number,
 action: 'create' | 'read' | 'delete' = 'read'
 ) {
 const key = PairKey.key(_x, _y);
 if (action === 'create' || action === 'read') {
 if (PairKey.cache[key]) {
 return PairKey.cache[key];
 }
 if (action === 'create') {
 PairKey.cache[key] = this;
 }
 }
 else if (action === 'delete') {
 delete PairKey.cache[key];
 }
 }
 private static key(x: number, y: number) {
 return `${x}_${y}`;
 }
 get x() {
 return this._x;
 }
 set x(x_pos: number) {
 this._x = x_pos;
 }
 get y() {
 return this._y;
 }
 set y(y_pos: number) {
 this._y = y_pos;
 }
}
const allElem = new Map<PairKey, string>();
allElem.set(new PairKey(1, 2, 'create'), 'a'); // the action flag to prevent a memory leak
allElem.set(new PairKey(2, 3, 'create'), 'b'); // the action flag to prevent a memory leak
console.log(allElem.has(new PairKey(1, 2))); // Returns true
allElem.delete(new PairKey(1, 2, 'delete')); // the action flag to prevent a memory leak
console.log(allElem.has(new PairKey(1, 2))); // Returns false

A similar solution with more static stuff:

class PairKey {
 private static cache: Record<string, PairKey> = {};
 private static readonly symbol = Symbol();
 private constructor(private _x: number, private _y: number, symbol: symbol) {
 if (symbol !== PairKey.symbol) {
 throw new Error("Use 'PairKey.create()' instead of constructor");
 }
 }
 static create(x: number, y: number) {
 const key = PairKey.key(x, y);
 if (PairKey.cache[key]) {
 return PairKey.cache[key];
 }
 const pairKey = new PairKey(x, y, PairKey.symbol);
 PairKey.cache[key] = pairKey;
 return pairKey;
 }
 static read(x: number, y: number) {
 const key = PairKey.key(x, y);
 return PairKey.cache[key];
 }
 static delete(x: number, y: number) {
 const key = PairKey.key(x, y);
 const pairKey = PairKey.cache[key];
 delete PairKey.cache[key];
 return pairKey;
 }
 private static key(x: number, y: number) {
 return `${x}_${y}`;
 }
 get x() {
 return this._x;
 }
 set x(x_pos: number) {
 this._x = x_pos;
 }
 get y() {
 return this._y;
 }
 set y(y_pos: number) {
 this._y = y_pos;
 }
}
const allElem = new Map<PairKey, string>();
allElem.set(PairKey.create(1, 2), 'a');
allElem.set(PairKey.create(2, 3), 'b');
console.log(allElem.has(PairKey.read(1, 2))); // Returns true
allElem.delete(PairKey.delete(1, 2));
console.log(allElem.has(PairKey.read(1, 2))); // Returns false