Address translation circuitry for translating virtual addresses to physical addresses for a data processor in response to access requests from said data processor targeting virtual addresses is disclosed. The address translation circuitry comprises: a data store comprising a plurality of entries for storing a plurality of mappings of ranges of virtual addresses to ranges of physical addresses for said data processor and additional data associated with each of said plurality of mappings within a table; updating circuitry for updating said table in response to an access request for a virtual address that is not mapped by said table, said updating circuitry being responsive to receipt of a mapping for said virtual address to: select a plurality of entries in said table suitable for storing said received mapping; and determine one of said plurality of selected entries to be overwritten by said received mapping in dependence upon at least a portion of said additional data stored in said one of said plurality of selected entries.