1. The number of potential probe sequences when using double hashing with a tabl

Question

1. The number of potential probe sequences when using double hashing with a table with m entries (m is prime) is:

A. m(m-1) B. m!     C. O(log m)   D. m

2. The number of potential probe sequences when using linear probing with a table with m entries is:

A. O(log m) B. m     C.   m(m-1)   D.  m!

3.   Before searching for a minimum cut in a network, it is useful to do the following:

A.   Find one augmenting path.

B.   Determine the type of each edge using depth-first search.

C.   Find and record augmenting paths until none remains.

D.   Perform a breadth-first search on the input network.

Explanation / Answer

1. There is no correct option

Double hashing is a technique used to resolve the collisions in the hash table. This technique is categorised under open-addressed hash table. Open-addresed hash table means to search the empty slots by linearly in the array. Double hashing uses two hash-functions to search the empty slot to insert the value. If there is a collision by the first hash function then it uses secnd hash function to determine the probe sequence to insert the value in the array. The most used first hash function is

hash1(key) = key % m (key is the value to be inserted)

if there is a collision after the hash1(key) then second hash function is used. The most used second hash function is

hash2(key) = n-(key%n) where n is a prime number less than m.

So, The number of potential probe sequence is based on the second hash function.

2. There is no correct option.

Linear probing is ouble hashing is a technique used to resolve the collisions in the hash table. This technique is categorised under open-addressed hash table. Open-addresed hash table means to search the empty slots by linearly in the array. The difference in linear probing and double hashing is double hashing requires 2 hash functions whereas linear probing requires only one hash function. In linaer probing If there is collision in the hash function then it will search linearly from the point of collision one by one if the slot is empty or not. If the next slot is empty then it will fill the slot otherwise it will jump to the next slot and so on. If the end of the table is reached then it will jump to the beginning of the table and will search from beginning.

The most used hash function is

hash(key) = key%m where key the value to be inserted

If the hash(key) is not empty or there is collision then from the point of collision linear probing will check if the next slot is empty or not, if the next slot is empty then it will insert the key in the slot if now empty it will check the next slot and it will keep on checking the until it finds the empty slot or the collision slot. If it again reaches to the collision slot then it means the table is full.

So the number of potential probe sequence for linear probing is 1.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.