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 double
s into long
s, 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 int
s, 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.