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.

Expert Solution

Colby Messinger answered 2 years ago

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>.

Assume that you are hashing key K to a hash table of n slots (indexed from...

Assume that you are hashing key K to a hash table of n slots (indexed from 0 to n - 1). For each of the following functions h(K), answer the following question(s): 1) Is the function acceptable as a hash function (i.e., would the has program work correctly for both insertions and searches), 2) and if so, is it a good hash function? Function rand(n) returns a random integer between 0 and n - 1. Also assume k is a...

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?

Question