Hashing and Hash Tables

Question 1

What is a hash table?

Answer 1

A collection of items which are stored in such a way as to make it easy to find them later.

Question 2

What is the correct name for each position within a hash table?

Answer 2

A slot.

Question 3

What is a hash function?

Answer 3

The mapping between an item and the slot where that item belongs in the hash table.

Question 4

What does the load factor refer to?

Answer 4

The number of slots within a hash table that are occupied.

Question 5

What is the calculation for the load factor?

Answer 5

Number of items divided by the hash table size.

Question 6

What does a collision or a clash refer to?

Answer 6

When two items need to be in the same slot within a hash table.

Question 7

What is a perfect hash function?

Answer 7

A hash function which maps each item into a unique slot.

Question 8

What is the complexity of search of a hash table?

Answer 8

O(1).

Question 9

What is the folding method for constructing a hash function?

Answer 9

It divides the item into equal-size pieces, which are then added together to give the resulting hash value, which is remainder divided by the size of the hash table.

Question 10

What is the mid-square method for constructing a hash function?

Answer 10

It squares the item, then extracts a portion of the resulting digits, which are then divided by the number of slots within the hash table.

Question 11

Why does the hash function have to be efficient?

Answer 11

So that it does not become the dominant part of the storage and search process.

Question 12

What does collision resolution refer to?

Answer 12

A systematic method for placing the second item of two items which have collided.

Question 13

How does open addressing work?

Answer 13

Moving through the hash table sequentially from the collision slot until we encounter the first slot that is empty.

Question 14

What is linear probing?

Answer 14

Systematically visiting each slot one at a time.

Question 15

What is a disadvantage of linear probing?

Answer 15

Clustering - the tendency for items to become clusters in the hash table.

Question 16

What can be done to mitigate the problem of clustering with linear probing?

Answer 16

Extending the technique to skip slots, such as using a ‘plus three’ probe.

Question 17

What does ‘rehashing’ refer to?

Answer 17

The process of identifying another slot after a collision has occurred.

Question 18

What is quadratic probing?

Answer 18

Instead of using a constant value, we use a rehash function that increments the has value by 1, 3, 5, etc.

Question 19

What is chaining?

Answer 19

Each slot contains a collection of items rather than a single item, which can then be searched using a suitable search method.