Glossary · Phase 7 · Software engineering
Hash table
A structure that turns a key into a slot number, so it can store and find values in about one step. Dicts and sets use one.
How can
d["tent"]be O(1) when the dict holds a million keys? With a hash table. Think of a wall of pigeonholes in a mailroom, and a rule that turns any name into a pigeonhole number. To file or find something, you apply the rule and walk straight there.
Try it now
Each new node points at the old head, so adding at the front never moves anything. Notice the printed order: the last item added comes first.
Learn it properly
Core data structures · Arrays, linked lists, stacks, queues and the hash table behind every dict. About 35 minutes.
Other terms from the same lesson
- linked list: A chain of small objects, each holding one item and a pointer to the next one.
- queue: A line of items where the first one added is the first one removed: first in, first out.
- stack: A pile of items you add to and take from at the top only: last in, first out.
Never trained an AI?
Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account.