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 LinkedHashMapAugmented.java. 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:


schedule.subMap("21","23");

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!

14 comments:

Unknown said...

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

for ict 99 said...

The effectiveness of IEEE Project Domains depends very much on the situation in which they are applied. In order to further improve IEEE Final Year Project Domains practices we need to explicitly describe and utilise our knowledge about software domains of software engineering Final Year Project Domains for CSE technologies. This paper suggests a modelling formalism for supporting systematic reuse of software engineering technologies during planning of software projects and improvement programmes in Final Year Project Centers in Chennai.

Spring Framework has already made serious inroads as an integrated technology stack for building user-facing applications. Spring Framework Corporate TRaining the authors explore the idea of using Java in Big Data platforms.
Specifically, Spring Framework provides various tasks are geared around preparing data for further analysis and visualization. Spring Training in Chennai

madin said...

replica breitling watches Shop the Swiss timepieces favored by aeronautical enthusiasts with our array of authentic, replica breitling watchespre-owned Breitling watches.

madin said...

Another Michele hit,Replica handbags the more structured Sylvie replica Gucci bags presents Gucci’s saddle-inspired red and green racing stripes – a house signature since the 1950s – in a fresh new light. Smooth leather and chunky hardware lends contemporary appeal to this instantly iconic Gucci bag.

madin said...

La marque avec le motif emblématique du crâne McQueen, réplique de alexander mcqueen y compris des pas cher homme alexander mcqueen foulards et une variété de produits avec des sacs à boucles, repousse les limites de la culture, de l'art et de la mode. En été, les entraîneurs surdimensionnés pour hommes et femmes continuent d'être les livres les plus vendus.

madin said...

Another Michele hit,Replica handbags the more structured Sylvie replica Gucci bags presents Gucci’s saddle-inspired red and green racing stripes – a house signature since the 1950s – in a fresh new light. Smooth leather and chunky hardware lends contemporary appeal to this instantly iconic Gucci bag.

madin said...

cheap Soccer Jerseys Shop a huge selection of SALE soccer cleats and shoes, jerseys, cheap winston reid Jerseys gloves, balls and more from www.2020jerseyshop.com

madin said...

Another Michele hit,Replica handbags the more structured Sylvie replica Gucci bags presents Gucci’s saddle-inspired red and green racing stripes – a house signature since the 1950s – in a fresh new light. Smooth leather and chunky hardware lends contemporary appeal to this instantly iconic Gucci bag.

madin said...

Montblanc MeisterstückClassique is not surprisingly regarded as one replica mont blanc ballpoint pen of Montblanc's top ten fountain pens, replica great characters edition and perhaps the most iconic of the Montblanc writing series. This pen is coated with precious black resin and has a bright white star badge. It is a must-have for collectors and has a well-known name, with German as a "masterpiece". Each pen has a separate serial number, which means that no two pens are the same. Similarly, each nib of Montblanc is individually stamped after manual testing by Montblanc's master craftsmen.

madin said...

Founded in 1905, Rolex watches have been in the uk replica rolex field of innovation for more than a century. The fake cosmograph daytona watches first certified precision chronograph, the first self-winding watch and the first effective waterproof case are milestones in Rolex design. Today, the Rolex brand is immediately recognized as a symbol of global reputation, luxury and innovation. Buying a Rolex watch means you are buying a watch history. Here we have a large catalog of used Rolex special watches for sale.

madin said...

replica longines watches uk have been a landmark of the industry since their brand began in 1832 in Saint-Imier. Today, replica mens longines 1832 watches the brand offers a wide variety of watches for men and women. Watches manufactured by Longines have been utilized throughout history for everything from exploration ventures to the expression of elegance. In addition to being famous for their ties to the racing and equestrian worlds, Longines watches are globally recognized for their timeless chic sophistication. we have a variety of Longines watches for sale, all new, beautiful, and guaranteed to be genuine. Even better, when shopping our Longines watches online, you know you are getting the best value. Browse our selection to find the Internet’s best Longines watch price.

madin said...

Giuseppe Zanotti shoes feature sleek, giuseppe zanotti shoes saleinnovative designs and are crafted from the cheap man giuseppe zanotti slip ons finest materials. Whether you chose elegant pumps, eye-popping platforms, or spectacularly studded sandals, you will never go unnoticed.

madin said...

Moncler S.p.A is an Italian apparel and lifestyle company, cheap moncler jackets most known for its down jackets and sportswear,replica man moncler jackets founded in 1952 by René Ramillon and André Vincent. Moncler took its name from the abbreviation of Monestier-de-Clermont, an Alpine town near Grenoble, France. Moncler is an abbreviation of Monastier de Clermont, the Alpine village where the brand was founded. Today its classic quilted down jackets with a sense of chic have made it the go-to outerwear label for active urbanites.

madin said...

Today it may be one of the biggest and most profitable luxury brands on the planet, Replica handbags a byword for indulgence from Beijing to Bond Street, replica Louis Vuiton bags but Louis Vuitton's origins are more humble, dating back to a young man who left home to make his living packing luggage for the great and the good in 19th-century Paris.