Monday, February 18, 2013

Assembling ordered Lists using HashMap and Collections.sort()

LinkedHashMap won't work if that's what you were thinking....

I was presented with a use case having to assemble an ordered List of objects out of tens/hundreds of thousands of ordered elements.  Here's the List<EventObject> I need to do something with:

  • Keys are not unique.
  • The List<EventObject> needs to become a List<SummarizedObject>.
  • 1 or more EventObjects make up a SummarizedObject.
  • The order of List<EventObject> must be matched in the resulting List<SummarizedObject>.  Meaning, the first EventObject will definitely be in the first SummarizedObject and the last EventObject will definitely be in the last SummarizedObject.
  • Typically, for every 10k EventObject values 100 unique keys and 200 unique SummarizedObjects are created (give or take 1 order of magnitude).
  • I'm not concerned about concurrency at this time.
LinkedHashMap<String, List<SummarizedObject>> wouldn't work for me even though it maintains order because a single key could have several SummarizedObjects (hence the List of SummarizedObjects) whose order could interweave with values in different keys.  Bummer.

I kept coming back to the HashMap.  Being able to quickly determine a key's existence in the Map and (if it does exist) going straight to that key's List<SummarizedObject> was ideal.  So I dropped an order field in SummarizedObject, which looked like:

The pseudo-code for getting the EventObjects into a HashMap<String, List<SummarizedObject>> is:

So my last problem is to assemble all SummarizedObjects into a single, properly ordered List.  Enter Collections.sort(). Here's real code:

Great performance and not that much code. And it can be optimized further by finding a better way to find the proper SummarizedObject in Step 5 of the above pseudo-code. Hope this helps someone!