BUILDING AND QUERYING HASH TABLES ON PROCESSORS

摘要

A plurality of memory maps may be allocated that represents the hash table on a memory device to store keys and values. The memory maps may comprise at least a primary map and a secondary map. A hash table operation may be performed on the primary map based on a first position computed using a first hash function, and if not successful, a bounded linear probing that probes a defined primary probe region in the primary map. Responsive to determining that the hash table operation on the primary map is not successful, the hash table operation may be performed on the secondary map based on a second position computed using a second hash function, and if not successful, a bounded linear probing that probes a defined secondary probe region in the secondary map.

主权项

1. A method of building and operating a hash table on one or more processors, 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, the primary map having a size greater than the secondary map; 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 probes 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 probes 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.