==============================================================================
CSC 263 Tutorial 5 Winter 2019
==============================================================================
1. Describe how to use a hash table (or a direct-address table) to solve each
of the following problems. Provide as much detail as possible about the
hash table (size, hash function if possible) and analyse the complexity of
your solution. Then, answer the following questions: Is a hash table the
best way to solve the problem? Why or why not?
(a) Given an unsorted list of the names of every student in a class (with
n students), determine if two of them have the same names.
(b) Given an unsorted list of the names of every student in a class (with
n students), return the list of names in sorted order.
Does a hash table even make sense in this situation? Discuss.
2. Recall the high-level implementation of each of the dictionary operations
for a hash table using chaining (covered in last week's lecture):
SEARCH(k):
search the linked list at T[h(k)] for k
INSERT(x):
search the linked list at T[h(x.key)] for x.key
if found:
replace old element with x
else:
insert x in a new node at the head of the linked list
DELETE(x):
search the linked list at T[h(x.key)] for x.key
if found:
remove the node with x from the linked list
In this question, you will explore "open addressing": hashing into a table
where every element is stored directly in the table (without using linked
lists at each location).
To insert into a hash table using open addressing, we examine ("probe")
different locations until we find one that is unused. The sequence of
locations examined is called a "probe sequence". Technically, the hash
function is redefined to take as input both a key and a "probe number":
h(k,i) gives the location to examine for key k and probe number i.
- For "linear probing," define h(k,i) = (h'(k) + i) mod m, where
h'(k) is an ordinary hash function.
- For "quadratic probing," define h(k,i) = (h'(k) + i^2) mod m, where
h'(k) is an ordinary hash function. It's also possible to
define a more general quadratic form but we will not study this.
- For "double hashing," define h(k,i) = (h'(k) + i h''(k)) mod m, where
h'(k) and h''(k) are two different hash functions such that h''(k) is
guaranteed to always be positive and relatively prime with m.
(a) Insert the keys 10, 22, 31, 4, 15, 28, 17, 88, 39 into a hash table
of size m = 11 using open addressing with the primary hash function
h'(k) = k mod m. Illustrate the results for linear probing, quadratic
probing, and double hashing with h''(k) = 1 + (k mod (m-1)).
(b) Write a detailed algorithm for INSERT for a hash table using open
addressing, in pseudocode. You may use h(k,i) for your hash function
without worrying about how it is implemented.
(c) Write a detailed algorithm for SEARCH for a hash table using open
addressing, in pseudocode. You may use h(k,i) for your hash function
without worrying about how it is implemented.
(d) Think about how to write DELETE for a hash table using open
addressing. Why can we not simply replace the element with NIL once we
find it? What could we do instead and how does this affect INSERT and
SEARCH? Discuss various options.