Hash tables, hashing and collisions

Overview

Hash table, term hashing algorithm and term collision.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a hash table?

   Model answer

   A hash table stores each item at a position calculated from the item's key. A hashing algorithm turns the key into that position.

2. 2

   Define the term hashing algorithm.

   Model answer

   A hashing algorithm converts a key into an index inside the table. The same key always produces the same index.

3. 3

   Give a simple hashing algorithm suitable for numeric keys.

   Model answer

   A common hashing algorithm divides the key by the table size and takes the remainder. Modulo division keeps the result inside the table.

4. 4

   Apply the hashing algorithm key MOD 10 to the key 137.

   Model answer

   The key 137 gives an index of 7. The remainder after dividing 137 by 10 is 7.

5. 5

   Why is a hash table fast to search?

   Model answer

   The index is calculated straight from the key, so one access reaches the record. Other elements do not have to be examined first.

6. 6

   Define the term collision.

   Model answer

   A collision happens when two different keys hash to the same index. Only one record can occupy that position.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.