A method is disclosed for preventing compressed keys from being aliased across multiple hash tables. A special hashing technique is used to produce hash keys and compressed keys that make such aliasing avoidable. Given a first input key K, a second and different input key K′, a first hash function H0 that produces a first hash key as an index into a first hash table, a second hash function H1 that produces a second hash key as an index into a second hash table, a first compression function L0 that produces a first compressed key for the first hash table, and a second compression function L1 that produces a second compressed key for the second hash table, functions H0, H1, L0, and L1 are selected in such a way that H0(K)=H0(K′) and L0(K)=L0(K′) if and only if H1(K)=H1(K′) and L1(K)=L1 (K′).