# Homework 10: Chained Hashing

**Due: 5/11 12:30pm**

**Name & Perm #:**

**Homework buddy (leave blank if you worked alone):**

**Reading:** DS 12.3

Please also read the handout at https://cs.ucsb.edu/~richert/cs32/misc/h09-handout.pdf .

## 1. \( \)

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.

(4 pts) The phrase

**load factor**is a technical term that arises in this context. Briefly: what does this term refer to?(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.

## 2. \( \)

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.

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

(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`

(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.

## 3. (10 pts)

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.

index | list (you may need to edit this to make it longer) |
---|---|

0 | |

1 | |

2 | |

3 | |

4 |