Fastest Way of Using Coordinates as Keys in Javascript Hashmap

Question

I'd like to store objects using their coordinates, like so:

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

These can then be retrieved using hash_map[x + "-" + y].

However, I am not sure about whether creating a new string every time an object is accessed is such a great idea.

An alternative would be to combine the coordinates by doing something like x | (y >>> 16) but I have no idea about how many bits to shift the y value by, what actually happens internally (since javascript's numbers are all floats, so there's an exponent and mantissa etc) and whether it's actually worth it.

tl;dr What's the fastest way (including garbage collection) of storing objects in a hash map with coordinates as keys?

Part of that I can answer ... JavaScript bitwise operators all work on 16-bit integers — Jeremy J Starcher
– Jeremy J Starcher, Commented Aug 17, 2016 at 20:35
Do you have to use a hash map? Assuming the coordinates are integers, why not use a 2D array? Or even a 2D hash map. If you used arrays, you could pre-allocate the keys and save yourself the cost of adding unique keys every time a new location is encountered. — Mike Cluck
– Mike Cluck, Commented Aug 17, 2016 at 20:36
What is the maximum size of the coordinates? What type of coordinate is it (GPS coordinates, grid coordinates, etc.)? — 10100111001
– 10100111001, Commented Aug 17, 2016 at 20:41
what do you need that for? I can't think of a situation where I would need/use this structure (to cache the Points by position)? If I need to store points by their position I'd probably use a quad-tree. — Thomas
– Thomas, Commented Aug 17, 2016 at 20:46
@MikeC, you're right! I could use an array. In context, it's for 2D game chucks, of which random ones need to be loaded, so the array would be wasting a bit of space though — Lucien
– Lucien, Commented Aug 17, 2016 at 20:48

10100111001 · Accepted Answer · 2016-08-18 00:09:02Z

You can use the below solution to compound a pair of coordinates into a single 32 bit signed integer. This integer can then be used as the key for a JS object. The 2 coordinates can only be a maximum of 16 bits. Therefore x and y can only contains values -32767 to +32767 (2^15-1).

In the below example, 100 random pair of coordinates are generated and added to to the hash_map object with their values containing the x and y coordinates calculated from the key. The coordinates must be within the aforementioned range otherwise an exception will be thrown.

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

Collectives™ on Stack Overflow

Fastest Way of Using Coordinates as Keys in Javascript Hashmap

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related