Memory-efficient storage and searching in hash tables using compressed indexes

A non-transitory, computer-readable media having instructions thereupon which, when executed by one or more processors, cause the one or more processors to perform operations comprising:

• separating bits of a value into address bits, prefix bits and signature bits;
• determining a container using the compressed index at an address specified by the address bits, wherein the container comprises a prefix table with bits set according to the prefix bits determined by aggregate values associated with the container and a signature table containing the signature bits determined by the aggregate values associated with the container;
• and
• determining, using the one or more processors, a result based on a function of the prefix and signature tables and the determined prefix and signature bits.

A system, comprising:

• one or more processors configured to:
• break a value into address bits, prefix bits and signature bits;
• determine a container using a compressed index at an address specified by the address bits, the container comprised of a prefix table with bits according to the prefix bits determined by aggregate values associated with the container and a signature table containing the signature bits determined by the aggregate values associated with the container;
• and
• determine a result based on a function of the prefix and signature tables and the determined prefix and signature bits;
• and
• determine whether the value is stored in a hash table based on the result.