Course contentsShow
← Computer Science
Lesson 1361 of 2,87231. Memory ManagementFree lesson

Hashed Page Tables

Learning how hash tables can be used to map virtual page numbers to frame numbers efficiently.

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:

  1. Take the virtual page number
  2. Apply a hash function (e.g., hash = vpn % table_size)
  3. Jump directly to that hash table slot
  4. 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.