Problem 73

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Hash table to store a set #2

Due: April 5
Points: 2

We want a data structure that supports the Set ADT:

• You can insert a new item in the set, which does nothing if the item is already there.
• You can test membership to find out if a given element is in the set or not.

In class we came up with the following idea: use a hash table of boolean values, initially all set to "false". When you "insert" an item $$x$$ into the set, you compute the hash value of that element $$h(x)$$, and then set the entry at position $$h(x)$$ in the hash table to "true". Testing membership of an element $$y$$ is then just looking at position $$h(y)$$ in the table and seeing whether that table entry is set to "true".

I'm going to ask some questions about this idea as a series of problems. You can turn these in all on the same page, but please number each problem very clearly if you do.

Question 2: Recall that a hash collision is when two elements, which are not equal to each other, hash to the same value. Explain the consequences (positive or negative) if (a) two inserted ellements have a hash collision, (b) two membership-tested elements have a hash collision, or (c) there is a hash collision between an inserted and a membership-tested element.