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

Due: March 22
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.

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 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 elements 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.