Sorting 1,000,000 Objects (not by Key) - Java

Question

I have c.1,000,000 objects that need to be stored in some form of data structure. They must be unique by a key (ID) - but sorted according to their date. I'm therefore trying to think of a best way of storing them in some form of data structure. Performance (in terms of time taken to execute) it the primary goal, and then memory usage. My idea was to put the objects into a Tree, so they may be sorted according to their date as they enter the data structure, and I can then return them in order. However - I think this is going to be horrendously slow to find a single object based on it's ID. One thought that did occur to me was to have a secondary structure which linked ID's to dates so I can reduce the time taken to find the single object, or just store everything by this ID anyway (perhaps in a HashTable) and then just sort through all 1,000,000 objects when I want to return them (although this seems to take a very long time).

Key Points:

Objects may be added afterwards so the c.1,000,000 objects ARE NOT fixed. They WILL NOT be updated or removed. I MAY NOT use Java's built in Comparator. I am optimising for efficiency of returning the data - whether this be the complete set in order (by date), or a single object obtained from it's ID.

Answer 1

if performance in your chief concern before memory usage, i'd go with 2 datastructures:

ArrayList<YourClass> instancesByDate;

and

HashMap<SomeId,YourClass> instancesById;

this gives you the fastest traversal by date and O(1) lookup (depending on hashCode() obviously).

Answer 2

How about using a hashtable of ID => yourobject for the ID lookups, and a secondary hashtable of date (at some level of granularity) => Vector<yourobject>? You could choose the 'granularity' of the date to ensure you've a moderate number of objects in each vector - and sort each by date.