Reading 07: Hash Tables, Separate Chaining

Readings

The readings for Monday, October 24 are:

1. Data Structures and Other Objects Using C++:

   • 12.2 - 12.4

Alternative

If you do not have the primary textbook, you can use the following free alternative texts instead:

1. Data Structures & Algorithm Analysis

   • 9.4 Hashing

2. Open Data Structures

   • 5.1 ChainedHashTable

3. Algorithms

   • 3.4 Hash Tables

Questions

Once you have completed the readings, answer the following questions in the reading07/README.md file in your assignments repository:

1. In the context of hash tables, what is the purpose of a hash function? That is, what is is used for?

2. In the context of hash tables, what exactly is a collision? How are collisions handled in a hash table that uses separate chaining?

3. In the context of hash tables, what constitutes a good hash function? That is, what sort of properties would we want in the hash function used in our implementation of a hash table?

4. For a hash table using separate chaining (ie. with lists for buckets), identify the average and worst case time complexities in terms of Big O for the following set operations:

   1. Search

   2. Insert

   3. Remove

   If the average and worst case time complexities are different, then explain the reason for the difference.

Submission

To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Reading 07 - TA assignment list.

$ cd path/to/repo                 # Go to your repository
$ git checkout master             # Make sure we are on master branch first
$ git pull                        # Make sure we have changes from GitLab
$ git checkout -b reading07       # Create reading07 branch
...                               # Do your work
$ git commit                      # Commit your work (can do this multiple times)
$ git push -u origin reading07    # Push branch to GitLab