Understand a hash table, the role of a hashing algorithm, how a key maps to an index, the meaning of a collision, and collision-resolution methods such as rehashing and chaining.

What this dot point is asking

AQA wants you to explain how a hash table stores and retrieves data using a hashing algorithm, define a collision, and describe collision-resolution methods such as rehashing (open addressing) and chaining.

How a hash table works

A good hash function is fast to compute, deterministic (the same key always gives the same index), distributes keys evenly across the table, and uses the whole table to minimise clustering. Poor functions that map many keys to the same region cause frequent collisions and destroy the speed advantage, so the quality of the hash function is central to performance.

Collisions

The load factor is the ratio of stored items to slots. A low load factor (a table much larger than the number of items) means few collisions and fast operations, but wastes memory; a high load factor saves memory but slows operations as more probing or longer chains are needed. Balancing this is why tables are resized.

Resolving collisions

When the load factor gets too high, the table is made larger and all items are re-inserted (resized and rehashed) to keep operations fast, because the indices depend on the table size and must be recomputed. Open addressing keeps everything in one array (good cache behaviour) but suffers clustering, where probed items pile up near a busy slot; chaining avoids clustering and can exceed the slot count, at the cost of extra memory and pointer following.

Hash tables are the standard way to implement the dictionary abstract data type, and the two topics are closely linked in the specification. The dictionary describes the behaviour (store and retrieve values by unique key); the hash table is the mechanism that makes that behaviour fast. This is also why hash tables suit any problem that needs near-instant membership testing or look-up: spell checkers store a dictionary of valid words and hash each typed word to check it in constant time, caches store recent results keyed by their inputs, and database indexes use hashing to jump straight to a record.

A limitation worth stating in an evaluation answer is that hashing destroys order. Because an item's position is determined by its hash value, the items are scattered across the array with no relationship to their keys' natural order, so a hash table cannot efficiently list its contents in sorted order or answer range queries (all keys between two bounds). When ordered output or range queries matter, a binary search tree is preferred even though its look-up is the slightly slower $O(\log n)$. Recognising this trade-off, fast unordered look-up versus slower ordered access, is exactly the kind of comparison examiners ask for.