CODEWITHSUNDEEP
javascriptecmascript-6
Daniel Cheung
Daniel Cheung

Reputation: 4819

ES6 Hashmap with 2 keys

JavaScript ES6 introduced Map implemented with hash table. Since hash table look up time is on average O(1), for random accessed data, Map seems to be a good choice for data storage.

However, JavaScript does not have data structures like struct in C++ that can be used as keys in the Map to enable "multiple keys mapping". The closest ones are Objects, but their instances do not equal to each other even if "contents are the same".

If I want to save a 2D or 3D tile based game map using the Map type, is there a way to easily access the blocks given the coordinates? Of course strings like "1,2,3" (representing x,y,z) would work, but is there a way that we can use integers as keys?

And if I must fall back to using assembled string coordinates, would the performance decrease a lot?

EDIT: I want to use a hash table because there may be "holes" in the maps and tiles may be created randomly in the middle of nowhere.

Upvotes: 0

Views: 2842

Answers (4)

Anderson
Anderson

Reputation: 31

I changed Daniels' performance test by adding the "Left shifting" case, where we left shift those numbers (as long as we don't extrapolate the number limits). I got the following results:

Array           OPS 0.90    ±4.68%     91% slower    //a[z][y][x]
Nested Object   OPS 0.86    ±3.25%     92% slower    //a[z][y][x]
String Object   OPS 3.59    ±16.90%    68% slower    //a["x,y,z"]
Left Shift      OPS 10.68   ±11.69%    fastest       //a[(x<<N1)+(y<<N2)+z]

Upvotes: 1

Daniel Cheung
Daniel Cheung

Reputation: 4819

I just made a performance test between storing in Array, and Nested Object as well as Object with string keys. The result is surprising to me. The fastest is Object with string keys.

https://jsperf.com/multiple-dimension-sparse-matrix

Array           OPS 0.48    ±5.19%     77% slower    //a[z][y][x]
Nested Object   OPS 0.51    ±16.65%    77% slower    //a[z][y][x]
String Object   OPS 2.96    ±29.77%    fastest       //a["x,y,z"]

Upvotes: 1

Kaiido
Kaiido

Reputation: 136746

What you are asking for is just a multidimensional Array. If you are going to use only integer keys, there is absolutely no benefit to use a Map.

const map = [];
for(let x=0; x<2; x++) {
  let xArr = [];
  map.push(xArr);
  for(let y=0; y<2; y++) {
    let yArr = [];
    xArr.push(yArr);
    for(let z=0; z<2; z++) {
      yArr.push(`${x},${y},${z}`);
    }
  }
}
console.log(map[1][1][0]);
console.log(map);

Upvotes: 1

CertainPerformance
CertainPerformance

Reputation: 370809

Other than joining the keys into a string like you mentioned (which is perfectly fine IMO), another option is to use multiple nested Maps. For example, for a 3d structure, accessing 1,2,3 (axes x, y, and z, let's say) could be done with

bigMap.get(1).get(2).get(3)

where the bigMap (containing the 3d structure) contains Map values for each y and z slice, and each of those has Map keys corresponding to each z slice, and each z-slice Map has values containing the information at each coordinate.

But while this is a possibility, your idea of an object or Map indexed by comma-joined coordinates is perfectly fine and probably more understandable at a glance IMO.

Remember that object property lookup is O(1) just like Map lookup - there's no performance hit if you use a single object (or Map) indexed by strings.

Upvotes: 0

Related Questions