使用元组或对象进行映射

Question

我尝试使用新的（ES6）Map 对象来表示属性与值之间的映射关系。

我有类似于以下形式的对象：

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

我希望能够基于它们的 key1 和 key2 值同时对它们进行分组。

例如，我想能够根据 x 和 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}]

获取包含以下内容的地图：

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

在Python中，我会使用元组作为字典的键。ES6 Map 允许任意对象作为键，但使用标准等式算法（===），因此据我所知，对象只能按引用相等。

如何使用ES6 Map 实现这种分组？或者，如果有一种优雅的方式，可以使用普通JS对象来解决。

我不想使用外部集合库 - 但如果有更好的解决方案，我也有兴趣了解它。

- Benjamin Gruenbaum

Answer 1

好的，我现在已经在esdiscuss上提出了这个问题，并从Mozilla的Jason Orendorff那里得到了答案：

1. 这确实是ES6 maps的一个问题。
2. 解决方案将以ES7 value objects的形式为键提供，而不是对象。
3. 之前考虑让人们指定.equals和.hashCode，但出于某些好的原因被拒绝了，转而采用值对象。
4. 目前唯一的解决方案是自己编写集合。

一个基本的这样的集合（概念，不要在生产代码中使用）由Bradley在ESDiscuss线程上提供，可能看起来像这样：

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;
  });
}

更好的解决方案是使用类似MontageJS/Collections这样的东西，它允许指定哈希/相等函数。

你可以在这里查看API文档。

- Benjamin Gruenbaum

Answer 2

看起来似乎不太方便。你能做什么呢？像往常一样，只能做一些可怕的事情。

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;
})();

而这就是它的效果。

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]]

- Ry-

---

我不确定是否可能滥用WeakMap来使其内存效率更高。可能不行。 - Ry-

你刚刚实现了一个元组享元模式，真有创意！但我认为这个问题应该在语言级别解决。 - Benjamin Gruenbaum

Answer 3

多年过去了，这仍然是JavaScript的一个问题。我改进了Jamesernator的方法，并创建了包https://www.npmjs.com/package/collections-deep-equal。现在你可以得到你想要的：

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));

- Leandro Facchinetti

Answer 4

虽然这个问题很旧了，但是在JavaScript中，值对象仍然不存在（所以人们可能仍然感兴趣），因此我决定编写一个简单的库，为数组作为映射键提供类似的行为（存储库在这里：https://github.com/Jamesernator/es6-array-map）。该库的设计与使用方式基本相同，只是数组是按元素逐个比较而不是按标识比较。

用法：

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}

警告：该库通过标识处理关键元素，因此以下内容无法正常工作：

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

只要您可以将数据序列化为基元数组，就可以按以下方式使用ArrayMap：

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}

- Jamesernator

Answer 5

Benjamin的答案并不适用于所有对象，因为它依赖于JSON.stringify，无法处理循环对象，并且可以将不同的对象映射到相同的字符串。Minitech的答案可以创建大量嵌套映射树，我怀疑这既浪费内存又浪费CPU，特别是对于长元组，因为它必须为元组中的每个元素创建一个映射。

如果您知道您的元组只包含数字，则最佳解决方案是使用[x,y].join(',') 作为键。如果要使用包含任意对象的元组作为键，则仍然可以使用此方法，但必须首先将对象映射到唯一标识符。在下面的代码中，我使用get_object_id懒惰地生成这些标识符，它将生成的ID存储在内部映射中。然后，我可以通过连接这些ID来为元组生成键。（请参见本答案底部的代码。）

tuple方法可以用于将对象元组哈希为可用作映射键的字符串。这使用对象等价性：

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

如果您确定元组只包含对象（即非null、数字或字符串），则可以在get_object_id中使用WeakMap，以便get_object_id和tuple不会泄漏作为参数传递的对象。请保留HTML标签。

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>');

- bcmpinc

---

请解释一下您认为我关于WeakMaps的陈述为何是错误的。如果您的回答可以不使用JSON.stringify，请更新您的回答以解释如何做到这一点。 - bcmpinc

使用WeakMap可以确保元组中使用的对象仍然符合垃圾回收的条件。也就是说，如果WeakMap是唯一引用一个对象的东西，垃圾回收器可以销毁该对象（并从WeakMap中删除它）。这样可以避免内存泄漏。 - bcmpinc

对象在 WeakMap 中被用作“键”，因此如果它们符合垃圾回收的条件，那么就没问题了。该映射用于为对象添加唯一标识符，而不实际更改对象。要将答案中的 JSON.stringify 替换为另一个哈希函数，您还需要创建这样的其他哈希函数，这很困难。我的 tuple() 就是这样的另一个哈希函数，具有与 JSON.stringify 不同（更好）的属性。除了哈希函数之外，我们的答案是相同的：将元组映射到可用作键的内容。 - bcmpinc

不，它正是在精确地使用 WeakMaps 的设计。是的，我知道对于你的问题，应该使用 .join(',') 作为哈希函数。但是你的问题的读者可能有不同的要求。你的解决方案不适用于循环对象或被 JSON.stringify 映射到相同字符串的对象。而且对于复杂对象来说效率低下。 - bcmpinc

让我们在聊天中继续这个讨论。 - bcmpinc

Answer 6

元组的另一段代码。

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'

- happynow