SYSTEMS, METHODS AND COMPUTER PROGRAM PRODUCTS FOR PROBING A HASH TABLE FOR IMPROVED LATENCY AND SCALABILITY IN A PROCESSING SYSTEM

摘要

System, method and computer program products for probing a hash table by receiving a compressed input key, computing a hash value for the compressed input key and probing one or more buckets in a hash table for a match. Each bucket includes multiple chunks. For a bucket in the hash table, chunks are searched in that bucket by comparing in parallel the hash value with multiple slots in each chunk, such that if a value in a chunk equals the hash value of the compressed input key, then a match is declared and a vector is returned with a significant bit of a matching slot in the bucket set to a value. If a value stored in a chunk corresponds to an empty slot, then a mismatch is declared, and the vector is returned as the result with the significant bit of a matching empty slot set to the value.

主权项

1. A method for probing a hash table, the method comprising:
receiving a compressed input key; computing a hash value for the compressed input key; and probing, using a probing processor, one or more buckets in a hash table for a match, each bucket including multiple chunks, comprising:
for a bucket in the hash table, searching chunks in that bucket by comparing in parallel the hash value with a plurality of slots in each chunk, such that if a value in a chunk equals the hash value of the compressed input key, then a match is declared and a vector is returned as a result with a significant bit of a matching slot in the bucket set to a particular value; andif a value stored in a chunk corresponds to an empty slot, then a mismatch is declared; and the vector is returned as the result with the significant bit of a matching empty slot set to the particular value.