Reducing collisions within a hash table

A computer program product comprising:

• a non-transitory computer readable storage medium encoded with instructions that, when executed by a processor, cause the processor to reduce collisions in hash tables by performing the functions of:
• removing each empty bucket from a hash table and compacting the non-empty buckets;
• generating a map of the hash table indicating a status of the buckets of the hash table;
• and
• accessing data in the hash table by applying a hash key to the generated map to determine a corresponding bucket containing the data, wherein accessing further comprises:
• applying the hash key to the generated map to determine a corresponding position in the generated map;
• computing a population count in the generated map, of all positions in the generated map up to the determined corresponding position;
• and
• using the computed population count as a bucket position of the corresponding bucket containing the data.

An apparatus comprising:

• a processor including:
• a hash table compacting module configured to remove each empty bucket from a hash table and to compact the non-empty buckets;
• a hash table map generating module configured to generate a map of the hash table indicating a status of the buckets of the hash table;
• and
• a data access module configured to access data in the hash table by applying a hash key to the generated map to determine a corresponding bucket containing the data, wherein accessing further comprises:
• applying the hash key to the generated map to determine a corresponding position in the generated map;
• computing a population count in the generated map, of all positions in the generated map up to the determined corresponding position;
• and
• using the computed population count as a bucket position of the corresponding bucket containing the data.