In one embodiment, a packet switching device comprises: a lookup chip including one or more processors and on-lookup chip memory, and off-lookup chip memory. In one embodiment, the lookup chip is configured to determine processing information for packets including performing a longest prefix match on a destination address of packets using progressive, exact matching of one or more single prefix length hash keys generated from the packets with entries in one or more hash tables until a matching hash table entry is found. The matching hash table entry is associated with particular information identifying how to process (e.g., manipulate, forward, drop) the corresponding packet. In one embodiment, entries of a hash table are distributed between said on-lookup chip memory and said off-lookup chip memory. In one embodiment, signatures of lookup keys are included in a hash table entry to quickly evaluate whether there is a match.