What is a hashed page table in OS?

Hashed page tables are a technique for structuring page tables in memory.

In a hashed page table, the virtual addresses are hashed into the hash table. Each element in the table comprises a linked list of elements to avoid collisions. The hash value used is the virtual page number, i.e., all the bits that are not part of the page offset.

Each element in the hash table has the virtual page number, the value of the mapped page, and a pointer to the next element. Hashed page tables are common in address spaces greater than 32 bits.

The virtual page number is matched against the first field, i.e., the virtual address, and if a match is found, the corresponding mapped address in the second field is used to form the desired memory address. If a match is not found, the linked list is traversed using the next pointer, until a match is found.