java - java中具有良好（插入，迭代）性能特征的原始多图

Question

我正在使用 Java 中的 ints/long 进行一些繁重的处理（构建反向索引）。

我已经确定标准 java.collections 映射的（取消）装箱占用了总处理时间的很大一部分。（与使用数组的类似实现相比，由于内存限制，我无法使用）。

我正在寻找可以支持以下结构的快速第 3 方实施（或任何实施）：

具有特征的地图：

- 地图中的键是稀疏的（范围 [0,2^64] 中的 +/- 10.000.000 个键 - 值始终附加到列表的末尾 - 快速插入（如果可能，摊销 O(1)） - 快速迭代按键顺序。

我看过 trove、fastutil 等，但找不到使用原语的多图实现（只有法线贴图）

任何帮助表示赞赏。

谢谢， Geert-Jan

Answer 1

您是否考虑过使用原始 long -> Object-map 和原始 int-set 作为值自己实现多部分？

Answer 2

谷歌收藏库怎么样？http://code.google.com/p/google-collections/

Answer 3

根据基数可以使用特定类型的对象 Primitive Int/Long To where 值：

• if (size == 1) => Long（如果有大量重复项，可以去重）；

• if (size <= 13) => LogSet（数组中的 16 个元素）；

• 如果（大小 > 13）=> SparceLongBitSet。使用例如 16 长作为每个块的有效负载（甚至可以重用数组）

for int 可以将 26 视为目标点。如果性能非常重要，请仅使用特定的分片/块大小进行基准测试，例如 SparseLongBitSet。对于内存局部性，请考虑重用相同的内存块（例如 2M 的数组）。

最后一滴：Insted of Object 考虑使用有效载荷的索引（例如堆外指针）并使用静态方法（Flightweith 之类）对有效载荷进行操作。