javascript - 在 Javascript Hashmap 中使用坐标作为键的最快方法

Question

我想使用坐标来存储对象，如下所示:

var hash_map = {};
hash_map[x + "-" + y] = new Object();

然后可以使用 hash_map[x + "-" + y] 检索这些内容.

但是，我不确定每次访问对象时创建一个新字符串是否是一个好主意。

另一种方法是通过执行类似 x | (y >>> 16) 的操作来组合坐标。但我不知道要移动多少位 y value by，内部实际发生了什么(因为 javascript 的数字都是 float ，所以有指数和尾数等)以及它是否真的值得。

tl;dr 在以坐标为键的 HashMap 中存储对象的最快方法(包括垃圾回收)是什么？

Answer 1

您可以使用以下解决方案将一对坐标复合为单个 32 位有符号整数。然后这个整数可以用作 JS 对象的键。 2个坐标最多只能是16位。因此 x 和 y 只能包含值 -32767 到 +32767 (2^15-1)。

在下面的示例中，生成 100 个随机坐标对并将其添加到 hash_map 对象中，它们的值包含根据键计算出的 x 和 y 坐标。坐标必须在上述范围内，否则会抛出异常。

var MAX_16BIT_SIGNED = 32767; //Math.floor((Math.pow(2, 16)/2)-1);

function getRandomIntInclusive(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function getRandomKey() {
  var x = getRandomIntInclusive(MAX_16BIT_SIGNED * -1, MAX_16BIT_SIGNED),
    y = getRandomIntInclusive(MAX_16BIT_SIGNED * -1, MAX_16BIT_SIGNED);

  //console.log("Generated key with x: " + x + " and y: " + y);
  return getKey(x, y);
}

function getKey(x, y) {
  if (x > MAX_16BIT_SIGNED || y > MAX_16BIT_SIGNED)
    throw "Invalid X or Y value.";
  x += MAX_16BIT_SIGNED;
  y += MAX_16BIT_SIGNED;
  return (x << 16) | y;
}

function getX(key) {
  return (key >> 16) - MAX_16BIT_SIGNED;
}

function getY(key) {
  return (key & 0xFFFF) - MAX_16BIT_SIGNED;
}

var hash_map = {};
hash_map[getKey(MAX_16BIT_SIGNED * -1, MAX_16BIT_SIGNED)] = "test";
hash_map[getKey(MAX_16BIT_SIGNED, MAX_16BIT_SIGNED)] = "test";
hash_map[getKey(MAX_16BIT_SIGNED * -1, MAX_16BIT_SIGNED * -1)] = "test";
hash_map[getKey(MAX_16BIT_SIGNED, MAX_16BIT_SIGNED * -1)] = "test";
//hash_map[getKey(MAX_16BIT_SIGNED+1, MAX_16BIT_SIGNED+1)] = "test";

for (var i = 0; i < 100; i++) {
  var key = getRandomKey();
  hash_map[key] = {
    x: getX(key),
    y: getY(key)
  };
}
console.log(JSON.stringify(hash_map));
console.log(100 === Object.keys(hash_map).length);