You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
This lesson covers hash tables — a data structure that provides fast average-case lookup, insertion, and deletion. Hash tables are a key topic in the OCR A-Level Computer Science (H446) specification, section 1.4.
A hash table (also called a hash map) is a data structure that stores key-value pairs and uses a hash function to compute an index (position) in an underlying array where the value is stored.
| Operation | Array (unsorted) | Sorted Array | Hash Table |
|---|---|---|---|
| Search | O(n) | O(log n) | O(1) average |
| Insert | O(1) at end | O(n) shift | O(1) average |
| Delete | O(n) | O(n) shift | O(1) average |
Hash tables achieve O(1) average-case performance for all three operations — making them one of the most efficient data structures for lookup-heavy tasks.
A hash function takes a key (e.g., a string, number) and converts it into an integer index within the range of the array.
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.