You know those times when you find yourself from mildly to totally perplexed with the complexity of your own creation? Have you ever gotten a feeling that some more engineering would make your code much simpler, professional, and easier to maintain — and that same engineering is something you ignore?

The number of data structures a developer knows and the level of intimacy with each of them substantially impacts her or his ability to tackle problems. No matter the programming language, the more diverse is the knowledge of a developer about data structures and their intricacies, the quicker and neater the solution is!

Usually, academic “Data Structures” courses (even the advanced ones) won’t give one a full data structure toolbox for dealing with complex business applications. Moreover, even modern programming languages such as Java are not equipped with standard complex data structures, if you need them you gotta implement or import them. Actually, Java uses Red-Black trees in the java.util.TreeMap class.

This post is not a complaint on the Java Collections Framework, to me it is great as it is. If some of the lower level data structures are not available in the Java API, this means that Sun/Oracle just chose the best performing subset of data structures/algorithms possible.

What would you do if you had to categorize a tree of complex objects in Java? Would you traverse it recursively? Would that be really necessary?

Well, if you are acquainted with Apache’s Jakarta Commons Collections or the former Google Collections (now maintained in the guava-libraries project), you know where I am trying to get to. Some of the data structures found in those libraries can be excellent helpers when complexity takes over, so why reinventing the wheel and creating code that others will take ages to understand?

Knowledge on more sophisticated “data structures” and associated abstractions can greatly reduce time to solution, and eliminates the need for maintaining a good deal of code (since an library is used).

Here is an example where the use of a MultiMap is advantageous over an approach that employs Java Collections: Suppose you have a list of fruits and their respective colors and you are asked to group them by color, you could use a data structure like a 2-dimensional array or something similar to the Map> I used in Listing 1, where only Java Collections classes are used to group fruit names by color.

The code in Listing 2 also groups fruits by color, but a MultiMap implementation from Guava Libraries is used, where the “grouping behavior” is out-of-the-box, thus eliminating the need for coding it. As you may know, a MultiMap is similar to a hash table, except that hash collisions won’t replace the previous value stored under the same key.

[code language=’code’] /*
* Listing 1 – Using Java Collections API
*/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FruitColorMainList
{
enum FruitColorEnum
{
YELLOW, RED, BLACK, BLUE, GREEN, BROWN, PURPLE
}

public static void main(String[] args)
{
Map<FruitColorEnum, List<String>> fruitByColorMap = new HashMap<FruitColorEnum, List<String>>();

putFruitToGroup(fruitByColorMap, FruitColorEnum.RED, "Strawberry");
putFruitToGroup(fruitByColorMap, FruitColorEnum.BROWN, "Kiwi");
putFruitToGroup(fruitByColorMap, FruitColorEnum.GREEN, "Watermelon");
putFruitToGroup(fruitByColorMap, FruitColorEnum.RED, "Raspberry");
putFruitToGroup(fruitByColorMap, FruitColorEnum.RED, "Grape");
putFruitToGroup(fruitByColorMap, FruitColorEnum.GREEN, "Grape");
putFruitToGroup(fruitByColorMap, FruitColorEnum.PURPLE, "Grape");
putFruitToGroup(fruitByColorMap, FruitColorEnum.YELLOW, "Grape");

System.out.println("Result: "+ fruitByColorMap);
}

private static void putFruitToGroup(Map<FruitColorEnum, List<String>> fruitByColorMap, FruitColorEnum color, String name)
{
if(fruitByColorMap.containsKey(color))
fruitByColorMap.get(color).add(name);
else
{
List<String> fruitNameList = new ArrayList<String>();
fruitNameList.add(name);
fruitByColorMap.put(color, fruitNameList);
}
}
}
[/code]

Output:

Result: Resulting Map: {PURPLE=[Grape], GREEN=[Watermelon, Grape], YELLOW=[Grape], RED=[Strawberry, Raspberry, Grape], BROWN=[Kiwi]}

[code language=’java’] /*
* Listing 2 – Google Guava Libraries’ Multimap
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

import com.google.common.base.Supplier;
import com.google.common.collect.Maps;
import com.google.common.collect.Multimap;
import com.google.common.collect.Multimaps;

public class FruitColorMultiMapMain
{
enum FruitColorEnum
{
YELLOW, RED, BLACK, BLUE, GREEN, BROWN, PURPLE
}

public static void main(String[] args)
{
Multimap<FruitColorEnum, String> fruitColorMultiMap = Multimaps.newListMultimap(Maps.<FruitColorEnum, Collection<String>>newHashMap(), new Supplier<List<String>>() {
public List<String> get() {
return new ArrayList<String>();
}
});

fruitColorMultiMap.put(FruitColorEnum.RED, "Strawberry");
fruitColorMultiMap.put(FruitColorEnum.BROWN, "Kiwi");
fruitColorMultiMap.put(FruitColorEnum.GREEN, "Watermelon");
fruitColorMultiMap.put(FruitColorEnum.RED, "Raspberry");
fruitColorMultiMap.put(FruitColorEnum.RED, "Grape");
fruitColorMultiMap.put(FruitColorEnum.GREEN, "Grape");
fruitColorMultiMap.put(FruitColorEnum.PURPLE, "Grape");
fruitColorMultiMap.put(FruitColorEnum.YELLOW, "Grape");

System.out.println("Result: "+ fruitColorMultiMap);
}
}
[/code]

Output:

Result: {PURPLE=[Grape], RED=[Strawberry, Raspberry, Grape], YELLOW=[Grape], BROWN=[Kiwi], GREEN=[Watermelon, Grape]}

Pretty cool, isn’t it? Adding entries with repeated keys to a regular java.util.Map would retain only the last key/value pair put to it, whereas the Multimap approach accumulates the entries by key and later a List of values can be retrieved for a given key.

P.S.: The “*” on “Data Structure” denotes that the term was used for simplicity, since almost any Data Structure is intimately associated with at least one algorithm.