A machine-accessible medium may contain program instructions that, when executed by a processor, may cause the processor to perform at least one operation including searching a virtual hash page table (VHPT) using a region identifier and a virtual page number of a virtual address, and a default page size corresponding to the region identifier to locate a virtual address translation in the VHPT. The operation performed may further include searching the VHPT using the region identifier, the virtual page number, and at least one utilized page size to locate a virtual address translation in the VHPT if a virtual address translation is not located during the search of the VHPT using the region identifier, virtual page number, and default page size. The operation performed may also include inserting the located virtual address translation into a translation cache once a virtual address translation is located.