Hash Tables

Question 1

Define Hash Table

Answer 1

data structure that implements an associative array (dictionary)

Question 2

Define Hash Function

Answer 2

algorithm that converts a hash key to a hash value

Question 3

What must a hash function have

Answer 3

• always produce the same hash value for the same key
• provide a uniform distribution of hash values
• minimise clustering
• fast to compute

Question 4

Define collision (hash table)

Answer 4

occurs when the hash function produces the same hash value for two or more keys

Question 5

Define linear probing

Answer 5

a solution to handling collisions, can probe sequentially or using an interval until an empty space is found

Question 6

Define chaining

Answer 6

a solution to handling collisions, using linked lists by storing the pointer to where the data is stored