Homework 10: Chained Hashing

Hash functions are used when the main objective is to make searches as fast as possible, i.e. an expected time O(1) search operation. Consider the typical process of finding an element: an O(1) hash function H(x) computed on an item x, giving some numerical location for a program to search for a value. A hash collision in a chained hash table creates a linked list of all elements that collide at any one index i.

1. (4 pts) The phrase load factor is a technical term that arises in this context. Briefly: what does this term refer to?

2. (4 pts) If something goes wrong, a chained hash strategy easily lead from an average case O(1) search operation to average case O(n) search operation. What is the circumstance in which things could go awry in this way? In other words, what is the worst-case scenario for chained hashing? Briefly describe.

Suppose that you are going to implement (without use of the STL) a chained hashing scheme for objects of class Student, using a hash over the perm number, using chained hashing. Suppose that a constant ARRAY_SIZE has been defined as the size of an array, and each element in that array should be the head of a linked list of Students that hashes to the index of that element.

1. (4 pts) Write a C++ definition for a struct that can represent a node in each of these linked lists.

2. (4 pts) Write a line of C++ that, if it appeared in the private: section of the class definition for class StudentHashTable, would represent a suitable array for the values, assuming that array was allocated on the heap in the constructor of class StudentHashtable

3. (8 pts) Write the definition of the constructor for StudentHashTable as it would appear in the .cpp file. Be sure to both allocate the space for the array on the heap, and set all of the pointers in that array to null.

Given the series of inputs [45, 7, 46, 90, 34, 6, 7, 71, 23, 24], insert each of these integers into the chained hash table below, with a hash function defined by \( H(x)= x \mod \mathit{tableSize} \). Draw in the linked lists to the right of each array index, showing a pointer to null as the end of each list. The Handout for this assignment has examples of the format we want for your answer.