Lab 19: Hash Tables

Introduction

As usual, pull the files from the skeleton and make a new IntelliJ project.

This lab is on the long side, so we’ll practice pair programming again during this lab.

In today’s lab, we’ll learn about an incredible data structure that can provide constant time insertion, removal, and containment checks. Yes, you read that correctly: constant, $\Theta(1)$ , runtime! In the best case scenario, the hash table can provide amortized constant time access to its elements regardless of whether we’re working with 10 elements, 1,000 elements, or 1,000,000 elements.

Before we jump into hash tables, we’ll first introduce a small example class, SimpleNameMap, that implements some of the basic ideas behind hash tables while incorporating the map abstract data type. Through the course of this lab, we will add new functionality to the SimpleNameMap to make it more robust. We will also analyze the SimpleNameMap to see exactly how it works and why we need to make a distinction between the best and worst case runtimes.

Finally, we’ll implement a real HashMap by generalizing the lessons we learned in the process of developing the hash table in the SimpleNameMap. Along the way, we’ll also discuss the merits and drawbacks of Java’s hashCode, or hash function, and how we can design our own hash functions.

Exercise: Fast Maps

Recall that we developed a binary search tree that acted as a Set back in lab 16 with the add and contains methods. It was certainly quite fast with $O(\log N)$ add, contains, and remove assuming a balanced tree. But we can do even better!

How can we design a constant time implementation of Map? If you’re familiar with Python, a map is like a dictionary: it provides a mapping from some key (like a word in an English dictionary) to its value (like the definition for that word). It’s similar to a Set in that keys are guaranteed to be unique.

We need to design a data structure where, no matter how many elements we insert into the Map, we can still retrieve any single element in $\Theta(1)$ time. If we were to use a binary search tree to maintain our mapping, it can take up to $O(\log N)$ time to retrieve any single element because we may need to traverse $\log N$ other nodes to reach a leaf at the bottom of the tree. Our goal, then, is to figure out how we can design a Map that does not need to consider any significant portion of other keys.

Which data structure have we seen before in class that provides constant-time access to any arbitrary element? Discuss with your partner and submit your answer to the Gradescope assessment.

Additionally, what kind of changes might we need to implement to this data structure to make it work with the Map interface? Discuss this with your partner.

A $\Theta(1)$ Implementation

We’ve seen before in class that arrays are fast. Unlike a linked list or a tree, there’s no need to traverse any part of the collection to reach an element: we can simply use bracket notation, array[i], to jump right to the i^th index in constant time.

For the most part, this works great! Consider the following implementation of a simple Map that maps first names (key) to last names (value). This Map associates a number with each key, and this number will refer to the index of the array that this key-value pair should be placed. In this scheme, we will let the first letter in each key determine its index in the final array. For example, if the key is “Alex”, the letter ‘A’ tells us that this key-value pair will map to array[0]. Listed below are our keys and values, and what index each key corresponds to:

Key	Value	Array Index
“Alex”	“Kazorian”	0
“Brandon”	“Fong”	1
“Carlo”	“Cruz-Albrecht”	2
“Jackson”	“Leisure”	9
“Kelly”	“Lin”	10
“Lauren”	“Hong”	11
“Matt”	“Owen”	12
“Neil”	“Lugovoy”	13

We can define this conversion in a hash function, whose job, when given a key, is to return a specific integer for that key. In this case, the hash function uses the first character of the name to figure out the correct integer to return.

public class String {
    public int hashCode() {
        return (int) (this.charAt(0) - 'A');
    }
 }

(We want to subtract 'A' because the ASCII table encodes the capital letter ‘A’ as starting at 65, not 0.)

When we are given this integer, we can then treat it as the index where the key-value pair should go in the array!

Now, if we were to put the key-value pairs in the array, it would look as follows (the last name values are abbreviated with the initials):

simple-name-map

Since we know exactly which index each String will map to, there’s no need to iterate across the entire array to find a single element! For example, if we put “Lauren Hong” into the map (in the map, this entry will appear as (“Lauren”, “Hong”)), we can find it later by simply indexing to array[11] because Lauren’s ‘L’ lives in the eleventh array entry. Insertion, removal, and retrieval of a single element in this map, no matter how full, will only ever take constant time because we can just index based on the first character of the key’s name.

Now that we’ve talked a little bit about this map, let’s return to hash tables. Our map above is actually implementing the foundational ideas of hash tables. Hash tables are array-backed data structures and use the integer returned by an object’s hash function to find the array index of where that object should go. In our map, we hash our key and use the return value to figure out where to put our key-value pair.

Exercise: `SimpleNameMap`

In SimpleNameMap.java, implement the array-backed data structure based on the details listed above. Fill in a constructor, add any instance variables if necessary, and implement the following methods:

boolean containsKey(String key);
String get(String key);
void put(String key, String value);
String remove(String key);

We’ve started you off with a very basic skeleton containing an Entry static nested class used to represent an entry, or key-value pair, in our map. There’s also a helper function isValidName(String key) which tells us if a given key is a valid name starting with an uppercase letter.

You may also want to write your own hash(String key) function that works like the String.hashCode() example introduced above to simplify the code you write. Remember that we need to subtract 'A' when hashing so that the zero-indexing will work correctly!

Limitations

Now that we’ve completed a basic implementation of SimpleNameMap, can you spot any problems with the design? Consider what happens if we try to add all the current staff members to the map. Below, we have a table of the name to array index mapping.

Key	Value	Array Index
“Alex”	“Kazorian”	0
“Alexander”	“Hwang”	0
“Angela”	“Kwon”	0
“Brandon”	“Fong”	1
“Carlo”	“Cruz-Albrecht”	2
“Catherine”	“Cang”	2
“Christine”	“Zhou”	2
“Jackson”	“Leisure”	9
“Joe”	“Deatrick”	9
“John”	“Xiang”	9
“Jonathan”	“Murata”	9
“Julianna”	“White”	9
“Kelly”	“Lin”	10
“Kevin”	“Chang”	10
“Lauren”	“Hong”	11
“Matt”	“Owen”	12
“Michael”	“Lum”	12
“Neil”	“Lugovoy”	13

Discussion: Not Quite Perfect

What are the drawbacks of the SimpleNameMap?

If we simply try to add all the elements in the table above to the map, what will happen?

What if we want to use lowercase letters or special characters as the first letter of the name? Or any character, ever, in any language?

And, how can we use this structure with objects other than strings?

Listed below are some of the problems that the current SimpleNameMap faces:

Collisions: Alex, Alexander, and Angela share index 0 while Carlo, Catherine, and Christine all share index 2. What happens if we need to include multiple A-names or C-names in our SimpleNameMap?
Memory inefficiency: The size of our array needs to grow with the size of the alphabet. For English, it’s convenient that we can just use the first letter of each name as the array index so we only need 26 spaces in our array. However in other languages, that might not be true. To support any possible symbol, we might need an array with a length in the thousands or millions to ensure complete compatibility, even though we may only need to store a handful of names.
Hashing: How do we generalize the indexing strategy in SimpleNameMap? The underlying principle behind hashing is that it provides a scheme for mapping an arbitrary object to an integer. For String names, we can get away with using the first character, but what about other objects? How can we reliably hash an object like a Potato?

We’ll see later that all three of these points above play a large role in the runtime and efficiency of a hash table. For the remainder of this lab, we will be extending the SimpleNameMap to workaround each of these limitations before implementing a fully-fledged HashMap that implements Map61BL.

The Hash Table

Collisions

In the previous example, the keys had mostly different values, but there were still several collisions caused by distinct keys sharing the same hash value. “Alex”, “Alexander”, and “Angela” are all distinct keys but they happen to map to the same array index, 0, just as “Carlo”, “Catherine”, and “Christine” share the index 2. Other hash functions, like one depending on the length of the first name, could produce even more collisions depending on the particular data set.

There are two common methods of dealing with collisions in hash tables, which are listed below:

Linear Probing: Store the colliding keys elsewhere in the array, potentially in the next open array space. This method is rarely used in practice.
External Chaining: A simpler solution is to store all the keys with the same hash value together in a collection of their own, such as a linked list. This collection of entries sharing a single index is called a bucket.

We primarily discuss external chaining implemented using linked lists in this course. Here are the example entries from the previous step, hashed into a 26-element map of linked lists using the function based on the first letter of the string as defined earlier (the hashCode function is duplicated below for your convenience).

    public class String {
        public int hashCode() {
            return (int) (this.charAt(0) - 'A');
        }
    }

simple-name-map-external-chaining

Inserting ("Christine", "Zhou") into this map after previously inserting ("Catherine", "Cang") appends Christine’s entry to the end of the linked list.

Exercise: External Chaining

Discussion 1: Step-by-Step Process

What happens if we were to insert the following sequence of key-value entries?

("Matt", "Owen"), ("Alexander", "Hwang"), ("Angela", "Kwon"), ("Alex",
"Kazorian"), ("Michael", "Lum"), ("Matt", "Owen")    

Discuss with your partner and try to come up with and describe the step-by-step process in as much detail as you can. It may help to draw out the hash map as you are inserting the elements into it!

Exercise 1: Runtime

Now, a bit of runtime analysis! Assume for a moment that all of the keys in the map have different hash codes and, as a result, end up in different indices in the array. What is the worst case runtime of getting a key with respect to the total number of keys, $N$ , in the map, and why?

An example input might look like: ("Brandon", "Fong"), ("Kevin", "Chang"), ("Neil", "Lugovoy"), ("Lauren", "Hong").

Discuss with your partner, then submit your answer to the Gradescope assessment. Make sure you understand why the runtime is what it is!

Exercise 2: Runtime

Now, assume instead that all the keys in the map happen to have the same hash code (despite being different keys), and they end up in the same bucket. For example, suppose all our keys begin with the letter ‘J’. If we add external chaining, what is the worst case runtime of getting a key with respect to the total number of keys, $N$ , in the map, and why?

An example input might look like: ("Jackson", "Leisure"), ("Jonathan", "Murata"), ("John", "Xiang"), ("Julianna", "White")

Once again, discuss with your partner, and then submit your answer to the Gradescope assessment. Make sure you understand why the runtime is what it is!

Exercise 3: External Chaining Implementation

First, switch which partner is coding for this part of the lab. Then, let’s add external chaining to our SimpleNameMap.

To implement external chaining, we can use Java’s LinkedList class. You’ll need to put in a little work to get it working with Java arrays, so see this StackOverflow post and this one as well for workarounds.

In addition, make changes to the following functions to support external chaining:

boolean containsKey(String key);
String get(String key);
void put(String key, String value);
String remove(String key);

Remember that any class that implements Map cannot contain duplicate keys.

Reasonably-Sized Maps

Another issue that we discussed is memory inefficiency: for a small range of hash values, we can get away with an array that individuates each hash value. This works well if our indices are small and close to zero. But remember that Java’s 32-bit integer type can support numbers anywhere between -2,147,483,648 and 2,147,483,647. Now, most of the time, our data won’t use anywhere near that many values. But even if we only wanted to support special characters, our array would still need to be 1,112,064 elements long!

Instead, we’ll slightly modify our indexing strategy. Let’s say we only want to support an array of length 10 so as to avoid allocating excessive amounts of memory. How can we turn a number that is potentially millions or billions large into a value between 0 and 9, inclusive?

The modulo operator allows us to do just that. The result of the modulo operator is like a remainder. For example, 65 % 10 = 5 because, after dividing 65 by 10, we are left with a remainder of 5. Note that you can read the expression as “65 mod 10”. Thus, 3 % 10 = 3, 20 % 10 = 0, and 19 % 10 = 9. Returning to our original problem, we want to be able to convert any arbitrary number to a value between 0 and 9, inclusive. Given our discussion on the modulo operator, we can see that any number mod 10 will return an integer value between 0 and 9. This is exactly what we need to index into an array of size 10!

More generally, we can locate the correct index for any key with the following.

Math.floorMod(key.hashCode(), array.length)

In Java, the floorMod function will perform the modulus operation while correctly accounting for negative integers.

Exercise: Modulo

Make changes to the following functions to support modulo.

boolean containsKey(String key);
String get(String key);
void put(String key, String value);
String remove(String key);

Hashing

Hash Functions

The idea underlying hashing is the transformation of any object into a number. If this transformation is fast and different keys transform into different values, then we can convert that number into an index and use that index to index into the array. This will allow us to approximate the direct, constant-time access that an array provides, resulting in near constant-time access to elements in our hash table.

The transforming function is called a hash function, and the int return value is the hash value. In Java, hash functions are defined in the object’s class as a method called hashCode with return value int. The built-in String class, for example, might have the following code.

public class String {
    public int hashCode() {
        ...
    }
}

This way, we can simply call key.hashCode() to generate an integer hash code for a String instance called key.

Exercise: `hashCode`

First, switch which partner is coding for this part of the lab. Then, modify our SimpleNameMap so that, instead of using the first character as the index, we instead use key’s hashCode method.

Make changes to the following functions to support hashCode.

boolean containsKey(String key);
String get(String key);
void put(String key, String value);
String remove(String key);

Note that, to use hashCode results as an index, we must convert the returned hash value to a valid index. Because hashCode can return negative values, use the floorMod operation discussed above!

Discussion: Collisions

We learned earlier that collisions are troublesome: exactly how many collisions occur defines the difference between a pretty good runtime, and a not so good runtime. To reduce collisions and distribute entries throughout the map, our hash function should return distinct values for different keys.

Given the following dataset, compare the first-letter hash function we defined earlier against the results of Java’s String.hashCode.

Key	First	First % 10	`hashCode`	`hashCode % 10`	`hashCode % 26`
“Alex”	0	0	2043454	4	10
“Alexander”	0	0	696546630	0	0
“Angela”	0	0	1965651104	4	14
“Brandon”	1	1	1802382214	4	22
“Carlo”	2	2	64878647	7	15
“Catherine”	2	2	641034271	1	7
“Christine”	2	2	1235314147	7	15
“Jackson”	9	9	172446413	3	9
“Joe”	9	9	74656	6	10
“John”	9	9	2314539	9	19
“Jonathan”	9	9	1205013639	9	11
“Julianna”	9	9	225388856	6	4
“Kelly”	10	0	72380223	3	19
“Kevin”	10	0	72389729	9	9
“Lauren”	11	1	2025971941	1	19
“Matt”	12	2	2390836	6	6
“Michael”	12	2	1575976441	1	13
“Neil”	13	3	2424122	2	12

Describe the differences. Which hash function, first letter or String.hashCode, minimizes the number of collisions? What else affects the number of collisions? Discuss this with your partner.

Load Factor

No matter what, if the underlying array of our hash table is small and we add a lot of keys to it, then we will start getting more and more collisions. Because of this, a hash table should expand its underlying array once it starts to fill up (much like how an ArrayList expands once it fills up).

To keep track of how full our hash table is, we define a load factor, the ratio of the number of entries over the total physical length of the array.

$\text{load factor} = \frac{\texttt{size()}}{\texttt{array.length}}$

For our hash table, we will define the maximum load factor that we will allow. Once the number of keys, size(), causes the ratio to exceed the specified maximum load factor, then the hash table should resize, usually by doubling the array length. Java’s default maximum load factor is 0.75 which provides a good balance between a reasonably-sized array and reducing collisions.

As an example, let’s see what happens if our hash table has an array length of 10 and currently contains 7 elements. Each of these 7 elements are hashed modulo 10 because we want to get an index within the range of 0 through 9. The current load factor is $\frac{7}{10}$ , or 0.7, just under the threshold.

If we insert one more element, we’ll have 8 elements and a load factor of 0.8. This necessitates a resize to an array of size 20. Remember that since our procedure for locating an entry in the hash table is to take the hashCode() % array.length and since our array’s length has changed from 10 to 20, all the elements in the hash table need to be relocated.

Exercise: Resizing

Update SimpleNameMap to include the automatic resizing feature described above. For the purposes of this assignment, only implement resizing upwards from smaller arrays to larger arrays. (Java’s HashMap also resizes downward if enough entries are removed from the map.)

Make changes to and add the following functions to support resizing.

void put(String key, String value);
int size();

Note: It might help to write a resize helper method instead of trying to cram all the details into put!

Exercise: `HashMap`

We’ve covered all the basics in a hash map. Now, let’s write HashMap.java! Or, rather, since we’ve already written SimpleNameMap.java, let’s just make the necessary changes to generalize the code to comply with theMap61BL interface.

First, switch which partner is coding for this portion of the lab. Then, copy SimpleNameMap.java to a file named HashMap.java and modify the type parameters everywhere in the code so that the key and value are generic types. For example, the class header might read:

public class HashMap<K, V> implements Map61BL<K, V>

In addition, modify the parameters and return values of the methods and implement the remaining functions of the Map61BL interface, listed below:

void clear();
boolean remove(K key, V value);
Iterator<K> iterator();

In implementing iterator, you may find it useful to write another inner class, as we have done in previous labs. Because remove of the Iterator interface is an optional method, the iterator does not need to have it implemented and you may throw an UnsupportedOperationException in that case.

To speed up testing, we’ve provided the full test suite in the skeleton. Our tests expect a couple of extra constructors and methods (listed below) so make sure to implement these in your HashMap as well.

/* Creates a new hash map with a default array of size 16 and load factor of 0.75. */
HashMap();

/* Creates a new hash map with an array of size INITIALCAPACITY and default load factor of 0.75. */
HashMap(int initialCapacity);

/* Creates a new hash map with INITIALCAPACITY and LOADFACTOR. */
HashMap(int initialCapacity, float loadFactor);

/* Returns the length of this HashMap's internal array. */
int capacity();

Discussion: Wrap Up

Hash Functions

Here are eleven integer keys.

10 100 32 45 58 126 1 29 200 400 15

Using what we’ve learned thus far, define a hash function that, when used with an empty chained map of size 11, produces three or fewer total collisions when the eleven keys are added to the map. Jot down your ideas or write a little pseudocode describing your function. Then, discuss your hash function with your partner and your neighbors.

Additional Miscellaneous Questions

We’ve learned that external chaining is one method for resolving collisions in our hash table. But why use a linked list? Why not use an array instead? What are the benefits and drawbacks of each?

How does the load factor play a part in this? Assuming that the keys are perfectly distributed, how many entries should be in each bucket and how does this affect the runtime?

Additionally, we forgot to put two staff members, “Kevin Lin” and “Catherine Han”, into our map! However, if we tried to put them into our map, we would override our previous entries “Kevin Chang” and “Catherine Cang”. Is it possible to modify our data structure so that both people can be in the map? What other data structures can we use so we can store all the staff members?

Discuss all these questions with your partner, and make sure to ask the lab staff if you have any questions.

Conclusion

Summary

In this lab, we learned about hashing, a powerful technique for turning a complex object like a String into a smaller, discrete value like a Java int. The hash table is a data structure which combines this hash function with the fact that arrays can be indexed in constant time. Using the hash table and the map abstract data type, we can build a HashMap which allows for amortized constant time access to any key-value pair so long as we know which bucket the key falls into.

However, we quickly demonstrated that this naive implementation has several drawbacks: collisions, memory inefficiencies, and the hash function itself. To workaround each of these challenges, we introduced three different features:

We added external chaining to solve collisions by allowing multiple entries to live in a single bucket.
To allow for smaller array sizes, we used the modulo operator to shrink hash values down to within a specified range.
Lastly, we compared the first-letter hash function to Java’s String.hashCode to see how different hash functions distributed keys and how it affects the runtime of the hash table.

In the next lab, we’ll discuss some of the finer details of hashing.

Deliverables

Complete the implementation of HashMap.java with:

external chaining,
the modulus operator,
use of the hashCode method,
resizing, and
miscellaneous methods of the Map61BL interface.

Introduction

Exercise: Fast Maps

A \Theta(1) Implementation

Exercise: SimpleNameMap

Limitations

Discussion: Not Quite Perfect

The Hash Table

Collisions

Exercise: External Chaining

Discussion 1: Step-by-Step Process

Exercise 1: Runtime

Exercise 2: Runtime

Exercise 3: External Chaining Implementation

Reasonably-Sized Maps

Exercise: Modulo

Hashing

Hash Functions

Exercise: hashCode

Discussion: Collisions

Load Factor

Exercise: Resizing

Exercise: HashMap

Discussion: Wrap Up

Hash Functions

Additional Miscellaneous Questions

Conclusion

Summary

Deliverables

A $\Theta(1)$ Implementation

Exercise: `SimpleNameMap`

Exercise: `hashCode`

Exercise: `HashMap`