Solid state storage devices and methods for populating a hot memory block look-up table (HBLT) are disclosed. In one such method, an indication to an accessed page table or memory map of a non-volatile memory block is stored in the HBLT. If the page table or memory map is already present in the HBLT, the priority location of the page table or memory map is increased to the next priority location. If the page table or memory map is not already stored in the HBLT, the page table or memory map is stored in the HBLT at some priority location, such as the mid-point, and the priority location is incremented with each subsequent access to that page table or memory map.