Problem 72

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 #1

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 1: What is the worst-case cost of insert and membership-testing in this hash-table-set?