Friday, March 19, 2010

LinkedHashMap enhanced

In my day to day Java programming it is rare for me to feel the need to re-engineer or significantly enhance something quite fundamental to the Java language. I am a pretty average programmer, I get the job done, I like to do things elegantly but I do not spend my spare time creating my own languages and compilers (that stuff looks harder than "rocket science"). Most of the time the standard Java Collections Framework with the ArrayList, HashSet, HashMap and LinkedHashMap is more than ample for my meagre needs. Sometimes I have looked elsewhere to solve a particular problem; I had previously encountered the ArrayListMultimap from the Google Collections Library. This deviates from the standard Map implementations in that it allows you to create a "Map" which may associate multiple values with a single key (well technically it does not implement the Map interface but never mind!).

Google Collections' ArrayListMultimap

The ArrayListMultimap is really useful and very powerful. Imagine for example you wanted tag cloud functionality for a blog. You can iterate through your pages, putting them in your "cloudmap" (new ArrayListMultimap<String,URL>) using the tag as the map key. You can very easily get back a list of URLs with that tag key.

List<URL> links = cloudmap.get("java");

You can also very easily produce the tag counts necessary for a tag cloud using something like.

int linkcount = cloudmap.get("java").size();

My contribution: LinkedHashMap augmented

I have been working on a timetable related application recently which provoked me to extend the behaviour of LinkedHashMap. My situation was that I needed to produce a Map where the entry order of the data was important (e.g. insertion-order). Java Collections' LinkedHashMap is designed specifically for those requirements. I had an additional requirement to be able to fetch a portion of my map whose keys range from fromKey to toKey. LinkedHashMap does not itself implement this. TreeMap is a collections class which does permit accessing ranges of data, however, TreeMap does not support insertion-order. Instead TreeMap supports data with a natural ordering (e.g. numbers in numeric order, dates in chronological order). In my map, although the keys and values were important data, the natural ordering does not provide anything useful.

So I set about extending LinkedHashMap and came up with a class which implements the following interface:

public interface ILinkedHashMapAugmented<K, V> extends Map<K, V> {

LinkedHashMapAugmented<K, V> subMap(K fromKey, K toKey);

LinkedHashMapAugmented<K, V> subMap(int fromIndex, int toIndex);

Map.Entry<K, V> getEntry(int idx);
K getKey(int idx);
V getValue(int idx);

You can access the implementation of this interface at this link here I make no claims about this being the most efficient code ever, if I wanted that I would take a copy of open source of LinkedHashMap and rather than extend it I would completely re-engineer it. I wanted something simple and what I have produced is useful and just feels right to me. The LinkedHashMap also supports access-ordering, I have not considered how my enhancement impacts on this but it could be useful.

So for a simplified example of my new class, I can define a week schedule like this:

LinkedHashMapAugmented<String, String> schedule = new LinkedHashMapAugmented<String, String>();
schedule.put("SV14", "21-Sep-09");
schedule.put("0", "28-Sep-09");
schedule.put("1", "05-Oct-09");
schedule.put("2", "12-Oct-09");
schedule.put("3", "19-Oct-09");
schedule.put("CV1", "14-Dec-09");
schedule.put("11", "11-Jan-10");
schedule.put("12", "18-Jan-10");
schedule.put("13", "25-Jan-10");
schedule.put("EV1", "22-Mar-10");
schedule.put("21", "19-Apr-10");
schedule.put("22", "26-Apr-10");
schedule.put("23", "03-May-10");
schedule.put("SV1", "21-Jun-10");

If I want to get a Map containing data between the weeks labelled 21 to 23 I need only call:


As insertion-order is significant I have also implemented the ability to retrieve the Nth position of Map.Entry, key or value.

I think I have produced a simple but useful enhancement to the LinkedHashMap. I could have implemented this functionality by using some combination of existing Collections classes and arrays but this single data structure approach feels better to me. I suppose I could complete the loop by implementing a similarly enhanced version of ArrayListMultimap but I currently do not have the need!


Unknown said...

Do you still have the code? The link is broken.