Hash table to store a set #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.