METHOD FOR IMPROVING THE EFFECTIVENESS OF HASH-BASED DATA STRUCTURES

• US 20100299333A1
• Filed: 05/13/2010
• Published: 11/25/2010
• Est. Priority Date: 05/24/2009
• Status: Active Grant

• Current Assignee: Pi-Coral Incorporated
• Original Assignee: Pi-Coral Incorporated
• Inventors: OSMOND, Roger Frederick
• Granted Patent: US 8,793,257 B2
• Time in Patent Office: Days
• 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 method for improving the effectiveness of hashed data structures comprising:

configuration of the data structure and,

transformation of hash codes as produced by the hash function,

wherein said method yields a more uniform distribution of data amongst the slots in said data structure.

2. The method of claim 1 wherein the range of generated hash codes becomes predictable.

3. The method of claim 1 wherein the predictable distribution of hash codes may be exploited by the configuration of a hash-based data structure such that more uniform distribution of items stored within said data structure is achieved.

4. The method of claim 1 wherein the transformation of hash codes is such that distribution is predicted by application of Benford'"'"'s Law.

5. The method of claim 1 wherein the transformation of hash codes is such that distribution is predicted by application of other statistical laws or theorems.

6. The method of claim 1 wherein hash code collisions are minimized.

7. The method of claim 1 wherein traversals of linked data structures, as used by hash-based data structures, and resulting from hash code collisions are reduced or eliminated.

8. The method of claim 1 wherein data sets comprise a wide range of values, covering multiple orders of magnitude.

9. The method of claim 1 wherein hash codes may be in the form of an extended sequence of decimal digits.

10. The method of claim 1 wherein the items stored at positions in a hash-based data structure may be themselves data structures, such as arrays, linked lists or hash-based data structures

11. The method of claim 1 wherein the digits of a hash code may be applied in sequence from most significant to least significant.

12. The method of claim 1 wherein the digits of a hash code may be applied in a pattern other than a sequence from most significant to least significant.