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

Question

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

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

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

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

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

tl;dr 在以坐标为键的哈希映射中存储对象的最快方法（包括垃圾回收）是什么？

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

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

Fastest Way of Using Coordinates as Keys in Javascript Hashmap

javascript

performance

hashmap

hashtable