1 Question 4 : 5 points A closed hash table can be used as a cache in networking applications. Whenever we visit a website, our browser has to translate the domain name in the URL to an IP address in order to know the location of the website's server. Normally, our browser will ask a DNS server to find the IP address. But if we visit a webpage more than once, we can cache the IP address and avoid having to look it up in the future. Here is a hypothetical hash function for web addresses: URL Hash IP https://www.google.com/ | 0 | 172.217.15.68 https://drexel.edu 1 144.118.72.83 https://www.cnn.com 1 151.101.193.67 https://www.nytimes.com 2 151.101.201.164 https://www.amazon.com| 3 99.84.109.115 Imagine we have a router that can only remember 4 IP addresses. If the address is not in memory, we'll just request it from the DNS server. Here is what our hash table of addresses could look like: Index Value 0 (https://www.google.com/, 172.217.15.68) (https://drexel.edu, 144.118.72.83) 2 (https://www.nytimes.com, 151.101.201.164) 3 (https://www.amazon.com, 99.84.109.115) If the user visits https://www.cnn.com, the hash table must be updated. We'll replace Drexel's address with CNN's address when the collision takes place: Index Value 0 (https://www.google.com/, 172.217.15.68) 1 (https://www.cnn.com, 151.101.193.67) 2 (https://www.nytimes.com, 151.101.201.164) 3 (https://www.amazon.com, 99.84.109.115) Given the table above (with CNN at position 1), say the user visits these websites: Google, CNN, NY Times, Google, Google, Drexel, Amazon, CNN, Amazon, CNN, Drexel. (a) (1 point) How many times was the address we requested not in the cache (a cache miss)? (b) (2 points) Say the user made five requests in a row on the original table with CNN in position 1). What is the worst sequence of requests (i.e. a series of requests that would result in the most cache misses)? (c) (2 points) Hash tables are defined by their collision resolution algorithm. Our algorithm is to simply overwrite the old value on collision. Why is this acceptable for this application? When would this not be acceptable