Anyone know of a java.util.Map implementation optimized for low memory use?

Question

I've looked in the usual places (apache commons, google) and not been able to find one ...

It should be opensource.

Pretty much looking for one based on a linked list. The use case is 10'000's of maps, with not necessarily many values in. It does not need to scale up, as i can convert it when it gets too big.

Some numbers, sizes using some calculated jvm values (8bytes/java.lang.Object, 4bytes/ref) the HashMap is about 100+32n bytes, the theoretical best is 12+20*n. <-- I want that, for small n.

Answer 1

Could have a look at commons-collections Flat3Map, it's optimised to store 3 values in 3 fields and overflows to another map at 4.

I haven't looked at the implementation but it may be worth thinking about. Only trouble is that since commons-collections is 1.3 compatible there are no generic's.

Answer 2

Wrap an ArrayList with the Map interface. The ArrayList uses only a few bytes itself. Each node needs two pointers, one for the key and one for the value. Use sequential search to look up values. As long as there are only few entries, performance will be OK[*]. This will give you the leeway to use real maps for the few vases where you have a large number of values.

*: Say your average map size is 10. Todays computers can compare roughly 100 million keys per second, so each lookup will take less than five microseconds on average.

If the performance is still too bad for your use case, you can try to sort the array by key and use binary search.