--- title: "Hash Tables and Near-Constant Lookup" description: "Turning a key into a slot number with a hash function, so a value is reached by calculation instead of by searching. Two keys can land in the same slot, and the table needs a rule for what happens whe" canonical: https://lightmysky.com/learn/computing/hash-tables-and-near-constant-lookup-mt_7v94MJEdmJ source: https://lightmysky.com/learn/computing/hash-tables-and-near-constant-lookup-mt_7v94MJEdmJ.md retrieved: 2026-09-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Hash Tables and Near-Constant Lookup Turning a key into a slot number with a hash function, so a value is reached by calculation instead of by searching. Two keys can land in the same slot, and the table needs a rule for what happens when they do. Subject: Computing · Area: Algorithms & Data Structures · Ages 16 to 18 Page: https://lightmysky.com/learn/computing/hash-tables-and-near-constant-lookup-mt_7v94MJEdmJ ## Ready when they can - Apply a small hash function to several keys and place them in a table of slots - Describe one collision rule, such as chaining or probing, and run it on a clash - Explain why lookup stays close to constant time until the table gets crowded ## Lesson: Jump to the answer by calculation A hash table stores key and value pairs in a fixed row of slots. A hash function turns each key into a slot number, so lookup jumps straight to the computed slot instead of searching. The same key always lands in the same slot, which is the whole trick, and a Python dictionary you already know is exactly this structure. **Example.** Try a tiny hash by hand: add up the letter positions of a key and take the remainder after dividing by the table size. A key with hash value 10 in a 7 slot table lands in slot 3, since 10 divided by 7 leaves remainder 3. Two different keys can still land in the same slot, and that clash is called a collision. Every table needs one collision rule. Chaining keeps a small list inside each slot, so clashing keys queue up and lookup scans that short list. Linear probing instead walks forward to the next free slot on insert and repeats the same walk on lookup. Both rules find the key provided the same steps run both times. **Tip.** Lookup stays close to constant time until the table gets crowded. As slots fill, chains grow long and probe walks stretch far, so the jump stops landing near the answer. Keys also sit in scrambled order, not sorted order, which is the price paid for the speed. **Recap.** Hash the key, jump to its slot, settle clashes by one fixed rule, and keep the table roomy. ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Linked Lists and Nodes That Point](https://lightmysky.com/learn/computing/linked-lists-and-nodes-that-point-mt_HvY7_-M2Zj) - [Dictionaries: Values Found by Key](https://lightmysky.com/learn/computing/dictionaries-values-found-by-key-mt_mofpj0n5AM) ## Opens up - [Amortised Analysis](https://lightmysky.com/learn/computing/amortised-analysis-mt_1zLrl5RKGr) - [Key-Value and Document Stores](https://lightmysky.com/learn/computing/key-value-and-document-stores-mt_PfBDSgfeQX) - [Hashes, Signatures and Certificates](https://lightmysky.com/learn/computing/hashes-signatures-and-certificates-mt_qLHm767U87)