java中的原始多重映射具有良好的（插入、迭代）性能特征
我正在使用 Java 中的 ints/longs 进行一些繁重的处理（构建逆索引）。
我已经确定标准 java.collections 映射的（取消）装箱占用了总处理时间的很大一部分。 （与使用数组的类似实现相比，由于内存限制我无法使用数组）。
我正在寻找可以支持以下结构的快速第 3 方实现（或任何与此相关的实现）：
Map 具有特征：
- 映射中的键是稀疏的（+/- 10.000.000 个键在 [0,2^64] 范围内 - 值总是附加到列表的末尾 -快速插入（如果可能的话分摊O(1)） -按键顺序的快速迭代。
我看过 trove、fastutil 等，但找不到使用基元（仅法线贴图）的多重贴图实现，
感谢任何帮助。
谢谢， 吉尔特-扬
I'm doing some heavy processing (building inverse indices) using ints/ longs in Java.
I've determined that (un)boxing of standard java.collections maps takes a big portion of the total processing time. (as compared to a similiar implementation using arrays, which I can't use due to memory constraints).
I'm looking for a fast 3rd-party implementation (or any implementation at all for that matter) that could support the following structure:
Map
with characteristics:
-keys in the map are sparse (+/- 10.000.000 keys in range [0,2^64]
-values are always appended to the end of the list
-fast insert (amortized O(1) if possible)
-fast iteration in key-order.
I've looked at trove, fastutil, etc. but couldn't find a multimap implementation using primitives (only normal maps)
any help is appreciated.
Thanks,
Geert-Jan
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您是否考虑过使用原始的 long -> 自己实现多部分？对象映射和原始 int-set 作为值？
Have you considered implementing the multi-portion yourself using a primitive long -> Object-map and primitive int-set as the value?
Google 收藏库怎么样？ http://code.google.com/p/google-collections/
What about Google collections library? http://code.google.com/p/google-collections/
根据基数可以使用特定类型的对象
原始 Int/Long 到 where 值：
if (size == 1) => Long（如果有大量重复项，可以进行重复数据删除）；
if (大小 <= 13) => LogSet（数组中有 16 个元素）；
如果（大小> 13）=> SpaceLongBitSet。使用例如 16 长作为每个块的有效负载（甚至可以重用数组）
可以将 26 视为决策点。如果性能非常重要，请仅针对特定分片/块大小进行基准测试，例如 SparseLongBitSet。对于内存局部性，请考虑重用相同的内存块（例如 2M 的数组）。
最后一滴：
Insted of Object 考虑使用有效负载索引（例如堆外指针）并使用静态方法（如 Flightweith）对有效负载进行操作。
Depending on cardinality can use specific types of object
Primitive Int/Long To where value:
if (size == 1) => Long (can dedup if have huge number of duplicates);
if (size <= 13) => LogSet (16 elements in array);
if (size > 13) => SparceLongBitSet. using e.g. 16 long as payload per block (can even reuse array)
for int can consider 26 as desision point. If performance is very important do benchmarking e.g. SparseLongBitSet only with specific sharding/block sizing. For memory locality consider reusing same memory blocks (e.g. arrays of 2M).
Last drop:
Insted of Object consider useing index to payload (e.g. offheap pointer) and use static methods (Flightweith like) to operate on payload.