In computer science, a hash table (or hash map) is a common data structure that allows for fast retrieval of information. For example, a retailer might use a hash table to associate a customer's phone number to their name. For each phone number $x$, the corresponding customer name is stored at memory address $h(x)$, which we will assume is an integer between 1 and 1000. The hash function $h$ is chosen to be pseudorandom, so we can assume that each phone number is equally likely to map to any address between 1 and 1000, independently of any other phone number.

One problem with hash tables is the possibility of collisions. That is, it is possible for two different phone numbers $x \neq y$ to map to the same address $h(x) = h(y)$. Suppose a retailer has 700 customers that it stores in the hash table.

  1. Find the expected number of addresses with no customer names.
  2. Find the expected number of addresses with exactly 1 customer name.
  3. Find the expected number of addresses with collisions (i.e., more than 1 name).

So I have that h(x) is the address and there are 1000 of them. Phone numbers are represented by variables x and there are 700 customers, therefore 700 phone #s.

Each name can be in any, so the total number of ways that the names can be arranged is $1000^{700}$

I am unsure on how to calculate the specific formulas for the 3 given situations. Once I get those, I know that I have to integrate p(x)*x to get the expected value.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.