--- title: "Hash Tables and Near-Constant Lookup" description: "A hash table calculates a key's home slot and compares keys using a collision rule. Different keys can share a home slot. With suitable capacity and good key spreading, expected lookup work stays near" 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-11-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 A hash table calculates a key's home slot and compares keys using a collision rule. Different keys can share a home slot. With suitable capacity and good key spreading, expected lookup work stays near constant. 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 how key distribution and table occupancy affect expected lookup work, including long chains and probe walks ## Lesson: Hash the key, then check for a match A hash table stores key-value pairs. A hash function gives a key a number. Its remainder after division by the table size gives the home slot. Slots run from 0 to size minus 1. Lookup starts there and compares keys using a collision rule. With the same hash rule and table size, the same key has the same home slot. Python dictionaries use hashing. **Example.** Use this practice rule: uppercase A = 1, B = 2, through Z = 26. Add a key's letter values, then take the remainder after division by the table size. In seven slots, AC has sum 4 and home slot 4. P has sum 16 and home slot 2: 16 = 2 x 7 + 2. B also has home slot 2. Different keys with the same home slot have a collision. *(drawing: This chaining example shows keys only. Slot 2's bucket contains both colliding pairs.)* Chaining stores a bucket of pairs at each slot. Here each bucket is a linked list, using the next references you have studied. A distinct colliding key joins that bucket. Lookup compares its keys until finding a match or reaching null. A bucket containing b pairs needs at most b key comparisons. Other buckets are not searched. Linear probing stores pairs in the slots. Assume no deletions here. Start at the home slot and compare any stored key. A match updates its value; an empty slot accepts a new pair. Otherwise advance one slot, wrapping from the last slot to 0. Lookup follows the same route, stopping at a match or an empty slot. Stop after one full circuit if no slot is empty; a new key then needs more capacity. *(drawing: These are successive checks in a seven-slot table. Probing wraps around and compares the actual keys.)* Treat hashing and comparing a key as fixed-cost work here. With good key spreading and suitable capacity, expected lookup work stays near constant as more pairs are stored. Crowding can lengthen chains or probe walks. Poor spreading can also cause long chains in a roomy table. One bucket holding every key may require checking them all. Hashing does not sort keys. Python dictionaries preserve insertion order during iteration. **Recap.** Calculate the home slot, then compare keys along the collision route. Key spreading and capacity affect expected lookup work. *The lesson, questions and flashcards were written for this dataset.* ## 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) ## Optional connections - [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)