A hash table works as follows. We allocate a table of m slots. All the items...

A hash table works as follows. We allocate a table of m slots. All the items we intend to store in the table belong to a large set U of items. We adopt a function f: U ->{0,1...m-1) which maps an item to a slot.

Suppose we seek to store n items from U in a table of m slots.

(a) Suppose f maps every item in U with equal probability to one of the m slots. What is the probability, given two distinct items i1,i2∈ U, that f(i1),f(i2)?

(b) Prove that if |U| > nm, then no matter what f is, there exist n items in U all of which are mapped by f to the same slot.

Solutions

Expert Solution

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

Consider a hash table T with m=10 slots that uses open addressing with linear probing and...

Consider a hash table T with m=10 slots that uses open addressing with linear probing and the hash function h(k,i) = ((k mod m) + i) mod m, where i = 0,1,..., m-1 is the probe number. Show T after inserting keys <867,755,535,296,866,135,669,445,524>.

Consider inserting n distinct keys into a hash table with m buckets, where collisions are resolved...

Consider inserting n distinct keys into a hash table with m buckets, where collisions are resolved by chaining and simple uniform hashing applies. 1. What is the probability that none of the n keys hashed to a particular bucket? 2. What is the expected number of empty buckets? 3. What is the expected number of collisions?

Let's suppose we are pulling a box of mass m along a horizontal floor. All sides...

Let's suppose we are pulling a box of mass m along a horizontal floor. All sides of the box have the same type of surface (same coefficient of friction between any side and the floor). In one case, the contact surface is much larger (first picture) and in another, it is much smaller. Will there be any difference in the force of friction? Why?

Subjects