5. (20 points) In this problem we will compute the expected average size of a chain...

 

Transcribed Image Text:

5. (20 points) In this problem we will compute the expected average size of a chain in the hash table, under the Simple Uniform Hashing assumption. The simple uniform hashing assumption states that each key is hashed into every bucket in the hash table with equal probability, regardless where any other elements have already been placed. Suppose a hash table has m buckets and n elements, and uses chaining to resolve collisions. Let n; be the number of elements in bucket i and Li be the length of the chain attached to bucket i. Define a = n n/m to be the load factor of the hash table. You may find the following equation useful: when m is large (as we always assume), (1-1) me-1. (a) What is the relation between ni and Li? (b) Show that Li = n m + No, where No is the number of empty buckets. m (c) Show that E( Li) = 1 + ea by computing the expectation of No. m =1 5. (20 points) In this problem we will compute the expected average size of a chain in the hash table, under the Simple Uniform Hashing assumption. The simple uniform hashing assumption states that each key is hashed into every bucket in the hash table with equal probability, regardless where any other elements have already been placed. Suppose a hash table has m buckets and n elements, and uses chaining to resolve collisions. Let n; be the number of elements in bucket i and Li be the length of the chain attached to bucket i. Define a = n n/m to be the load factor of the hash table. You may find the following equation useful: when m is large (as we always assume), (1-1) me-1. (a) What is the relation between ni and Li? (b) Show that Li = n m + No, where No is the number of empty buckets. m (c) Show that E( Li) = 1 + ea by computing the expectation of No. m =1