US 10,706,101 B2Granted

Bucketized hash tables with remap entries

AssigneeAdvanced Micro Devices, Inc.

InventorsAlexander D. Breslow, Dong Ping Zhang, Nuwan S. Jayasena

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods and mechanisms for managing data in a hash table are disclosed. A computing system includes a hash table configured to store data and hash management logic. In response to receiving a request to insert data into the hash table, the hash management logic is configured to generate a first hash value by applying a first hash function to the key of the key-value pair, and identify a first bucket within the hash table that corresponds to the first hash table. If the first bucket has a slot available, store the key-value pair in the slot. If the first bucket does not have a slot available, select a first slot of the first bucket for conversion to a remap entry, store the key-value pair in a second bucket, and store information associating the key-value pair with the second bucket in the remap entry.

Claims20

Dependent claims

A system comprising:

a hash table configured to store data;
and
hash management logic coupled to the hash table;
wherein in response to receiving a request to insert a key-value pair in the hash table, the hash management logic comprises circuitry configured to:
generate a first hash value by applying a first hash function to the key of the key-value pair;
identify a first bucket within the hash table that corresponds to the first hash value;
in response to determining the first bucket has an unused slot available, store the key-value pair in the slot;
and
in response to determining the first bucket does not have an unused slot available for storing a key-value pair and no remap entries allocated in the first bucket for storing information identifying at least a second bucket are available:
select a first slot of the first bucket for conversion to a set of two or more remap entries allocated in the first bucket for storing information identifying at least the second bucket;
store the key-value pair in the second bucket;
and
store information associating the key-value pair with the second bucket in one of the remap entries of the first bucket.

10 more elements

A non-transitory computer readable storage medium storing program instructions, wherein when executed by a processor unit the instructions are executable to:

store key-value pairs in a hash table;
receive a request to insert a key-value pair in the hash table;
generate a first hash value by applying a first hash function to the key of the key-value pair;
identify a first bucket within the hash table that corresponds to the first hash value;
in response to determining the first bucket has an unused slot available, store the key-value pair in the slot;
and
in response to determining the first bucket does not have an unused slot available for storing a key-value pair and no remap entries allocated in the first bucket for storing information identifying at least a second bucket are available:
select a first slot of the first bucket for conversion to a set of remap entries allocated in the first bucket for storing information identifying at least the second bucket;
store the key-value pair in the second bucket;
and
store information associating the key-value pair with the second bucket in one of the remap entries of the first bucket.

8 more elements

Dependencies are inferred from the claim text.