Method for improving the effectiveness of hash-based data structures

摘要

A method to improve the effectiveness of hash-based data structures includes configuration of a data structure and transformation of hash codes as produced by a hash function, to yield a more uniform distribution of data amongst the slots in a data structure. Transformation results in a non-uniform but predictable distribution of hash codes. Configuration exploits the predictable nature of the transformed hash codes to accomplish more uniform and therefore more efficient distribution of items stored in a hash-based data structure.

主权项

1. A computer-implemented method for minimizing collisions in hash based data storage operative on a computing device, the computer-implemented method comprising:
determining a predicted distribution of a plurality of digits of a plurality of hash codes generated by a hash function; generating at least one hash data structure comprising a plurality of data slots configured based on the predicted distribution, wherein a number of the plurality of data slots is based on the predicted distribution of at least one of the plurality of digits; and uniformly distributing at least one element associated with the plurality of hash codes in the plurality of data slots based on the plurality of digits.