Possibility and Probability

Coding Python and making businesses…

14 October 2006

An ordered HashMap in Java

by Nick

HashMaps are pretty cool, they allow you to access you information using a “named” index. They aren’t as good/useful as Python’s dictionaries, but they are still really useful. (In Java, the key and the value have to Objects, so using primitives like int are out. Which is a bummer because while you can create an Integer out of an int, it leads to more code which looks less streamlined. Python doesn’t have this problem because everything is an Object.) It seems like I’m always using HashMaps to organize my data. The other day I ran into a situation where I needed to pull the keys from the HashMap in the same order that I put them in. I’d never run into this particular scenario before, so I didn’t really give it much thought until I kept noticing that my keys were coming out in a crazy order (i.e. not in the insert order, and not in alphabetical order either). My first thought when I need something in an ordered collection in Java is to run to the TreeMap (or TreeSet depending on the data situation). TreeMap will keep the keys sorted, so I thought all was well. When I tried it out I found out that because I was using Strings as the key, it alphabetized them, which is not what I was looking for. The data structure I was looking for is the LinkedHashMap. It keeps track of the keys based on insertion order, so that when you do a call to getKeySet(), you will get the keys back in the order you put them in. Once I started using LinkedHashMap, everything started working perfectly. Sometimes it pays to look around the API a little bit and see what all is out there. I’ve been running around the java.util package for a while now, but until this requirement came up, I’d never even given LinkedHashMap a second look. And since LinkedHashMap derives from HashMap, you can use it in the same places as you would a regular HashMap (i.e. use the Map interface in your method calls) and no one would notice the difference, other than the sorting of the keys.