# US 2013/0159629 A1 · Method and system for hash key memory footprint reduction

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

- Number: US 2013/0159629 A1
- Document ID: US20130159629A1
- Status: Published application
- Kind: A1
- Application number: 13/677,791
- Filed: 2012-11-15
- Published: 2013-06-20
- Earliest claimed: 2011-12-16
- Assignees: STEC, Inc.
- Inventors: Mohammad Reza SADRI; Saied KAZEMI; Siddharth CHOUDHURI
- Web page: https://patentgrep.com/patent/US20130159629A1

## CPC

- G06F 16/172: Caching, prefetching or hoarding of files
- G06F 3/0626: {Reducing size or complexity of storage systems}
- G06F 3/0643: {Management of files}
- G06F 3/0673: {Single storage device}
- G06F 12/0864: using pseudo-associative means, e.g. set-associative or hashing
- G06F 12/1018: involving hashing techniques, e.g. inverted page tables
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/9014: {hash tables}
- G06F 2212/6032: Way prediction in set-associative cache
- G06F 2212/657: Virtual address space management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system and method are disclosed for storing data in a hash table. The method includes receiving data, determining a location identifier for the data wherein the location identifier identifies a location in the hash table for storing the data and the location identifier is derived from the data, compressing the data by extracting the location identifier; and storing the compressed data in the identified location of the hash table.

## Claims

### Claim 1

A method for storing data in a hash table, the method comprising:
receiving data;
determining a location identifier for the data, wherein the location identifier identifies a location in the hash table for storing the data, and the location identifier is derived from the data;
compressing the data by extracting the location identifier; and
storing the compressed data in the identified location of the hash table.

### Claim 2 (depends on 1)

The method of claim 1, wherein the location identifier comprises a set number.

### Claim 3 (depends on 2)

The method of claim 2, wherein the determining the location identifier for the data includes
determining a number of bits to extract from the data, based on (i) a block size of the hash table and (ii) a total number of sets in the hash table;
extracting a plurality of middle bits from the data, based on the number of bits to extract;
calculating a decimal value of the plurality of middle bits;
if the decimal value is greater than the total number of sets;
determining the set number by subtracting the total number of sets from the decimal value; and
setting a wrapped bit to 1;
otherwise;
determining the set number as the decimal value; and
setting the wrapped bit to 0.

### Claim 4 (depends on 1)

The method of claim 1, wherein the hash table comprises a cache.

### Claim 5 (depends on 1)

The method of claim 1, wherein the hash table comprises a set associative cache.

### Claim 6

A method for retrieving data from a hash table, the method comprising:
receiving an index;
retrieving compressed data stored at the index of the hash table;
determining a set number based on the index and an associativity, the associativity indicating a capacity of the hash set;
determining whether wrapping is required;
if wrapping is required,
expanding the compressed data based on the set number and a total number of sets in the hash table; and
otherwise,
expanding the compressed data based on the set number.

### Claim 7 (depends on 6)

The method of claim 6, wherein the hash table comprises a cache.

### Claim 8 (depends on 6)

The method of claim 6, wherein the hash table comprises a set associative cache.

### Claim 9

A storage device for storing data in a hash table, the storage device comprising:
a host interface for communicating with a host device;
a memory for storing data;
a memory controller comprising logic stored in a computer readable medium, the logic configured to:
receive data;
determine a location identifier for the data, wherein the location identifier identifies a location in the hash table for storing the data, and the location identifier is derived from the data;
compress the data by extracting the location identifier; and
store the compressed data in the identified location of the hash table.

### Claim 10 (depends on 9)

The storage device of claim 9, wherein the location identifier comprises a set number.

### Claim 11 (depends on 10)

The storage device of claim 10, wherein the logic configured to determine the location identifier for the data includes logic configured to:
determine a number of bits to extract from the data, based on (i) a block size of the hash table and (ii) a total number of sets in the hash table;
extract a plurality of middle bits from the data, based on the number of bits to extract;
calculate a decimal value of the plurality of middle bits;
if the decimal value is greater than the total number of sets;
determine the set number by subtracting the total number of sets from the decimal value; and
set a wrapped bit to 1;
otherwise;
determine the set number as the decimal value; and
set the wrapped bit to 0.

### Claim 12 (depends on 9)

The storage device of claim 9, wherein the hash table comprises a cache.

### Claim 13 (depends on 9)

The storage device of claim 9, wherein the hash table comprises a set associative cache.

### Claim 14 (depends on 11)

The storage device of claim 11, wherein the memory controller further comprises logic for retrieving data from the hash table, the logic configured to:
receive an index;
retrieve compressed data stored at the index of the hash table;
determine a set number based on the index and an associativity, the associativity indicating a capacity of the hash set;
determine whether wrapping is required;
if wrapping is required,
expand the compressed data based on the set number and a total number of sets in the hash table; and
otherwise,
expand the compressed data based on the set number.

### Claim 15

A non-transitory computer program product, tangibly embodied in a computer-readable medium, the computer program product including instructions operable to cause a data processing apparatus to:
receive data;
determine a location identifier for the data, wherein the location identifier identifies a location in the hash table for storing the data, and the location identifier is derived from the data;
compress the data by extracting the location identifier; and
store the compressed data in the identified location of the hash table.

### Claim 16 (depends on 15)

The non-transitory computer program product of claim 15, wherein the location identifier comprises a set number.

### Claim 17 (depends on 16)

The non-transitory computer program product of claim 16, wherein the instructions operable to cause a data processing apparatus to determine the location identifier for the data further comprise instructions operable to cause a data processing apparatus to:
determine a number of bits to extract from the data, based on (i) a block size of the hash table and (ii) a total number of sets in the hash table;
extract a plurality of middle bits from the data, based on the number of bits to extract;
calculate a decimal value of the plurality of middle bits;
if the decimal value is greater than the total number of sets;
determine the set number by subtracting the total number of sets from the decimal value; and
set a wrapped bit to 1;
otherwise;
determine the set number as the decimal value; and
set the wrapped bit to 0.

### Claim 18 (depends on 15)

The non-transitory computer program product of claim 15, wherein the hash table comprises a cache.

### Claim 19 (depends on 15)

The non-transitory computer program product of claim 15, wherein the hash table comprises a set associative cache.

### Claim 20 (depends on 17)

The non-transitory computer program product of claim 17, wherein the computer program product further includes instructions operable to cause a data processing apparatus to retrieve data from the hash table, the instructions operable to cause a data processing apparatus to:
receive an index;
retrieve compressed data stored at the index of the hash table;
determine a set number based on the index and an associativity, the associativity indicating a capacity of the hash set;
determine whether wrapping is required;
if wrapping is required,
expand the compressed data based on the set number and a total number of sets in the hash table; and
otherwise,
expand the compressed data based on the set number.