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.

Problem 69

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?