Back to results
US 12,603,774 B2Granted
Memory efficient hash table
AssigneeMicrosoft Technology Licensing, LLC
InventorsJonathan Jaegerman, Nathaniel Jesse Miller
Life of this patent
Estimating the term…
Abstract
The disclosure reduces a memory footprint of a hash table that employs chaining as a collision avoidance solution. The methods and systems disclosed herein enable the use of chaining collision handling while reducing a memory footprint by storing parts of a tag and a link list pointer associated with a linked list that contain useful information, without storing parts of the tag and pointer that do not contain useful information. The linked list pointer and a hash key are packed together without reducing either size, and without using additional memory overhead.
Claims20
A computerized method comprising:
- receiving a first key-value pair for a data group, the first key-value pair comprising a first key and a first value, the data group comprising a first array comprising a first plurality of buckets and a second array comprising a second plurality of buckets;
- generating a first hashed key of the first key using a hash function;
- using the first hashed key and a quantity of the first plurality of buckets, generating a first index comprising a first plurality of bits;
- selecting a group of most significant bits from the first plurality of bits of the first index to form a first tag, the first tag comprising a first quantity of bits less than a second quantity of bits in the first plurality of bits;
- receiving a second key-value pair for the data group, the second key-value pair comprising a second key and a second value;
- generating a second hashed key of the second key using the hash function;
- using the second hashed key and the quantity of the first plurality of buckets, generating a second index comprising a second plurality of bits;
- generating a second tag using the second index;
- determining that the second index is equal to the first index;
- based on determining that the second index is equal to the first index, storing the second value in the second array along with the second tag at a second address different from a first address of the first value;
- storing a third key-value pair, that results in a third index equal to the first index, in the second array along with a third tag;
- and
- forming a linked list in the second array that includes the second value.
10 more elements
A system comprising:
- a processor;
- and
- a memory having stored thereon computer-readable instructions, that when executed by the processor cause the processor to:
- receive a first key-value pair for a data group, the first key-value pair comprising a first key and a first value, the data group comprising a first array comprising a first plurality of buckets and a second array comprising a second plurality of buckets;
- generate a first hashed key of the first key using a hash function;
- using the first hashed key and a quantity of the first plurality of buckets, generate a first index comprising a first plurality of bits;
- select a group of most significant bits from the first plurality of bits to form a first tag, the first index comprising a first quantity of bits less than a second quantity of bits in the first plurality of bits;
- receive a second key-value pair for the data group, the second key-value pair comprising a second key and a second value;
- generate a second hashed key of the second key using the hash function;
- using the second hashed key and the quantity of the first plurality of buckets, generate a second index comprising a second plurality of bits;
- generate a second tag using the second index;
- determine that the second index is equal to the first index;
- based on determining that the second index is equal to the first index, store the second value in the second array along with the second tag at a second address different from a first address of the first value;
- store a third key-value pair, that results in a third index equal to the first index, in the second array along with a third tag;
- and
- form a linked list in the second array that includes the second value.
13 more elements
A computer-readable storage medium having stored thereon computer-readable instructions, that when executed by a processor cause the processor to:
- receive a first key-value pair for a data group, the first key-value pair comprising a first key and a first value, the data group comprising a first array comprising a first plurality of buckets and a second array comprising a second plurality of buckets;
- generate a first hashed key of the first key using a hash function;
- using the first hashed key and a quantity of the first plurality of buckets, generate a first index comprising a first plurality of bits;
- select a group of most significant bits from the first plurality of bits of the first index to form a first tag, the first tag comprising a first quantity of bits less than a second quantity of bits in the first plurality of bits;
- receive a second key-value pair for the data group, the second key-value pair comprising a second key and a second value;
- generate a second hashed key of the second key using the hash function;
- using the second hashed key and the quantity of the first plurality of buckets, generate a second index comprising a second plurality of bits;
- generate a second tag using the second index;
- determine that the second index is equal to the first index;
- based on determining that the second index is equal to the first index, store the second value in the second array along with the second tag at a second address different from a first address of the first value;
- store a third key-value pair, that results in a third index equal to the first index, in the second array along with a third tag;
- and
- form a linked list in the second array that includes the second value.
10 more elements
Dependencies are inferred from the claim text.