a hashed page table
Suppose you keep contacts not as a giant numbered list with one slot per possible name, but as a set of small buckets: you run each name through a fixed rule (a hash) that picks a bucket, then store the contact there. To find someone, run the same rule, go to that bucket, and scan the few entries in it. A HASHED PAGE TABLE organises translations the same way: instead of one slot per page (most of them empty for a sparse space), it hashes the page number to a bucket and stores only the translations that actually exist.
Mechanically, the hardware or OS takes the virtual page number and feeds it through a HASH FUNCTION that produces an index into a hash table. Each slot of the hash table points to a CHAIN (a small linked list) of records, because two different page numbers can hash to the same slot — a collision. Each record in the chain holds a page number, its frame number, and a pointer to the next record. To translate, the hardware hashes the page number, walks down the chain at that slot comparing the stored page number against the one it wants, and on a match returns the frame. Because the table holds entries only for pages that are actually mapped, its size grows with USED pages, not with the size of the address space — which is the whole point for very large, sparse spaces. This approach is especially common on systems with address spaces larger than 32 bits, where a flat or even multi-level table would be unwieldy.
Hashed page tables matter because they handle large, sparse address spaces compactly without a deep multi-level walk. The honest caveats: lookups require comparing the full page number (a flat table never has to, since the index IS the page number), and collisions mean a lookup may have to scan several records, so worst-case time depends on chain length and a good hash function. A variant, the clustered page table, stores several consecutive pages per entry to cut chain traversals. As always, the TLB still catches most accesses, so the hash walk only runs on a miss.
To translate virtual page 0x3F2A1, the hardware computes hash(0x3F2A1) = slot 14, then walks the chain at slot 14: first record holds page 0x10000 (no match), next holds page 0x3F2A1 with frame 502 (match) — return frame 502. Pages never accessed have no record at all, so the table stays small.
Hash the page number to a bucket, then scan its chain; only mapped pages have records, so size tracks usage.
Unlike a flat table where the index IS the page number, a hashed table must compare the full page number and may scan a collision chain — so lookup time depends on the hash quality and chain length. The TLB still handles the common case; the walk runs only on a miss.