Method for improving the effectiveness of hash-based data structures

• US 8,793,257 B2
• Filed: 05/13/2010
• Issued: 07/29/2014
• Est. Priority Date: 05/24/2009
• Status: Expired due to Fees

• Current Assignee: Pi-Coral Incorporated
• Original Assignee: Pi-Coral Incorporated
• Inventors: Osmond, Roger Frederick
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US12/779,727
• Publication Number:
  US 20100299333A1
• Time in Patent Office: 1,538 Days
• Field of Search: 711/202
• US Class Current: 707/747
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

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.

Claims

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.

2. The computer-implemented method of claim 1, further comprising using at least one prediction model to determine the predicted distribution.

3. The computer-implemented method of claim 2, wherein the at least one prediction model is associated with Benford'"'"'s Law.

4. The computer-implemented method of claim 1, wherein generating at least one hash data structure comprises generating the at least one hash data structure as a three-dimensional array.

5. The computer-implemented method of claim 1, wherein generating at least one hash data structure comprises generating the at least one hash data structure as a tree data structure.

6. The computer-implemented method of claim 1, wherein the at least one element comprises at least one data structure.

7. The computer-implemented method of claim 1, wherein the plurality of hash codes comprise at least three digits and the at least one element is uniformly distributed based on a first three digits of the at least three digits.

8. The computer-implemented method of claim 1, further comprising providing a number of the plurality of data slots for each of the plurality of digits corresponding to the predicted distribution of the plurality of digits.

9. The computer-implemented method of claim 1, further comprising assigning at least one digit of the plurality of digits to the plurality of data slots corresponding to the predicted distribution of the plurality of digits.

10. The computer-implemented method of claim 1, further comprising:

obtaining a percentage for each of the plurality of digits based on the predicted distribution; and

providing a number of the plurality of data slots for each of the plurality of digits in proportion to the percentage for each of the plurality of digits.