hash table
A hash table stores key–value pairs so you can look a value up by its key almost instantly. The trick: feed the key to a hash function that turns it into a number, then use that number (modulo the array size) as an index into a plain array of buckets. Instead of scanning for "alice", you compute where "alice" must live and go straight there.
On average, insert, lookup, and delete are all O(1) — the hash points you to the right bucket in one step. The catch is collisions: two different keys can hash to the same bucket. Tables handle this with chaining (each bucket holds a small linked list) or open addressing (probe nearby slots). With a good hash function and a sensible load factor (it resizes when it gets too full), collisions stay rare and O(1) holds. In a bad worst case — many collisions — operations degrade to O(n).
The cost of that speed is that a hash table has no order: iterating gives keys in an arbitrary, hash-dependent sequence, and you cannot ask for "the smallest key" cheaply. When you need ordering, a balanced tree (like std::map) is the alternative; when you just need fast keyed lookup, the hash table wins.
#include <unordered_map>
#include <string>
std::unordered_map<std::string, int> age;
age["alice"] = 30; // average O(1) insert
age["bob"] = 25;
int a = age["alice"]; // average O(1) lookup -> 30
// buckets: [0] -> ...
// [3] -> ("alice",30) -> ("bob",25) <- a collision, chained
bool has = age.count("carol"); // 0 (not present)hash(key) % buckets picks a bucket; collisions chain inside it.
Average O(1) assumes a good hash function and bounded load factor; with adversarial keys or a poor hash, lookups can degrade to O(n).