Building and querying hash tables on processors

A system for building and operating a hash table, comprising:

• one or more processors;
• a memory device;
• a plurality of memory maps allocated on the memory device that represents the hash table to store keys and values, the memory maps comprising at least a primary map and a secondary map, wherein a primary map's size is defined a first predefined multiple of a number of items indexed and wherein a secondary map's size is defined as a second predefined multiple of the number of items indexed, wherein the first predefined multiple is greater than the second predefined multiple, the primary map associated with a defined primary probe region contained in the primary map and the secondary map associated with a defined secondary probe region contained in the secondary map, wherein the defined primary probe region is smaller than the defined secondary probe region,
• the one or more processors performing a hash table operation on the primary map based on a first position computed using a first hash function,
• the one or more processors performing a bounded linear probing that scans a defined primary probe region in the primary map responsive to determining that the hash table operation on the primary map on the first position is not successful,
• the one or more processors in response to determining that the hash table operation on the primary map on the first position and the defined primary probe region is not successful, performing the hash table operation on the secondary map based on a second position computed using a second hash function, and
• the one or more processors performing the bounded linear probing that scans a defined secondary probe region in the secondary map responsive to determining that the hash operation on the secondary map on the second position is not successful,
• wherein multiple levels of memory maps are allocated, the multiple levels of memory maps comprising at each level a memory map and an associated probe region.

A computer readable storage medium storing a program of instructions executable by a machine to perform a method of building and operating a hash table on one or more processors, the method comprising:

• allocating a plurality of memory maps on a memory device that represents the hash table to store keys and values, the memory maps comprising at least a primary map and a secondary map, wherein a primary map's size is defined as a first predefined multiple of a number of items indexed and wherein a secondary map's size is defined as a second predefined multiple of the number of items indexed, wherein the first predefined multiple is greater than the second predefined multiple, the primary map associated with a defined primary probe region contained in the primary map and the secondary map associated with a defined secondary probe region contained in the secondary map, wherein the defined primary probe region is smaller than the defined secondary probe region;
• performing a hash table operation on the primary map based on a first position computed using a first hash function;
• performing a bounded linear probing that scans a defined primary probe region in the primary map responsive to determining that the hash table operation on the primary map on the first position is not successful;
• in response to determining that the hash table operation on the primary map on the first position and the defined primary probe region is not successful, performing the hash table operation on the secondary map based on a second position computed using a second hash function;
• and
• performing the bounded linear probing that scans a defined secondary probe region in the secondary map responsive to determining that the hash operation on the secondary map on the second position is not successful,
• wherein multiple levels of memory maps are allocated, the multiple levels of memory maps comprising at each level a memory map and an associated probe region.