Hash TablesHow O(1) lookup actually works, and when it stops being O(1).ComputingEvery dictionary, map and set in every language is built this way.1Hash the keyA function turns the key into a large integer, deterministically.2Reduce to an indexModulo the array size gives a slot.3Handle collisionsTwo keys can land in one slot — chain them, or probe for the nextfree one.4Resize when fullPast a load factor around 0.7, allocate a bigger array and rehasheverything.WHEN IT DEGRADESMany collisions → O(n) in the worst caseResizing is O(n), but amortised across insertsA mutable key changes its hash and becomes unfindableNever mutate an object after using it as a key. Its hash changes and theentry becomes unreachable.Hash Tableslearnposters.com
Hash Tables — printable computing wall chart from LearnPosters. Free vector PDF, US Letter and A4.

Hash Tables, step by step

Every dictionary, map and set in every language is built this way.

  1. Hash the keyA function turns the key into a large integer, deterministically.
  2. Reduce to an indexModulo the array size gives a slot.
  3. Handle collisionsTwo keys can land in one slot — chain them, or probe for the next free one.
  4. Resize when fullPast a load factor around 0.7, allocate a bigger array and rehash everything.

When it degrades

  • Many collisions → O(n) in the worst case
  • Resizing is O(n), but amortised across inserts
  • A mutable key changes its hash and becomes unfindable

Never mutate an object after using it as a key. Its hash changes and the entry becomes unreachable.

Questions about the Hash Tables poster

What’s on the Hash Tables poster?
4 numbered steps, with a full worked run-through. Every dictionary, map and set in every language is built this way. Hash the key — A function turns the key into a large integer, deterministically.; Reduce to an index — Modulo the array size gives a slot.; Handle collisions — Two keys can land in one slot — chain them, or probe for the next…; Resize when full — Past a load factor around 0.7, allocate a bigger array and rehash…. Never mutate an object after using it as a key. Its hash changes and the entry becomes unreachable.
Who is the Hash Tables poster for?
Hash Tables belongs to the Computing section rather than to a school year, because computing is not something one grade owns. Anyone learning foundations can pin it up — a beginner, a student mid-course, or someone revising years later.
When should you use the Hash Tables poster?
A hash table is an array plus a function that turns a key into an index. A wall chart earns its place by being glanceable from where the work is happening, so Hash Tables belongs on the wall where that computing work actually happens, within glancing distance, rather than filed away.
What other posters go with Hash Tables?
Big-O Complexity, Binary, Hex & Decimal and Bits, Bytes & Sizes sit alongside Hash Tables in the Computing section. Printed together they make a wall rather than a single sheet, which is how a reference set actually gets used.Big-O ComplexityBinary, Hex & DecimalBits, Bytes & Sizes
Is the Hash Tables poster free to download and print?
Yes. Hash Tables downloads as a free PDF with no account, no email and no watermark, like everything else in the Computing section. Print as many copies as you like for a home, a classroom, a library or a tutoring group; reselling the file is the only thing the licence rules out.Read the licence
What size does the Hash Tables poster print at?
Hash Tables is a vector PDF laid out for US Letter, and prints on A4 with Fit to page — the same file, no separate download. Because every mark on it is drawn rather than photographed, it stays sharp enlarged to A3, A2 or A1 at a copy shop. Colour carries emphasis only, so a greyscale print of Hash Tables loses nothing.Printing guide

Related posters

Charts that sit alongside Hash Tables on the same wall.

Browse every Computing poster, or start from the full catalogue.