A method, comprising: determining, by a packet switching device, a particular plurality of mask lengths of a particular conforming entry that matches a particular address of a packet via a lookup operation in a mask length data structure, with the mask length data structure including a plurality of stored conforming entries, with each of the plurality of stored conforming entries associated with a corresponding one or more mask lengths, but no more than a predetermined number of mask lengths, for searching an address search space, with the address search space referring to installed prefixes that can match a lookup value, with the plurality of stored conforming entries including the particular conforming entry, and with each mask length in the particular plurality of mask lengths corresponding to a searchable hash table (341, 342, 343) in the address search space; determining, by the packet switching device, an overall longest matching prefix in the address search space for the particular address, which includes: for a particular mask length in the particular plurality of mask lengths, performing a hash table lookup operation in said corresponding searchable hash table based on a hash key to identify a particular matching hash table entry storing the hash key and additionally storing one or more indications of corresponding one or more possible matching prefixes that are longer than the particular mask length, with the hash key including the particular address masked to said particular mask length, and responsive to said indications, matching the particular address against one of said possible matching prefixes to identify the overall longest matching prefix which is a longest matching prefix represented in the particular matching hash table entry; and processing, by the packet switching device, the particular packet based on processing information associated with the overall longest matching prefix. determining, by a packet switching device, a particular plurality of mask lengths of a particular conforming entry that matches a particular address of a packet via a lookup operation in a mask length data structure, with the mask length data structure including a plurality of stored conforming entries, with each of the plurality of stored conforming entries associated with a corresponding one or more mask lengths, but no more than a predetermined number of mask lengths, for searching an address search space, with the address search space referring to installed prefixes that can match a lookup value, with the plurality of stored conforming entries including the particular conforming entry, and with each mask length in the particular plurality of mask lengths corresponding to a searchable hash table (341, 342, 343) in the address search space; determining, by the packet switching device, an overall longest matching prefix in the address search space for the particular address, which includes: for a particular mask length in the particular plurality of mask lengths, performing a hash table lookup operation in said corresponding searchable hash table based on a hash key to identify a particular matching hash table entry storing the hash key and additionally storing one or more indications of corresponding one or more possible matching prefixes that are longer than the particular mask length, with the hash key including the particular address masked to said particular mask length, and responsive to said indications, matching the particular address against one of said possible matching prefixes to identify the overall longest matching prefix which is a longest matching prefix represented in the particular matching hash table entry; and processing, by the packet switching device, the particular packet based on processing information associated with the overall longest matching prefix. for a particular mask length in the particular plurality of mask lengths, performing a hash table lookup operation in said corresponding searchable hash table based on a hash key to identify a particular matching hash table entry storing the hash key and additionally storing one or more indications of corresponding one or more possible matching prefixes that are longer than the particular mask length, with the hash key including the particular address masked to said particular mask length, and responsive to said indications, matching the particular address against one of said possible matching prefixes to identify the overall longest matching prefix which is a longest matching prefix represented in the particular matching hash table entry; and processing, by the packet switching device, the particular packet based on processing information associated with the overall longest matching prefix.