title: Memory-efficient sparse array in Java
body: <p>(There are some questions about time-efficient sparse arrays but I am looking for memory efficiency.)</p>
  
  <p>I need the equivalent of a <code>List&lt;T&gt;</code> or <code>Map&lt;Integer,T&gt;</code> which</p>
  
  <ol>
  <li>Can grow on demand just by setting a key larger than any encountered before. (Can assume keys are nonnegative.)</li>
  <li>Is about as memory-efficient as an <code>ArrayList&lt;T&gt;</code> in the case that most of the indices are not <code>null</code>, i.e. when the actual data is not very sparse.</li>
  <li>When the indices are sparse, consumes space proportional to the number of non-<code>null</code> indices.</li>
  <li>Uses less memory than <code>HashMap&lt;Integer,T&gt;</code> (as this autoboxes the keys and probably does not take advantage of the scalar key type).</li>
  <li>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.</li>
  <li>Implemented in a nonviral open-source pure Java library (preferably in Maven Central).</li>
  </ol>
  
  <p>Does anyone know of such a utility class?</p>
  
  <p>I would have expected Commons Collections to have one but it did not seem to.</p>
  
  <p>I came across <code>org.apache.commons.math.util.OpenIntToFieldHashMap</code> which looks almost right except the value type is a <code>FieldElement</code> which seems gratuitous; I just want <code>T extends Object</code>. 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.</p>