Saturday, February 4, 2012

The Java Collections Framework - Maps

The Collections Framework is a group of classes that allow you to group objects together in various ways and perform operations against those groupings. It is contained within the core Java API, so you don't have to install anything extra to use it. Its features are so basic and powerful that pretty much every piece of software written in Java makes use of this framework in one way or another. The framework has been around since Java 1.2 (1998) and has been improved upon with every subsequent Java release. There are four major collection types: Lists, Sets, Queues, and Maps.

The four basic collection types (List, Set, and Queue all inherit from the Collection interface).

A map is a data structure that contains a collection of key/value pairs. After the key/value pair is added to the map, the key can then be used to retrieve its corresponding value. All of the keys in a map are unique, so if the key in a key/value pair already exists in the map, adding that key/value pair to the map will just replace the existing key's value.

Implementations

The Java Collections Framework contains three main implementations of the Map interface. Much like the Set implementations (which I described in a previous blog post), they differ in how they iterate over their data.

  • HashMap - The most basic implementation. It iterates over its entries in no particular order.
  • LinkedHashMap - This implemention iterates over its entries in either (1) the order in which the entries were added to the map, with the oldest entries coming first or (2) the access time of each entry, with the least recently accessed entry coming first. The order type can be specified in the constructor and it defaults to insertion order.
  • TreeMap - This implementation iterates over its entries by the sorted order of its keys. This requires that the key class implement the Comparable interface, which defines how objects of the class are sorted. If the class does not implement this interface, then a Comparator object can be passed into the TreeMap constructor to define the sorting rules.

Example

The following example demonstrates how to use a map in the Java Collections Framework. This map will hold the names of some of the states in the United States, with the state abbreviation acting as the key.

Map<String, String> states = new HashMap<String, String>();
states.put("AZ", "Azerbaijan");
states.put("TX", "Texas");
states.put("AZ", "Arizona");
states.put("CO", "Colorado");

System.out.println(states.get("AZ"));
System.out.println(states.get("ZZ"));
for (Map.Entry<String, String> entry : states.entrySet()){
  String abbr = entry.getKey();
  String name = entry.getValue();
  System.out.println(name + " (" + abbr + ")");
}

On line 1, a new instance of HashMap is created. The classes that will be used for the keys and values are specified using generics. In this case, both the key and value are Strings.

On lines 2-5, data is added to the map. On line 4, the key is the same as the key on line 2. This will cause the key's original value of "Azerbaijan" to be replaced with "Arizona".

Line 7 shows that the value for "AZ" was indeed replaced. It will print "Arizona". Line 8 will print "null" because the key "ZZ" does not exist in the map (the get() method returns null if the key does not exist).

On lines 9-13, each key/value pair in the map is iterated over and the abbreviation (key) and full name (value) of each state is printed out. The entrySet() method is used to do this. It returns a Set object that contains all of the map's key/value pairs. Because this is a HashMap, the map entries are returned in no particular order. Other map implementations would iterate over these entries differently:

  • LinkedHashMap (insertion order): AZ, TX, CO
    The first entry to be added was "AZ", followed by "TX" and "CO". Replacing a key's value does not count as an insertion, which is why "AZ" comes before and not after "TX".
  • LinkedHashMap (access order): TX, CO, AZ
    "AZ" comes last because it was most recently accessed (on line 7).
  • TreeMap (sorted order): AZ, CO, TX
    Because the keys are Strings, they are sorted alphabetically.

3 comments:

Arthur Gonzalez said...

You made some decent points there. I looked on the internet for the issue and found most individuals will go along with with your blog.

Janeve George said...

A Nice introduction to Java Collections Framework! You might find the article on "Which Java collection to use?" interesting.

It doesn't go into depth of using each Collection class but it's sort of interesting to know some facts about them.

Michael Angstadt said...

Thanks Janeve. Nice chart. You might be interested in hearing that I did some experimenting with the performance of LinkedList vs ArrayList recently. I found that LinkedList is actually *much* slower when it comes to appending elements to the end of the list. However, LinkedList is extremely good at inserting elements at the beginning of the list (i.e. "list.add(0, obj)").

I don't know if the "Arrays" class is considered a "special purpose collection" necessary. It's more of a "helper class" because all of its methods are static. Since "Arrays" is in the chart, you should include the "Collections" class too.