Answer Happy

Problem 1 - Hash Tables (15 points) This is a subjective question (no coding required) a) Hash tables are known to provide constant expected running time to search for or insert a key. In your own words, explain how this is achieved, i.e., how is the hash-table designed to reduce the search (or insert) time from linear time to expected constant time? (Provide sufficient details and you can add hand- written sketches). b) Name one built-in type in Python that uses a hash-table implementation. c) A hash function maps a key to an integer. State whether each of the following statements is true or false for a valid (but not necessarily good) hash function: Hash (key1) is equal to Hash(key2) whenever key1 is equal to key2 Hash (key1) is not equal to Hash(key2) whenever key1 is not equal to key2 d) In the worst-case, a hash table will need linear time to search for/insert a key. Give an example implementation of the Hash function that causes this worst-time behavior.