# US 12,603,774 B2 · Memory efficient hash table

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,603,774 B2
- Document ID: US12603774B2
- Status: Granted
- Kind: B2
- Application number: 18/424,730
- Filed: 2024-01-26
- Published: 2025-07-31
- Granted: 2026-04-14
- Earliest claimed: 2024-01-26
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Jonathan Jaegerman; Nathaniel Jesse Miller
- Web page: https://patentgrep.com/patent/US12603774B2

## CPC

- H04L 9/14: using a plurality of keys or algorithms
- H04L 9/3242: {involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The method of claim 1, wherein generating the first index comprises performing a modulo operation with a value of the first hashed key as a numerator and the quantity of the first plurality of buckets as a denominator.

### Claim 3 (depends on 1)

The method of claim 1, wherein the quantity of the first plurality of buckets is a multiple of 2, and selecting the group of most significant bits from the first plurality of bits to form the first tag comprises:
computing a log to a base 2 value of the quantity of the first plurality of buckets;
subtracting the computed value from a maximum number of bits that a processor of a computer is capable of processing in one computing cycle to produce a first integer; and
using a value of the first integer as a number of elements in the group of the most significant bits.

### Claim 4 (depends on 3)

The method of claim 3, wherein the maximum number of bits that the processor of the computer is capable of processing in one computing cycle is 64, wherein the quantity of the first plurality of buckets is m, and the number of bits in the group of most significant bits is equal to 64-log2 m.

### Claim 5 (depends on 1)

The method of claim 1, wherein the method further comprises:
storing the first tag in a first bucket of the first plurality of buckets; and
storing the first value in the first bucket of the first plurality of buckets.

### Claim 6 (depends on 3)

The method of claim 3, wherein the method further comprises:
providing a pointer from the first array to the second array, the pointer comprising a number of bits equal to the maximum number of bits; and
storing a number of least significant bits out of the number of bits of the pointer as an effective pointer value, wherein the number of the least significant bits is equal to the computed value.

### Claim 7 (depends on 1)

The method of claim 1, wherein a ratio of occupied buckets to a total number of buckets in the second array is designated as a load factor, and wherein the first array and the second array resize when the load factor reaches a threshold value.

### Claim 8 (depends on 7)

The method of claim 7, wherein the first array and the second array resize together.

### Claim 9 (depends on 1)

The method of claim 1, wherein a quantity of the first plurality of buckets is equal to a quantity of the second plurality of buckets.

### Claim 10

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.

### Claim 11 (depends on 10)

The system of claim 10, wherein generating the first index comprises performing a modulo operation with a value of the first hashed key as a numerator and the quantity of the first plurality of buckets as a denominator.

### Claim 12 (depends on 10)

The system of claim 10, wherein the quantity of the first plurality of buckets is a multiple of 2, and selecting the group of most significant bits from the first plurality of bits to form the first tag comprises:
computing a log to a base 2 value of the quantity of the first plurality of buckets;
subtracting the computed value from a maximum number of bits that the processor is capable of processing in one computing cycle to produce a first integer; and
using a value of the first integer as a number of elements in the group of the most significant bits.

### Claim 13 (depends on 12)

The system of claim 12, wherein the maximum number of bits that the processor is capable of processing in one computing cycle is 64, wherein the quantity of the first plurality of buckets is m, and the number of bits in the group of most significant bits is equal to 64-log2 m.

### Claim 14 (depends on 10)

The system of claim 10, where the computer-readable instructions further cause the processor to:
store the first tag in a first bucket of the first plurality of buckets; and
store the first value in the first bucket of the first plurality of buckets.

### Claim 15 (depends on 12)

The system of claim 12, where the computer-readable instructions further cause the processor to:
provide a pointer from the first array to the second array, the pointer comprising a number of bits equal to the maximum number of bit; and
store a number of least significant bits out of the number of bits of the pointer as an effective pointer value, wherein the number of the least significant bits is equal to the computed value.

### Claim 16 (depends on 10)

The system of claim 10, wherein a quantity of the first plurality of buckets is equal to a quantity of the second plurality of buckets.

### Claim 17

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.

### Claim 18 (depends on 17)

The computer-readable storage medium of claim 17, wherein generating the first index comprises performing a modulo operation with a value of the first hashed key as a numerator and the quantity of the first plurality of buckets as a denominator.

### Claim 19 (depends on 17)

The computer-readable storage medium of claim 17, wherein the quantity of the first plurality of buckets is a multiple of 2, and selecting the group of most significant bits from the first plurality of bits to form the first tag comprises:
computing a log to a base 2 value of the quantity of the first plurality of buckets;
subtracting the computed value from a maximum number of bits that the processor is capable of processing in one computing cycle to produce a first integer; and
using a value of the first integer as a number of elements in the group of the most significant bits.

### Claim 20 (depends on 19)

The computer-readable storage medium of claim 19, wherein the maximum number of bits that the processor is capable of processing in one computing cycle is 64, wherein the quantity of the first plurality of buckets is m, and the number of bits in the group of most significant bits is equal to 64-log2 m.