Hashed Page Tables
You'll learn how hash tables speed up the translation from virtual page numbers to physical frame numbers.
The Problem with Large Address Spaces
As address spaces grow (especially in 64-bit systems), traditional page tables become enormous. Even hierarchical page tables can require multiple memory accesses per translation. We need a faster way to find the right frame number when given a virtual page number.
How Hashed Page Tables Work
A hashed page table uses a hash function to map virtual page numbers directly to entries in a hash table. Instead of walking through multiple levels or scanning an entire inverted table, you:
- Take the virtual page number
- Apply a hash function (e.g.,
hash = vpn % table_size) - Jump directly to that hash table slot
- Find the matching entry (handling collisions via chaining)
Each hash table entry typically contains:
- The virtual page number (to verify it's the right match)
- The corresponding frame number
- Status bits (valid, dirty, etc.)
- A pointer to the next entry (for collision handling)
The Analogy
Think of a library catalog system. Instead of flipping through every card sequentially (linear page table) or following a tree of categories (hierarchical), you hash the book's ID to jump directly to the right drawer, then scan just that small drawer for your exact card.
Handling Collisions
When multiple virtual pages hash to the same slot, they're stored as a linked list (chain) at that location. You traverse the short chain comparing virtual page numbers until you find a match.
Key Takeaway: Hashed page tables use hash functions to achieve O(1) average-case lookup time for virtual-to-physical address translation, making them efficient for sparse, large address spaces with minimal memory overhead.