Hash Tables

Overview

Recall questions on hash tables and hash functions, inserting with linear probing, lookup, collisions and why they are unavoidable, separate chaining and other collision strategies, load factor, performance, deletion, and when a hash table fits.

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 data structure that stores key-value pairs in an array of slots (sometimes called buckets), where the position of each item is calculated directly from its key by a hash function rather than found by searching. This lets an item be stored or retrieved by going straight to the calculated slot, which is what makes lookup so fast.

2. 2

   What does the hash function do?

   Model answer

   It takes the key and performs a calculation on it that produces an index within the range of the table, which is where that item is stored. The same key always produces the same index, so retrieval works by running the same function again and going straight to that slot. It converts a key of any form - a name, an account number, a string - into a valid array position.

3. 3

   What makes a good hash function?

   Model answer

   It must be quick to compute, since it runs on every access. It must be deterministic, always giving the same index for the same key. It must always produce an index within the table's range. Most importantly it should distribute keys as evenly as possible across all the slots, because clustering of keys into a few slots produces collisions and destroys the performance advantage.

4. 4

   Give a simple hash function and show it working.

   Model answer

   Taking the key modulo the table size is the standard simple example: index = key MOD table size. With a table of 10 slots and the key 45, the index is 45 MOD 10 = 5. For a text key you first convert it to a number, for instance by adding the character codes of its letters together, then take that total modulo the table size.

5. 5

   Insert the keys 23, 45, 12, 33 and 87 into a 10-slot hash table using index = key MOD 10, resolving collisions by linear probing. Where does each go?

   Model answer

   23 hashes to 3 and goes in slot 3. 45 hashes to 5 and goes in slot 5. 12 hashes to 2 and goes in slot 2. 33 hashes to 3, which is occupied by 23 - a collision - so linear probing moves to slot 4, which is free, and 33 is stored there. 87 hashes to 7 and goes in slot 7. Slots 0, 1, 6, 8 and 9 remain empty.

6. 6

   How do you look an item up in a hash table?

   Model answer

   Apply the hash function to the key you are searching for to get an index, then go directly to that slot. If the item there has the matching key, you have found it. If the slot is empty the item is not in the table. If a different key is there, a collision must have occurred when it was stored, so you follow the same collision-resolution strategy that was used on insertion - walking the chain, or probing on to the next slots - until you find the key or reach an empty slot.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.