java - 存储大量可通过稀疏标识符检索的对象的适当数据结构

Question

我想我正在寻找一个稀疏数组实现，但我真的需要它在内存使用方面是有效的，并且实现可以利用的我的数据的一个特点是填充索引使得如果值如果存在索引i，则索引i-1和i+1也可能存在值，类似地，如果值 fori不存在值，i-1并且i+1可能不存在值。

我正在使用 Java，如果这有所作为，我需要索引类型long而不是更常见的类型。int我有大约 5000 万个对象需要存储。我研究了 Trove4J 的TLongObjectHashMap，不幸的是，仅哈希表就需要大约 1.6GB，我真的需要改进这一点。

谁能指出我可以针对长期顺序分配的标识符进行优化的东西？插入/获取的对数性能对我来说是可以接受的，所以也许是基于树的？

Answer 1

Maybe you could use a database instead of an array ? An in-memory embedded databse like h2sql!

Answer 2

Btrees 的内存开销很小，所以我会尝试这些。