receiving an input lookup key and dividing the input lookup key into a plurality of strides of stride bits, including a first stride, a second stride, and a third stride;

using the first stride to locate a first entry in a first-level stride table;

locating a second-level stride table in a plurality of second-level stride tables using a table pointer in the first entry;

compressing stride bits in the second stride using a function indicated by a compression-type field in the first entry to generate compressed second stride bits;

wherein the function is in a plurality of functions that include XOR functions that combine two or more stride bits to generate a compressed stride bit using an XOR logical function, wherein the compression-type field indicates which function in the plurality of functions to perform to generate the compressed second stride bits;

using the compressed second stride bits to locate a second entry in the second-level stride table;

locating a third-level stride table in a plurality of third-level stride tables using a table pointer in the second entry;

compressing stride bits in the third stride using a second function indicted by a compression-type field in the second entry to generate compressed third stride bits;

wherein the second function is in the plurality of functions that include XOR functions that combine two or more stride bits to generate a compressed stride bit using an XOR logical function;

using the compressed third stride bits to locate a third entry in the third-level stride table;

continuing for any other strides in the input lookup key until a final entry in a final-level stride table is located;

returning a lookup result stored in or pointed to by the final entry in the final-level stride table;

wherein the second-level stride table and the third-level stride table are compressed stride tables that have been compressed to remove invalid and empty entries, wherein a compressed stride table has 2^D entries locatable by D compressed stride bits that are compressed from S stride bits from the input lookup key;

whereby 2^S−D entries have been removed to form the compressed stride table,

whereby stride bits are compressed by functions including XOR functions before locating entries in compressed stride tables.