SuperExamsSuperExams
Search papers…
Menu
DashboardBrowse papersRevision notesBooksSavedRevision packsFlashcardsMy progressAchievementsAI TutorMy classMessages
Back to dashboard

Unlock worked solutions

Step-by-step answers by examiners. From €5/mo.

Try Premium free →
← Computer Science notes
Cambridge A-Level·Computer Science·Cambridge AS & A Level Computer Science

Further Data Structures — Hash Tables & Graphs

14 min read

Hash tables and hashing functions, collisions and resolution, graphs (directed/undirected, weighted), adjacency matrix and adjacency list, and graph traversals.

Hash tables

A hash table stores key–value pairs for very fast lookup. A hash function maps a key to an index in an array (e.g. index = key MOD tableSize). Ideally lookup, insertion and deletion are close to O(1).

A collision happens when two keys hash to the same index. Resolution methods:

    Open addressing (linear probing) — if a slot is taken, try the next slot(s) until a free one is found.
    Chaining — each slot holds a linked list of all items that hashed there.

A good hash function spreads keys evenly to minimise collisions; performance degrades as the table fills (high load factor).

Hash table: key -> hash function -> index key 27 27 MOD 7 = 6 [0][1][2][3][4][5][6] = 27
The hash function maps a key to an array index for near-O(1) access; collisions need resolving.

Viewing only

This content is free to read on superexams.com and cannot be printed or downloaded.

Read the full note, free

Create a free account to read this note in full. Every free account gets 2 complete revision notes, no card needed.

Sign up free →Log in

More Computer Science notes

Information Representation

Data Compression & Encryption

Communication & Networking

Hardware & the Processor