Searching for a path to identify where to move entries among hash tables with storage for multiple entries per bucket during insert operations
First Claim
1. A method used in storing values in hash tables for use in hash-based lookup operations, the method comprising:
- determining a first bucket within a first hash table of a plurality of hash tables based on hashing a particular data item using a first hash function, each of the plurality of hash tables including a plurality of buckets, each of the plurality of buckets sized to store a plurality of data items, the plurality of hash tables including the first hash table and a second hash table;
determining a second bucket within the second hash table based on hashing the particular data item using a second hash function;
in response to identifying that the first and second buckets are both full, performing a breadth-first search in the first and second hash tables from the first hash bucket to identify an identified bucket having space to add a data item along a path identified by said breadth-first search to the identified bucket, the breadth-first search including traversing buckets and data items stored within the first and second hash tables based on stored data items in each particular bucket encountered;
updating the first and second hash tables to move previously stored data items based on the path identified, including moving one of said previously stored data items to the identified bucket; and
adding the particular data item to the first hash bucket;
wherein said operation of updating the first and second hash tables is performed after completion of said performing said breadth-first search in the first and second hash tables.
1 Assignment
0 Petitions
Accused Products
Abstract
Entries are arranged in hash tables with storage for multiple entries per bucket with entries being shifted among hash tables to make room for entries being added. A path is determined through a search of the hash tables to identify where to move entries during insert operations among the hash tables to make room for a data item being added. Entries are moved and a data item added according to the identified path. Many different types of searches may be used, such as breadth-first, depth-first, random walk, etc. Also, a free position at the end of the path may be identified by being a bucket having a lowest occupancy level in a first predetermined number of levels of the search, a first bucket encountered having space available or an occupancy level less than a predetermined threshold level, with the predetermined threshold level typically being less than that of a full bucket, etc.
-
Citations
36 Claims
-
1. A method used in storing values in hash tables for use in hash-based lookup operations, the method comprising:
-
determining a first bucket within a first hash table of a plurality of hash tables based on hashing a particular data item using a first hash function, each of the plurality of hash tables including a plurality of buckets, each of the plurality of buckets sized to store a plurality of data items, the plurality of hash tables including the first hash table and a second hash table; determining a second bucket within the second hash table based on hashing the particular data item using a second hash function; in response to identifying that the first and second buckets are both full, performing a breadth-first search in the first and second hash tables from the first hash bucket to identify an identified bucket having space to add a data item along a path identified by said breadth-first search to the identified bucket, the breadth-first search including traversing buckets and data items stored within the first and second hash tables based on stored data items in each particular bucket encountered; updating the first and second hash tables to move previously stored data items based on the path identified, including moving one of said previously stored data items to the identified bucket; and adding the particular data item to the first hash bucket; wherein said operation of updating the first and second hash tables is performed after completion of said performing said breadth-first search in the first and second hash tables. - View Dependent Claims (2, 3, 4)
-
-
5. A method used in storing values in hash tables for use in hash-based lookup operations, the method comprising:
-
performing a breadth-first search in a plurality of hash tables to identify an identified bucket having space to add a particular data item along a path identified by said breadth-first search through the plurality of hash tables to the identified bucket, the breadth-first search including traversing buckets and data items stored within the plurality of hash tables based on stored data items in particular buckets encountered and traversing to buckets in different hash tables using corresponding hashing functions for each of the items stored in said particular buckets; updating the plurality of hash tables to move previously stored data items based on the path identified including moving one of said previously stored data items to the identified bucket; and adding the particular data item to the first bucket in the path identified; wherein said operation of updating the plurality of hash tables is performed after completion of said performing the breadth-first search in the plurality of hash tables. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12)
-
-
13. A computer-readable medium tangibly encoded thereon computer-executable instructions for performing steps used in storing values in hash tables for use in hash-based lookup operations, said steps comprising:
-
performing a breadth-first search in a plurality of hash tables to identify an identified bucket having space to add a particular data item along a path identified by said breadth-first search through the plurality of hash tables to the identified bucket, the breadth-first search including traversing buckets and data items stored within the plurality of hash tables based on stored data items in particular buckets encountered and traversing to buckets in different hash tables using corresponding hashing functions for each of the items stored in said particular buckets; updating the plurality of hash tables to move previously stored data items based on the path identified including moving one of said previously stored data items to the identified bucket; and adding the particular data item to the first bucket in the path identified; wherein said operation of updating the plurality of hash tables is performed after completion of said performing the breadth-first search in the plurality of hash tables. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
-
21. An apparatus used in storing values in hash tables for use in hash-based lookup operations, the apparatus comprising:
-
means for performing a breadth-first search in a plurality of hash tables to identify an identified bucket having space to add a particular data item along a path identified by said breadth-first search through the plurality of hash tables to the identified bucket, the breadth-first search including traversing buckets and data items stored within the plurality of hash tables based on stored data items in particular buckets encountered and traversing to buckets in different hash tables using corresponding hashing functions for each of the items stored in said particular buckets; means for updating the plurality of hash tables to move previously stored data items based on the path identified including moving one of said previously stored data items to the identified bucket; and means for adding the particular data item to the first bucket in the path identified; wherein the apparatus is configured update the plurality of hash tables after completion of the breadth-first search in the plurality of hash tables. - View Dependent Claims (22, 23, 24, 25, 26)
-
-
27. A method used in storing values in hash tables for use in hash-based lookup operations, the method comprising:
-
performing a random walk in a plurality of hash tables to identify an identified bucket having space to add a particular data item along a path identified by said random walk through the plurality of hash tables to the identified bucket, the random walk including traversing buckets and data items stored within the plurality of hash tables based on stored data items in particular buckets encountered and randomly selecting one of the data items in an encountered bucket of said particular buckets and determining a next-level bucket using hashing function corresponding to a hashing table within the plurality of hashing tables that is different than the hashing table in which said one of the data items is currently stored; updating the plurality of hash tables to move previously stored data items based on the path identified including moving one of said previously stored data items to the identified bucket; and adding the particular data item to the first bucket in the path identified; wherein said operation of updating the plurality of hash tables is performed after completion of said performing the random walk in the plurality of hash tables. - View Dependent Claims (28, 29, 30, 31, 32)
-
-
33. A method used in storing values in hash tables for use in hash-based lookup operations, the method comprising:
-
performing a multi-level search in a plurality of hash tables to identify an identified bucket having space to add a particular data item along a path identified by said multi-level search through the plurality of hash tables to the identified bucket, the multi-level search including traversing buckets and data items stored within the plurality of hash tables based on stored data items in each particular bucket encountered and traversing to buckets in different hash tables using corresponding hashing functions for each of the items stored in an encountered bucket;
wherein said identification of the identified bucket having space to add the particular data item includes comparing an occupancy level of the identified bucket with a predetermined threshold occupancy level, the predetermined threshold occupancy level being less than the maximum number of data items that can be stored by the identified bucket;updating the plurality of hash tables to move previously stored data items based on the path identified including moving one of said previously stored data items to the identified bucket; and adding the particular data item to the first bucket in the path identified; wherein said operation of updating the plurality of hash tables is performed after completion of said performing the multi-level search in the plurality of hash tables. - View Dependent Claims (34)
-
-
35. An apparatus comprising one or more processors and memory, wherein the memory stores one or more instructions that, when executed by said one or more processors, perform operations for storing values in hash tables for use in hash-based lookup operations, including storing a particular data item, said operations comprising:
-
performing a multi-level search in a plurality of hash tables for a predetermined number of levels or until a low-occupancy bucket is encountered with an occupancy level at or below a predetermined threshold occupancy level, the multi-level search including traversing buckets and data items stored within the plurality of hash tables based on stored data items in each particular bucket encountered and traversing to buckets in different hash tables using corresponding hashing functions for each of the items stored in an encountered bucket; using the low-occupancy bucket as an identified bucket or if no low-occupancy bucket was encountered in the multi-level search, then selecting a bucket with a lowest-occupancy level from the buckets encountered during said multi-level search as the identified bucket, an identified patch being defined as the path through the plurality of hash tables to the identified bucket; updating the plurality of hash tables to move previously stored data items based on the identified path including moving one of said previously stored data items to the identified bucket; and adding the particular data item to the first bucket in the identified path; wherein the apparatus is configured to perform the operation of updating the plurality of hash tables after completing the operation of said performing the multi-level search in the plurality of hash tables.
-
-
36. A method used in storing values in hash tables for use in hash-based lookup operations, including storing a particular data item, the method comprising:
-
performing a multi-level search in a plurality of hash tables for a predetermined number of levels or until a low-occupancy bucket is encountered with an occupancy level at or below a predetermined threshold occupancy level, the multi-level search including traversing buckets and data items stored within the plurality of hash tables based on stored data items in each particular bucket encountered and traversing to buckets in different hash tables using corresponding hashing functions for each of the items stored in an encountered bucket; using the low-occupancy bucket as an identified bucket or if no low-occupancy bucket was encountered in the multi-level search, then selecting a bucket with a lowest-occupancy level from the buckets encountered during said multi-level search as the identified bucket, an identified patch being defined as the path through the plurality of hash tables to the identified bucket; updating the plurality of hash tables to move previously stored data items based on the identified path including moving one of said previously stored data items to the identified bucket; and adding the particular data item to the first bucket in the identified path; wherein said operation of updating the plurality of hash tables is performed after completion of said performing the multi-level search in the plurality of hash tables.
-
Specification