Practice Problems on Hashing

Insertion of keys into hash table using linear probing as collision resolution technique – In linear probing technique, collision is resolved by searching linearly in the hash table until an empty location is found. 

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table? 

• 
• 
• 
• 

What is the complexity of finding order information, such as max, min or range from a hash table?

Given the input {4371, 1323, 6173, 4199, 4344, 9679, 1989}, a fixed table size of 10, and a hash function H(X) = X mod 10, show the resulting

a.       Linear probing hash table

b.      Quadratic probing hash table

c.       Separate chaining hash table

Explain how deletion is performed in both probing and separatechaining hash tables.

What is the appropriate probing table size if the number of items inthe hash table is 10? Assume 0.7 load factor.

• 10

• 15

• 20

• 25

A hash table needs to be resized if load factor of a table exceeds 0.7. What are the important things to do when resizing a hash table?

In this type of questions, hash values are computed by applying given hash function on given keys. 

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? (GATE CS 2004) 

i. 9679, 1989, 4199 hash to the same value 

ii. 1471, 6171 hash to the same value 

iii. All elements hash to the same value 

iv. Each element hashes to a different value 

• i only 

• ii only 

• i and ii only 

• iii or iv