Hash Tables

Question 1

Direct hashing

Answer 1

Overwrites data when a collision is found

Question 2

Code for direct hashing

Question 3

Separate chaining

Answer 3

Each cell of the hash table points to a linked list of records that have the same hash function value

Question 4

Code for separate chaining

Question 5

Linear probing

Answer 5

Linear probe for the next available index

Formula:

Question 6

Linear probing code

Question 7

Quadratic probing

Answer 7

When a collision occurs, we iterate with i^2 to look for the next available slot in the table

Formula:

Question 8

Quadratic probing code

Question 9

Double hashing

Answer 9

When a collision happens, we use another hash function to look for an empty index

Formula:

Question 10

Code for double hashing