Hash Tables

So far we have used ArrayLists as our main way of storing collections of objects. ArrayLists store their elements in numerical order. We can get the elements out of the ArrayList by indexing the list with an integer. The first element is in slot 0, the second in slot 1, and so on.

Today we will look at the hash table data structure which also stores collections of objects. However the way we access individual elements is different. Instead of referencing elements by their numerical slot, we reference them with a "key".

A hash table maps keys (which could be any type) to values (which can also be any type). The key needs to uniquely reference the values they go along with. For example, we could make a hash table for storing student information. Here the keys could be the student id number, or the students netid (a String). The value could then be the Student object with all the matching student's info in it.

Java has two classes for creating hash tables. The first, called Hashtable, is older and considered legacy. We will use the newer HashMap class. The difference is that the older Hashtable class does not work as well when using multiple threads.

Creating a Hash Table

To create a hash table in Java, we will create a new HashMap object. Like ArrayList, we need to put in type information to specify what types it will store. However, with a HashMap we need two types: one for the keys and one for the values. We could use the following to make a hash table of students:


HashMap<String, Student> students = new HashMap<>();

The first type given is the type of the key. And the second is the value. So this hash table will map strings onto students. We can then add some student objects into it using the put method:


students.put("bjones18", new Student("Bob", "Jones", 87, 2.8));
students.put("cclarke3", new Student("Claire", "Clarke", 36, 3.1));

Looking Up Items

The main reason to use a hash table is so that you can easily look up information stored inside the table. The hash tables get method allows us to pass in the key and retrieve the value that is associated with it. If the key doesn't exist, it will return back null:


System.out.print("Enter a student id: ");
String id = scanner.next();

// perform the lookup
Student s = students.get(id);

If there is a student with the given id, a reference to it will be returned. Otherwise it will return null.

Other HashMap Methods

We can also call the remove method to remove a particular key from the table:


students.remove("bjones18");

Or we can call the clear method to remove all of the elements:


students.clear();

If we need to loop through the items in a hash table we can use the values or keySet methods. The first returns a collection of the values being stored and the second returns a collection of the keys. That lets us loop through either collection using a for loop:


// loop through the values
System.out.println("Students in the table:");
for (Student s: students.values()) {
    System.out.println(s);
}

// loop through the keys
System.out.println("Ids in the table:");
for (String id: students.keySet()) {
    System.out.println(id);
}