7. Deletion with Open Addressing Hash Tables We claimed in class that a hash table using open addressing must use lazy deletion.

a) Give a short-as-possible example that demonstrates that using full deletion can lead to the hash table returning the wrong result for an operation. Make your example complete:

? Explain your hash table features, including the table size, probing strategy, and hash function.

? Give the sequence of operations and the state of the hash table after each operation.

? Demonstrate how lazy deletion leads to the correct result.

? Argue that no shorter sequence of operations can lead to the wrong result.

b) When rehashing to a larger table, do lazily-deleted items need to be included? Briefly explain.