The other day, I implemented a parameterised MultiMap in Java.  In my project, however, I recently discovered that it would be nice to choose what data structures underlie the MultiMap, since you might have a preference for ordering, runtime, duplicates, etc.  So I made some minor changes that make the MultiMap significantly more powerful.

So I won’t talk about it too long, but the basic idea was that any class can extend the MultiMap class, which is now abstract.  By overriding the two methods: getNewMapInstance() and getNewPostingsInstance() you can use any combination of Maps and Collections you have available, and the MultiMap will assume the properties of those data structures.

For convenience, I’ve implemented a few permutations by default:

MultiHashMap, which uses a HashMap for the map and a HashSet for the postings.  This one gives you constant-time lookups for both the map and the postings, but guarantees no particular ordering and does not allow duplicates.

MultiTreeMap uses a TreeMap and a TreeSet, so you get logarithmic lookups, duplicate prevention, and as an added bonus, traversals are ordered by value!

MultiHashListMap and MultiTreeListMap both use LinkedLists for the postings.  This means the postings allow duplicates, and have an order related to the order in which items were inserted.  This is useful if the order of the values put to a given key really matter, and of course, if you want to allow duplicates.

Reasonably, there are other permutations, but it’s easy enough to just implement them on your own.

Here is the MultiMap0.2.jar and here is the JavaDoc.

related post

• Java Parameterised MultiMap Implementation
• College Student Starts One of the Better Pages on the Internet
• About The Kevin Dolan
• Interval Tree Java Implementation
• Frog and Scorpion Tattoo Part Two