University of Engineering and Technology
Department of Electrical Engineering
EE 234: Data Structures and Algorithms
Spring 2022
Problem Set 5 Points: 20 Date: April 10, 2022 Due: April 18, 2022
Lab
The following is a skeleton of a hash table.
class HashTable:
def __init__(self):
[Link] = 11
[Link] = [None] * [Link]
[Link] = [None] * [Link]
One list, called slots, will hold the key items and another list, called data, will hold the data values.
When we look up a key, the corresponding position in the data list will hold the associated data value.
We will treat the key list as a hash table.
Question 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 points
Please add the following methods to the HashTable class (note that the self argument is implicit
in the following definitions).
(a) put(key,val) Add a new key-value pair to the map. If the key is already in the map then
replace the old value with the new value.
(b) get(key) Given a key, return the value stored in the map or None otherwise.
(c) del(key) Delete the key-value pair from the map using a statement of the form del map[key].
(d) len() Return the number of key-value pairs stored in the map.
(e) hash function method implements the remainder method. The collision resolution tech-
nique is linear probing with a “plus 1” rehash function.
(f) In the hash table map implementation, the hash table size was chosen to be 11. If the table
gets full, this needs to be increased. Re-implement the put method so that the table will
automatically resize itself when the loading factor reaches a predetermined value (you can
decide the value based on your assessment of load versus performance).
Theory
For the problems below you may assume that the function used for linear probing is just h(x, i) =
h(x) + i (mod m) and for quadratic probing it is h(x, i) = h(x) + i2 (mod m), where m is the
size of the hash table.
Question 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 points
In hashing dynamic resizing refers to increasing/decreasing the size of the hash table based on
the load factor. Are collision resolution and dynamic resizing necessary to maintain performance
and correctness? Why?
Question 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 points
Assume that in a hash table there are n elements. Suppose you enlarge a table of size m to a
table of size m0 . What is the best time complexity for this enlargement process?
Question 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 points
Given the hash function h(x) = x (mod 1)7, and the following set of numbers as input: {133, 148, 164, 206, 96, 1
show the resulting:
(a) Hash table with chaining
(b) Open addressing hash table with linear probing
(c) Open addressing hash table with quadratic probing
Question 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 points
Consider the following hash function h(x) = x mod 11 with linear probing as the collision han-
0 1 2 3 4 5 6 7 8 9 10
dling strategy, and the current table as Do the
1 24 14 12 16 28 7 31
following:
(a) Insert x = 9 into the hash table. Show the steps.
(b) Insert x = 42 into the hash table. Show the steps.
(c) Find x = 9 in the hash table. Show the steps.
(d) Find x = 42 in the hash table. Show the steps.
(e) Delete x = 9 from the hash table. Show the steps.
(f) Find x = 42 in the hash table. Show the steps.
(g) Explain what would happen if x = 9 was deleted by leaving an empty cell, instead of leaving
a mark. Can we find x = 42 if this was the case?
Question 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 points
Questions from the book
(a) 11.2-2
(b) 11.2-3
(c) 11.4-3
(d) 11.4-4
Page 2