primitive multimap in java with good (insert, iteration) performance characteristics

Question

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

Answer 1

Have you considered implementing the multi-portion yourself using a primitive long -> Object-map and primitive int-set as the value?

Answer 2

What about Google collections library? http://code.google.com/p/google-collections/