Hash Tables

Question 1

What is a hash table?

Answer 1

A data structure, typically an array, which contains a set of unique keys, and values associated with these.

Question 2

What is the main advantage of a hash table?

Answer 2

Data can be retrieved with a constant time complexity of O(1).

Question 3

What are the steps of the hashing process?

Answer 3

1. Apply a hash algorithm to the key value.
2. The result returned will be the index of where to store the data.

Question 4

What is a collision?

Answer 4

When the hash function produces the same index for two or more keys.

This is a problem. If multiple items are attempted to be stored I. The same memory location, data will be overwritten.

Question 5

What are the solutions to dealing with collisions?

Answer 5

Solution 1: Store multiple values at the same index using a linked list.

Solution 2: Use the next available free memory location.

Solution 3: Rehash using a larger table with a different hash function.

Question 6

What are the steps involved in rehashing?

Answer 6

1. A larger hash table is created
2. Each value in the existing table is inserted into the new table
3. In a position determined by a new hashing algorithm

Question 7

What are the advantages of hash tables?

Answer 7

Faster to look up/insert a record (O(1)) compared to arrays/linked lists.

Used on large datasets where frequent access/modifications are needed.

Question 8

What are the disadvantages of hash tables?

Answer 8

Collisions require additional handling.
Data stored is unordered.
Larger amount of memory used due to need for available memory locations.

Do not use if data needs to be sorted e.g. processed in a specific order.