Resizable cache sensitive hash table
AssigneeInternational Business Machines Corporation
InventorsAamer Sachedina, Matthew A. Huras, Keriley K. Romanufa
Life of this patent
Estimating the term…
Abstract
A hash table for a collection of data items includes a set of hash buckets, each hash bucket being associated with a subset of the collection of data items, and a set of properties entries in each of the hash buckets. Each properties entry includes a pointer to an associated data item in the subset associated with the bucket and a set of representative values identifying the associated data item. A hash table can also include bucket groups defining a second level hash table to permit resizing of the hash table.
Claims45
A method for providing a hash table for a collection of data items, the method comprising:
- (a) providing a set of hash buckets in the hash table, each hash bucket being associated with a subset of the collection of data items;
- and
- (b) providing a set of properties entries in each of the hash buckets, wherein each properties entry includes a pointer to an associated data item in the subset associated with the hash bucket and a set of representative values for the associated data item, wherein the set of representative values identifies the data item.
A method for generating a hash table for a collection of data items, the method comprising:
- (a) defining a set of hash buckets;
- (b) generating, for each data item, a properties entry associated with the data item, the properties entry including representative values for the data item and a pointer to the data item;
- and
- (c) storing each properties entry in a selected one of the hash buckets in a linked list of properties entries, the selected one of the hash buckets being determined by a hash value of the data item associated with the properties entry.
A computer readable medium including program instructions to be implemented by a computer for generating and maintaining a hash table for a collection of data items, the hash table comprising a set of bucket groups and hash buckets, each bucket group comprising:
- a latch for the bucket group;
- a set of inline hash buckets;
- and
- a group header comprising a pointer definable to point to an array of overflow hash buckets.
A method for generating a hash table for a collection of data items, the hash table comprising a set of bucket groups and hash buckets, the method comprising:
- (a) defining each of the bucket groups to include a latch for the bucket group, a set of inline hash buckets, and a group header comprising a pointer definable to point to an array of overflow hash buckets;
- and
- (b) defining each hash bucket to comprise a set of properties entries, each properties entry comprising a pointer to an associated data item in the subset associated with the hash bucket and a set of representative values for the associated data item, wherein the set of representative values identifies the data item.
A method for generating and maintaining a collection of data items, the method comprising:
- (a) providing a hash table;
- and
- (b) defining hash buckets in the hash table, the hash buckets storable in alignment with cache line boundaries in a specified data cache.
A system for providing a hash table for a collection of data items, the system comprising:
- means for providing a set of hash buckets in the hash table, each hash bucket being associated with a subset of the collection of data items;
- and
- means for providing a set of properties entries in each of the hash buckets, wherein each properties entry includes a pointer to an associated data item in the subset associated with the hash bucket, and a set of representative values for the associated data item, wherein the set of representative values identifies the data item.
A computer readable medium including program-instructions to be implemented by a computer for providing a hash table for a collection of data items, the program instructions performing steps comprising:
- (a) providing a set of hash buckets in the hash table, each hash bucket being associated with a subset of the collection of data items;
- and
- (b) providing a set of properties entries in each of the hash buckets, wherein each properties entry includes a pointer to an associated data item in the subset associated with the hash bucket and a set of representative values for the associated data item, wherein the set of representative values identifies the data item.
Dependencies are inferred from the claim text.