Hash tables

Question 1

Define Hash table

Answer 1

A data structure that implements an associative array (dictionary)

Question 2

How is data stored in an associative array?

Answer 2

As a collection of key-value pairs

Question 3

What is hashing?

Answer 3

The position of the data within the array is determined by applying a hashing algorithm to the key

Question 4

What is the hashing algorithm called?

Answer 4

A hash function

Question 5

Pros of hash tables

Answer 5

Enable efficient searching

Maintaining data in a hash table is very efficient

Question 6

Why must you use an array to implement hash tables?

Answer 6

So you can access each position of the array directly by specifying the index of the position

Question 7

What are the positions within an array called?

Answer 7

Buckets

Question 8

What’s a bucket?

Answer 8

A single piece of data or complex data object stored alongside a key

Question 9

Load factor =

Answer 9

N (number of occupied buckets) / K (Number of buckets)

Question 10

What is the optimal load factor?

Answer 10

0.75

Question 11

What are the main requirements of a hash function?

Answer 11

Always produces the same hash value for the same key

Provides a uniform distribution of hash values- every value has an equal chance of being generated

Minimises clustering- keys don’t produce the same hash value

Be fast to compute

Question 12

Define a collision

Answer 12

When 2 or more different keys produce the same hash value