Optimal way of creating a SortedSet from a number of HashMap objects

Question

I have a number of HashMap data structures containing hundreds of Comparable objects (say, of type MyClass) and need to put all the values (not the keys) in a single data structure, and then sort it.

Due to the volume and the arrival rate of MyClass objects, this procedure (performed at least once per millisecond) needs to be as efficient as possible.

An approach would be to use SortedSet, roughly as follows:

HashMap<String, MyClass>[] allMaps = ... // All the HashMaps

SortedSet<MyClass> set = new TreeSet<MyClass>();

Collection<MyClass> c;

for (HashMap<String, MyClass> m:allMaps)
{
    c = m.values();
    set.addAll(c);
}

It may be faster to pass a sorted collection to set.addAll(), which may re-sort the TreeSet on every insertion, or after every few insertions. However, to do so, a List needs to be passed to Collections.sort(), which means a conversion from Collection to List has to take place, i.e. another performance hit has to be sustained.

Also, there may be another, more efficient way of achieving the same goal.

Comments?

Answer 1

I think the answer kinda depends on how the MyClass data tends to change. For example, if you have a couple of new values coming in per timeframe, then you might want to consider keeping a hold of the last returned sorted set and a copy of the previous keys so that on the next run, you can just do a delta of the changes (i.e. find the new keys in the maps and manually insert them into the sorted set you returned last time).

This algorithm varies a bit if the MyClass objects might get removed from the maps. But the general thought is to make it faster, you have to find a way to perform incremental changes instead of reprocessing the whole set every time.