Hash tables

Overview

Recall questions on hashing algorithms, working out where a key is stored, why collisions are unavoidable, and how rehashing resolves them.

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 creates a mapping between keys and values. It stores items in an array of slots, and the position of each item is calculated directly from its key by a hashing algorithm, so an item can be found without searching through the other items.

2. 2

   What is a hashing algorithm?

   Model answer

   An algorithm that takes a key and calculates from it an integer, the hash, which is used as the index of the slot in the table where the item associated with that key is stored. The same key always produces the same hash, and the hash must always fall within the range of valid indices for the table.

3. 3

   Give four typical uses of a hash table.

   Model answer

   Indexing records in a database so a record can be retrieved directly from its key rather than by searching. Storing a compiler's symbol table, so the details of an identifier can be looked up quickly. Implementing a dictionary or associative array in a programming language. Caching, where a page or result is stored under a hash of its address.

4. 4

   A hash table has 10 slots, indices 0 to 9, and uses h(k) = k MOD 10. Where are the keys 27, 13 and 82 stored?

   Model answer

   27 MOD 10 = 7, so the item with key 27 goes in slot 7. 13 MOD 10 = 3, so key 13 goes in slot 3. 82 MOD 10 = 2, so key 82 goes in slot 2.

5. 5

   Apply the hashing algorithm 'sum the ASCII codes of the characters, then take the result MOD 10' to the key CAT.

   Model answer

   C is 67, A is 65 and T is 84, so the sum is 67 + 65 + 84 = 216. 216 MOD 10 = 6, so the item with key CAT is stored in slot 6.

6. 6

   What is a collision?

   Model answer

   A collision occurs when two different key values compute the same hash, so the hashing algorithm sends both items to the same slot in the table. Only one item can occupy a slot, so the table must have a strategy for dealing with the second.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.