Method and system for hash key memory footprint reduction

摘要

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.

主权项

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, wherein the location identifier is determined based on the data, wherein the location identifier comprises a set number, and 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; compressing the data by extracting the location identifier from the data, wherein the compressing includes:
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; andsetting a wrapped bit to 1;otherwise,
determining the set number as the decimal value; andsetting the wrapped bit to 0; and storing the compressed data in the identified location of the hash table.