Memory-efficient sparse array in Java

Question

(There are some questions about time-efficient sparse arrays but I am looking for memory efficiency.)

I need the equivalent of a List<T> or Map<Integer,T> which

1. Can grow on demand just by setting a key larger than any encountered before. (Can assume keys are nonnegative.)
2. Is about as memory-efficient as an ArrayList<T> in the case that most of the indices are not null, i.e. when the actual data is not very sparse.
3. When the indices are sparse, consumes space proportional to the number of non-null indices.
4. Uses less memory than HashMap<Integer,T> (as this autoboxes the keys and probably does not take advantage of the scalar key type).
5. Can get or set an element in amortized log(N) time where N is the number of entries: need not be linear time, binary search would be acceptable.
6. Implemented in a nonviral open-source pure Java library (preferably in Maven Central).

Does anyone know of such a utility class?

I would have expected Commons Collections to have one but it did not seem to.

I came across org.apache.commons.math.util.OpenIntToFieldHashMap which looks almost right except the value type is a FieldElement which seems gratuitous; I just want T extends Object. It looks like it would be easy to edit its source code to be more generic, though I would rather use a binary dependency if one is available.

Answer 1

Late to this question, but there is IntMap in libgdx which uses cuckoo hashing. If anything it would be interesting to compare with the others.

Answer 2

I would look at Android's SparseArray implementation for inspiration. You can view the source by downloading AOSP's source code here http://source.android.com/source/downloading.html

Answer 3

I would try with trove collections, there is TIntObjectMap which can work for your intents.

Answer 4

I have saved my test case as jglick/inthashmap. The results:

HashMap size: 1017504
TIntObjectMap size: 853216
IntHashMap size: 846984
OpenIntObjectHashMap size: 760472

Answer 5

I will suggest you to use OpenIntObjectHashMap from Colt library. Link