A combined hash table/bucket trie technique facilitates fast, deterministic,
memory-efficient
exact match look-ups on extremely large tables. A limited number of hash keys which
collide on the same location can be stored in the hash table. If further keys collide
on the same location, a bucket trie is formed, the colliding keys are stored in
the trie, and trie traversal information is stored in the hash table. Regardless
of the number of buckets in the trie, an input key need only be compared with the
keys in one bucket to detect a stored key identical to the input key or conclude
that no stored key is identical to the input key.