Hashing Data Structures

Question 1

What are buckets?

Answer 1

• A file is divided into a number of buckets (usually a prime number)
• Records are stored in buckets

Question 2

What is the purpose of a hashing table?

Answer 2

Allows fast random access to <key,value> pair logical-records…

…Without any indexing overheads

Question 3

What determines the bucket location a record is stored in?

Answer 3

A hashing function

Question 4

How do hashing functions work?

Answer 4

• The function will use the key field assigned to the record
• Will return a number between 0 and the total number of buckets

Question 5

How do collisions occur?

Answer 5

When trying to store a record in a full bucket

Question 6

What are 3 methods used to minimise collisions?

Answer 6

1. Increase the number of buckets
2. Have expandable buckets that can store a flexible amount of records
3. Use overflow buckets

Question 7

What are the downsides of method 1:
Increase the number of buckets

Answer 7

• A new hashing function is needed
• All current data will need to be rehashed

Question 8

What are the downsides of method 2:
Have expandable buckets that can store a flexible amount of records

Answer 8

• Requires an in-bucket sequential search
• No longer an O(1) search

Question 9

What are the downsides of method 3:
Use overflow buckets

Answer 9

• Requires pointers from buckets to overflow area
• Increases search time

Question 10

What is the probability of a collision occurring after adding 4 records to a file with 10 buckets?

Answer 10

Probability a collision has not occurred:
(10/10) x (9/10) x (8/10) x (7/10) = 0.504

Probability a collision has occurred:
1 - 0.504 = 0.496

Question 11

What are 2 examples of hashing tables?

Answer 11

1. HashSets <u></u>
2. HashMaps <k, v>

Question 12

What is a hash table?

Answer 12

• A data structure that stores data via hashing
• The index of each element is determined by a hash code
• Hash code is calculated using a hashing function

Question 13

How to search a hash table for an object?

Answer 13

1. Compute the hash code and then reduce it to find the index/bucket.
   (Hash code MOD table size)
2. Search the elements of the bucket
3. If a match is not found, the object is not present

Question 14

What is the best case scenario when searching and storing data in a hash table?

Answer 14

• Data will be distributed evenly among buckets, so that each bucket will only store 1 item
• Time complexity O(1)

Question 15

What is the worst case scenario when searching and storing data in a hash table?

Answer 15

• All items have been stored in a single bucket
• Time complexity O(n) as it’s a sequential search through every item of data