What HashMap-like collection should I use for this case?

Question

I have a number of coordinate spaces measuring 65,536 by 65,536 and populated by many objects where no two can share the same coordinates. Given this, I can guarantee a unique hash for each object by combining the two shorts that make the coordinates into int which makes the hash.

To store references to these objects I am currently using a HashMap with a custom immutable Point class as key. However since I am beginning to utilise a whole lot of these coordinate spaces at once I have begun to look at ways to trim down on memory usage.

My understanding of how java's HashMap works is basic, but considering that I can guarantee a unique hash for each object, it seems like I could be using a much more memory efficient version which:

Doesn't use buckets which can contain multiple objects
Can put and get objects by using the hash instead of using a key

Does such a HashMap-like collection exist?

edit: The coordinate spaces are sparse, running at around 2000-3000 objects per.

Well at the very least I would use a single array, since I dont want/need 65,536 extra array objects (A 2d array is actually an array of arrays)... but even that reserves too much space in memeory as I only really have 2000-3000 objects per coord space and an array would reserve memory for 4,294,967,296 references — Numeron, Apr 20 '12 at 11:00
@Numeron - please refer to this [discussion on sparse matrices](http://stackoverflow.com/questions/390181/sparse-matrices-arrays-in-java). Since memory efficiency is important to you it might be the way to go for your project. — Perception, Apr 20 '12 at 11:03

score 4 · Accepted Answer · edited Apr 20 '12 at 11:03

4

You could use TIntObjectHashMap or TIntXxxxHashMap from trove4j:

private final TIntIntHashMap map = ...

public void putInt(int x, int y, int value) {
   int index = (x << 16) + y;
   map.put(index, value); // only uses primitives.
}

public int getInt(int x, int y) {
   int index = (x << 16) + y;
   return map.get(index);
}

edited Apr 20 '12 at 11:03

Ernest Friedman-Hill

80,601
10
150
186

answered Apr 20 '12 at 10:59

Peter Lawrey

525,659
79
751
1,130

Ernest Friedman-Hill · Answer 2 · 2012-04-20T11:22:40.223

Your statement about buckets belies a misunderstanding. Hash buckets don't contain all the items with a given hashcode; they contain all the items with some function of the hashcode in common. For example, a simple example of such a function might just be the modulo operator. You have 2^32 different possible codes, but a HashMap is likely to have only (for example) 100 buckets or so. Using single-item buckets would mean you were effectively putting your objects into an array with the hashcode as the index!

Now, the other idea of a specialized map that just used a 32-bit integer as the key would actually work, and reduce the memory usage a bit. Peter Lawrey has an excellent suggestion in his answer.

Hmm, thanks for some clarification, I think I get what you're saying. Im going to have to go back and re-read some of my java books... Up until now, HashMaps have basically worked by magic. — Numeron, Apr 20 '12 at 11:19

What HashMap-like collection should I use for this case?

2 Answers2