01Overview
Hash tables appeared in 1953; linked lists entered programming practice in 1955. In 1962 B-trees were designed for large on-disk indexes and became the default structure of nearly every database. In 1972 red–black trees used colour constraints to bring the cost of a balanced tree within engineering reach.
The choice of data structure often matters more than the algorithm: contiguous arrays are cache-friendly, linked lists insert cheaply but lose locality; hash tables are O(1) on average yet face collisions and worst cases. Union–find, segment trees, skip lists and Bloom filters each solve a particular problem. Understanding their cost models is the prerequisite for writing fast code.
02History
- 1953
Hash tables
Average constant-time lookup through a hash function.
- 1962
B-trees
A multiway balanced tree designed for disk indexes.
- 1964
Union–find
Near-constant-time merging and querying of sets.
- 1972
Red–black trees
A balanced binary search tree you can actually implement.
- 1989
Skip lists
Probabilistic balance instead of strict rotations.
03Core concepts
Abstract data type
Defines a structure by its operations rather than its implementation.
Hashing and collisions
Map keys to buckets; resolve collisions with chaining or open addressing.
Balanced trees
Keep height at O(log n) with rotations or colour constraints.
04Hands-on
Do it once — it beats reading it ten times
Implement a hash table with open addressing, measure the load factor against probe count, and compare with a tree map
05Self-check
Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.
Can you explain "Abstract data type"?
Defines a structure by its operations rather than its implementation.
Can you explain "Hashing and collisions"?
Map keys to buckets; resolve collisions with chaining or open addressing.
Can you explain "Balanced trees"?
Keep height at O(log n) with rotations or colour constraints.
What problem did it solve, and why was there nothing better at the time?
Go back to the history section: how was this done before, and what did it cost?
If you had to build it today, how would you break it down?
Use the hands-on task above: write a plan of at most three steps before you start.
06Key people
Rudolf Bayer
1925 – 2013
Co-inventor of the B-tree.
Robert Tarjan
1948 –
Union–find, amortised analysis and graph algorithms.
07Further reading
- Data Structures and Algorithm Analysis
- The Algorithm Design Manual