Hashed page table method

A general approach for managing address spaces larger than 32 bits is to use a hashed page table with the hash values being the virtual-page number. Every entry in the hash table contains a linked list of elements that hash to the same location. Every element consists of three fields that are a) the virtual page number b) the value of the mapped page frame and c) a pointer to the next element in the linked list.

The virtual page number inside the virtual address is hashed into the hash table. The virtual page number is evaluate to field (a) in the first element in the linked list. If there is a match then the corresponding page frame (field (b)) is used to form the desired physical address. If there is no match then subsequent entries in the linked list are searched for a matching virtual page number.