This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

# Hash table to store a set #1

Due: March 22
Points: 1

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.

Here is a simple idea to do this: 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?