4.2.6-7 - FoDS (Hash Tables and Dictionaries)

Question 1

What is a hash table

Answer 1

A Data structure that creates a mapping between keys and values as pairs

Question 2

What is an abstract data type

Question 3

What are hash tables made of

Answer 3

• An array we call a hash table
• This is linked to a hash function
• Keys are inputted into the function which returns a hash value
• The hash value determines where in the hash table the value is stored

Question 4

What are some examples of hash functions

Answer 4

• Summations
• Modulus functions

Question 5

What is meant by a collision

Answer 5

• When two key values compute to the same hash

Question 6

What are the 3 ways to avoid collisions

Answer 6

• Closed Hashing
• Open Hashing
• Rehashing

Question 7

How does a Closed-Hashing work

Answer 7

When there is a collision:
- data is stored in the next available empty location in the hash table
- The original location points to the next location