Fast data structure for random and sequential access

Question

I'm looking for a data structure or a combination of various data structures that perform very well on random and sequential access.

I need to map an (integer) id to a (double) value and sort by that value. The values can occur multiple times.

The amount of data can possibly be large.

Insertion or deletion are not critical. Iteration and Get Operations are.

I'm using Java. Currently I have a Guava Multimap, built from a TreeMap and ArrayList for sequential access. For random access I use a HashMap in parallel.

Any suggestions?

Answer 1

When insertion and deletion are not critical, then a sorted array might be your friend. You could search there directly via Arrays.binarySearch and you custom Comparator.

In case you don't know any sane upper bound on the size, you can switch to an ArrayList (or implement you own resizing, but why...).

I guess this could be faster then the TreeMap, which is good when insertion and/or deletion are important, but suffers from bad spatial locality (binary tree with many pointers to follow).

The optimal structure would place all the data in a single array, which is impossible in Java (you'd need C struct for this). You could fake it by placing doubles into longs, this is sure to work and to be fast (Double.doubleToLongBits and back are intrinsics, and the length of both datatypes is 64 bits). This would mean a non-trivial amount of work, especially for sorting (if this is uncommon enough, a conversion in some sortable array and back would do).

In order to get faster search, you could use hashing, e.g., via a HashMap pointing to first element and linking the elements. As you keys are ints, some primitive-capable implementation would help (e.g. trove or fastutils or whatever).

There are countless possibilities, but keeping all your data in sync can be hard.