Question

1. (Basic) What is the main advantage of hash tables over direct-address tables? 2. (Basic) What is the assumption of simple uniform hashing? 3. (Basic) Why the hash function h(k) = k mod 21 for some integer L is not desirable?

Answer 1

SOLUTION:

From given data,

(1)What is the main advantage of hash tables over direct-address tables.

Chaining: Unlimited number of elements are allowed in the chaining.

Unlimited numbers of collisions are possible.

Overflow Area: Provides quite fast access

Collisions do not use primary table space.

Re-Hashing: Has the edge of fast re-hashing.

Provides access through use of main table space.

2)What is the assumption of simple uniform hashing

The assumption is that in a hash table in which collisions are mostly resolved by chaining operations, the

average time for a successful search is case time ⊖(1+load factor).

As, we know that Load Factor = No. of stored elements / No. of Slots

The expected number of elements in a chain is given by this load factor with the uniform hashing method.

So the search can be at most number of elements * load factor + time taken by the hash function to hash a search

element to the given bucket which is a constant.

3) Why the hash function h(k) = k mod 2^L for some integer L is not desirable

Hash tables consist of mainly two components:

- bucket array

- hash function.

An array of size "m" (here m = 2L ) can be used to represent the dictionary. Here each entry is thought of a bucket.

The prime drawback of this is that size of bucket array is the size of set from which the key is drawn, which may be

huge.

Here, when the value of integer L is increased beyond a limit, it makes hashing operation cumbersome, inefficient

and time taking.

Hence, hash function h(k) = k mod 2L for some integer L is not desirable.

The simplest hash function which is used to limit the size of the array and to make the hashing efficient is:

h(k) = k mod m

where k can be very large, and m can be very small as we want it to be.

Please thumbs-up / vote up this answer if it was helpful. In case of any problem, please comment below. I will surely help. Down-votes are permanent and not notified to us, so we can't help in that case.