3. Hash Tables: Dealing with Collisions In a hash table, when two keys hash to the same location, we have a collision. There are multiple strategies for handling collisions: Separate chaining: each location in the table stores a chain (typically a linked list) of all keys that hashed to that location. Open addressing: each location in the table stores a key directly. In case of a collision when inserting, we probe the table to search for an available storage location. Similarly, in case of a collision when looking up a key k, we probe to search for k. Suppose our hash function is h, the size of the table is m, and we are attempting to insert or look up the key k: - Linear probing: on the ith attempt (counting from 0), we look at index (h(k)+i) Quadratic probing: on the th attempt (counting from 0), we look at index For insertion, we are searching for an empty slot to put the key in. For lookup mod m. (h(k) ) mod m. we are trying to find the key itself 3.1 You are given a hash table of size m with n inserted keys. Collisions are resolved using separate chaining. If n- 2m and the keys are not evenly distributed, what is the worst-case runtime complexity of searching for a specific key using big-O notation? Under the same conditions, except that now the keys are evenly distributed, what is the worst-case runtime complexity of searching for a specific key using big O notation? As usual, for both of the answers above, give the tightest, simplest bound. 3. Hash Tables: Dealing with Collisions In a hash table, when two keys hash to the same location, we have a collision. There are multiple strategies for handling collisions: Separate chaining: each location in the table stores a chain (typically a linked list) of all keys that hashed to that location. Open addressing: each location in the table stores a key directly. In case of a collision when inserting, we probe the table to search for an available storage location. Similarly, in case of a collision when looking up a key k, we probe to search for k. Suppose our hash function is h, the size of the table is m, and we are attempting to insert or look up the key k: - Linear probing: on the ith attempt (counting from 0), we look at index (h(k)+i) Quadratic probing: on the th attempt (counting from 0), we look at index For insertion, we are searching for an empty slot to put the key in. For lookup mod m. (h(k) ) mod m. we are trying to find the key itself 3.1 You are given a hash table of size m with n inserted keys. Collisions are resolved using separate chaining. If n- 2m and the keys are not evenly distributed, what is the worst-case runtime complexity of searching for a specific key using big-O notation? Under the same conditions, except that now the keys are evenly distributed, what is the worst-case runtime complexity of searching for a specific key using big O notation? As usual, for both of the answers above, give the tightest, simplest bound