Back to results
US 8,429,143 B2Granted
Methods and systems for improving hash table performance
AssigneeInternational Business Machines Corporation
InventorsTimothy Peter Ellison, Nikola Grcevski, David Kevin Siegwart
Life of this patent
Estimating the term…
Abstract
Methods and systems for generating a hashcode for a hash table are provided to improve the hash table performance. A particular method includes receiving an input of a key; applying a hash function to the key to generate an incoming hashcode of the key; encoding a key type into the incoming hashcode to generate a first hashcode; and storing the first hashcode. A particular method includes encoding the key type into at least one bit of a bucket index portion of the incoming hashcode.
Claims20
A method, comprising:
- receiving an input of a key;
- applying a hash function to the key to generate an incoming hashcode of the key for a hash table;
- generating the incoming hashcode based on the hash function;
- determining a number of buckets in the hash table;
- applying a bucket mask based on the determined number of buckets to at least one bit of a bucket index portion of the incoming hashcode;
- determining a bucket index of the incoming hashcode based on the applied bucket mask;
- determining a data type of the key, wherein the data type of the key comprises at least one of boolean, byte, character, short, integer, or float;
- applying a data type mask based on the determined data type to the incoming hashcode by modifying at least one bit of the bucket index portion of the incoming hashcode to encode the determined data type of the key into the bucket index portion of the incoming hashcode to generate a modified incoming hashcode, wherein the bucket index portion of the incoming hashcode corresponds to at least one bit of least significant bits of the incoming hashcode, and wherein modifying the bucket index portion of the incoming hashcode to encode the determined data type of the key includes modifying at least one bit of the least significant bits of the incoming hashcode;
- generating the modified incoming hashcode based on the applied data type mask;
- and
- storing the modified incoming hashcode in a bucket of the hash table corresponding to the determined bucket index.
8 more elements
A method, comprising:
- receiving an input of a first key;
- applying a hash function to the first key to generate an incoming hashcode of the first key for a
- hash table;
- generating the incoming hashcode based on the hash function;
- determining a number of buckets in the hash table;
- applying a bucket mask based on the determined number of buckets to at least one bit of a bucket index portion of the incoming hashcode;
- determining a bucket index of the incoming hashcode based on the applied bucket mask;
- determining a data type of the first key, wherein the data type of the first key comprises at least one of boolean, byte, character, short, integer, or float;
- applying a data type mask based on the determined data type to the incoming hashcode by modifying at least one bit of the bucket index portion of the incoming hashcode to encode the determined data type of the first key into the bucket index portion of the incoming hashcode to generate a modified incoming hashcode, wherein the bucket index portion of the incoming hashcode corresponds to at least one bit of least significant bits of the incoming hashcode, and wherein modifying the bucket index portion of the incoming hashcode to encode the determined data type of the key includes modifying at least one bit of the least significant bits of the incoming hashcode;
- generating the modified incoming hashcode based on the applied data type mask;
- and
- determining if the modified incoming hashcode of the first key matches a stored hashcode of a second key.
9 more elements
A computer program product stored on a computer readable storage device comprising computer readable program instructions, the instructions executable by a processor to:
- receive an input of a key;
- apply a hash function to the key to generate an incoming hashcode of the key for a hash table;
- generate the incoming hashcode based on the hash function;
- determine a number of buckets in the hash table;
- apply a bucket mask based on the determined number of buckets to at least one bit of a bucket index portion of the incoming hashcode;
- determine a bucket index of the incoming hashcode based on the applied bucket mask;
- determine a data type of the key, wherein the data type of the key comprises at least one of boolean, byte, character, short, integer, or float;
- apply a data type mask based on the determined data type to the incoming hashcode by modifying at least one bit of the bucket index portion of the incoming hashcode to encode the determined data type of the key into the bucket index portion of the incoming hashcode to generate a modified incoming hashcode, wherein the bucket index portion of the incoming hashcode corresponds to at least one bit of most significant bits of the incoming hashcode, and wherein modifying the bucket index portion of the incoming hashcode to encode the determined data type of the key includes modifying at least one bit of the most significant bits of the incoming hashcode;
- generate the modified incoming hashcode based on the applied data type mask;
- and
- store the modified incoming hashcode in a bucket of the hash table corresponding to the determined bucket index.
8 more elements
Dependencies are inferred from the claim text.