Efficiently ordered data-structure that supports duplicate keys

Question

I am looking for a data structure that orders objects at insertion efficiently. I would like to order these objects (in this case individuals) based on the value of a particular variable (in this case the fitness).

The data structure should allow duplicate keys since a particular fitness value can occur in different individuals. This is a problem because for example the TreeMap data structure does not allow duplicate keys. I would prefer to use this type of tree-like structure because of it's efficiency O(log N).

If I inserted the individuals in an ordered list, the efficiency would drop to O(n), and sorting the individuals after they have been inserted wouldn't be very efficient either.

Is there a data structure that is efficient, keeps the individuals ordered and supports duplicate-keys?

I will be adding and removing entries very often after the data structure has been created so sorting the objects after the structure has been created would be very expensive.

Answer 1

Both Apache Commons and Guava support multimaps, which are what you're looking for.

Alternatively, depending on your usecase, you could gather the elements in an ArrayList and sort it afterwards in O(n lg n) total time.

Or, you could define a comparison that checks fitness first and other distinguishing properties of the items if the fitnesses compare equal.