title: Appropriate data structure for storing large number of objects retrievable by sparse identifier
body: <p>I guess I'm looking for a sparse array implementation, but I really need this to be efficient in terms of memory usage, and one peculiarity of my data that an implementation could take advantage of is that the indices are populated such that if the value for an index <code>i</code> is present, the indices <code>i-1</code> and <code>i+1</code> are also likely to have values present, and similarly if the value for <code>i</code> has no value present, <code>i-1</code> and <code>i+1</code> are likely to not have values present.</p>
  
  <p>I'm working in Java, and I need the index type to be <code>long</code> rather than the more usual <code>int</code>, if this makes a difference.  I have approximately 50 million objects that will need to be stored.  I've looked into Trove4J's <code>TLongObjectHashMap</code>, unfortunately this will require around 1.6GB for the hash table alone, and I really need to improve on this.  </p>
  
  <p>Can anyone point me towards something that can optimize for long runs of sequentially allocated identifiers?  Logarithmic performance of insert/get is acceptable to me, so perhaps something tree-based?</p>