Patent ID: 6449613
Filing Date: 2002-09-10
Classification: G06F,Y10S

Abstract:
A method of hashing a hash key into a hash table containing a set of holes uniformly distributed across the hash table to generate a hash table index used to index a hash bucket in the hash table, wherein:each of the set of holes in the hash table is followed by a contiguous region of hash buckets in the hash table; the method comprises;A) applying a first hash function to the hash key to generate a first hash index, wherein: the first hash function maps the hash key across the hash table containing the set of holes; B) testing whether the first hash index falls within a one of the set of holes in the hash table; C) applying a second hash function to the hash key to generate a second hash index when the first hash index falls within the one of the set of holes in the hash table, wherein: the second hash function maps the hash key into the contiguous region of hash buckets following the one of the set of holes in the hash table; and D) utilizing the first hash index as the hash table index when the first hash index does not fall within a one of the set of holes, and utilizing the second hash index as the hash table index when the first hash index does fall within a one of the set of holes.