4.2.6.1 Hash tables

Question 1

What is a hash table?

Answer 1

A data structure that creates a mapping between keys and values.
When we want to retrieve one record from many in a file, searching the file for the required record takes time that varies with the number of records. If we can generate a hash for the record’s key, we can use that hash value as the “address” of the record and move directly to it; this takes the same time regardless of the number of records in the file.

Question 2

What is a hashing algorithm?

Answer 2

The algorithm that produces different values. The hashing algorithm is applied to the key, the result is an index of where to store the value in an array.
Hashed values can be used to speed data retrieval, and can be used to check the validity of data.

Question 3

What is a collision?

Answer 3

the hashing algorithm might generate the same key for two different values, in which case a collision handling method is used.

Question 4

What is rehashing?

Answer 4

When there are collisions, each value in the existing table is inserted into a new table in a position determined by a new hashing algorithm. Takes more time, but creates a better table

Question 5

What is chaining?

Answer 5

When two hash keys create the same hash value we place the colliding keys in the same location, by utilising a linked list to link together all the values that match that hashing value. This is a quicker method but makes the data slower to receive as you’re creating multiple data structures.