A hash table is a commonly used data structure in computer science, allowing for fast

Chapter 1, Problem 25

(choose chapter or problem)

A hash table is a commonly used data structure in computer science, allowing for fast information retrieval. For example, suppose we want to store some peoples phone numbers. Assume that no two of the people have the same name. For each name x, a hash function h is used, letting h(x) be the location that will be used to store xs phone number. After such a table has been computed, to look up xs phone number one just recomputes h(x) and then looks up what is stored in that location. The hash function h is deterministic, since we dont want to get dierent results every time we compute h(x). But h is often chosen to be pseudorandom. For this problem, assume that true randomness is used. Let there be k people, with each persons phone number stored in a random location (with equal probabilities for each location, independently of where the other peoples numbers are stored), represented by an integer between 1 and n. Find the probability that at least one location has more than one phone number stored there.