HashMap

The last collection class we will look at is the HashMap class. You will again learn much more about the structure of this class (and hash tables in general) in later classes, but for now, the purpose is to store information by key. For example, you might want to store information about a bunch of accounts, and you want to be able to look up information on a particular account using an account number (the key). Arrays are actually a form of this structure, but the key is always an array index. Here, we can use ANYTHING as our “lookup” key. Like with a TreeSet, this data is NOT stored in a linear way, so it will again be trickier for us to look at all the elements.

Creating a HashMap

To create a HashMap object, we do:

HashMap<keyType, valueType> name = new HashMap<keyType, valueType>();

Here, keyType is the type of the keys, valueType is the type of values that we want to store, we want to store, and name is the variable name we’re giving to this HashMap. For example, to create a HashMap that allows us to look up state names (the values) by their two-letter abbreviations (the keys), we would do:

HashMap<String, String> states = new HashMap<String, String>();

Adding elements

Once we’ve created a new HashMap object, we can add (key, value) pairs to it. This is done with the syntax:

name.put(key, value);

Where name is the name of our HashMap, key is the key for the element (and has the same type as keyType when we created it), and value is the value for the element (and has the same type as valueType from above). For example, we could add state information to our states object as follows:

states.put("KS", "Kansas");
states.put("NE", "Nebraska");
states.put("TX", "Texas");
states.put("OR", "Oregon");
states.put("AZ", “Arizona”);

Again, a HashMap does not store elements the way you would expect them to be stored in arrays (with indices corresponding to the different elements). Instead, the elements are stored in a way that makes it very fast for them to be looked up by key.

If we want to change the value associated with a particular key, we can call put with that key and just pass in a different value. It will overwrite the original value stored with that key. Note that this means that each key in a hash map must be unique.

Looking up elements

Once we’ve created and filled a HashMap, we can look up the values by key.

valueType val = name.get(key);

Where name is the name of our HashMap, key is the key for the element we’re looking up (and has the same type as keyType when we created it), and valueType is the type of values that are stored. For example, we could get back state names from our states object as follows:

String abbrev = states.get("KS");

Now, abbrev will be “Kansas” – the value stored with the key “KS”. If we try to get a value from a key that doesn’t exist:

String anotherAbbrev = states.get("MD");

Then we will get back null.

Getting back all elements

To get back each (key,value) pair in a HashMap, we must first get back an Iterator that lets us step through each key. We will then call get with each key to get back the corresponding values. Suppose we have the states HashMap from above. We can access and print each (key,value) pair like this:

Iterator<String> keysIt = states.keySet().iterator();
while (keysIt.hasNext()) 
{
    String curKey = keysIt.next();
    String curValue = states.get(curKey);
    System.out.printf("%s: %s%n", curKey, curValue);
}

This will print:

TX: Texas
AZ: Arizona
KS: Kansas
OR: Oregon
NE: Nebraska

Notice that this information is not being printed in the order we added it, nor is it printed in any kind of sorted order. This has to do with how things are stored in a hash map, and you will learn more about it in CIS 300. For now, just know that while getting elements out of a hash table is very fast, things are not sorted or even stored in their original order.

Using a for-each loop

We can also use a for-each loop to step through each pair in a HashMap. Here is how we could repeat the above example to print each abbreviation and corresponding state name using a for-each loop instead of an iterator:

for (String curKey : states.keySet()) 
{
    String curValue = states.get(curKey);
    System.out.printf("%s: %s%n", curKey, curValue);
}

Removing elements

We can remove elements from our HashMap by passing in the key of the (key,value) pair that we want to remove. The syntax is:

name.remove(key)

Where key is the key of the pair we wish to remove. This method does return the value associated with that key, so you can optionally store the result of the method call.

For example, we can do:

states.remove("KS");

To remove the pair (“KS”, “Kansas”) If we were to print each pair again, it would print:

TX: Texas
AZ: Arizona
OR: Oregon
NE: Nebraska

In this example, the remaining elements were shifted up to cover the hole left by “Kansas”, but this is not always the case. You should think of hash maps as storing elements in a fairly random order (it is not actually random, but it looks that way).

Seeing if a key exists

We can see if a key currently exists in our HashMap by calling the containsKey method with a particular key. This method will return true if that key does exist in the HashMap, and false otherwise. It is commonly used in an if/else statement. Here is the syntax:

boolean found = name.containsKey(key);

Where key is the key we wish to search for. For example, we can do:

if (states.containsKey("KS")) {
    //now we know the key "KS" is in our HashMap
}
else {
    //now we know the key "KS is NOT in our HashMap
}

Example: Word frequency

Finally, we will look at an application for which a hash table is appropriate. Suppose we have an input file that contains several paragraphs of text. We want to use a hash map to help count the frequency of each word in the document. Here’s how:

public void countOccurrences(String filename) 
{
    Scanner inFile = new Scanner(new File(filename));
    HashMap<String, Integer> h = new HashMap<String, Integer>();

    while (inFile.hasNext()) 
    {
        String line = inFile.nextLine();
        String delims = ",:.;()?! ";
        StringTokenizer tok = new StringTokenizer(line, delims);

        while (tok.hasMoreTokens()) 
        {
            String word = tok.nextToken();
        
            //if we haven’t seen it yet, give it a count of 1
            if (!h.containsKey(word)) 
            {
                h.put(word, 1);
            }
            else 
            {
                //otherwise, make its count one bigger
                int count = h.get(word);
                h.put(word, count+1);
            }
        }
    }   
    inFile.close();

    //now, print all the word frequencies
    for (String s : h.keySet()) 
    {
        int num = h.get(s);
        System.out.printf("%s: %d%n", s, num);
    }
}