Abstract:
A pseudo-random number generator is employed to provide the same results normally produced by hash functions. In particular, input character string data is employed to sequentially adjust the seed of a pseudo-random number generator to produce hash values.

Description:
TECHNICAL FIELD 
       [0001]    The present invention relates in general to hash algorithms, and more particularly, to methods for generating hash values using pseudorandom number generators. 
       BACKGROUND OF THE INVENTION 
       [0002]    There are many uses for hash functions which are deterministic functions designed to serve many purposes in the data processing arts. For example, they are used to determine if errors in transmission have occurred. They are used to provide an indication of whether or not data has been corrupted. They are also used in signature verification and for user identification. 
         [0003]    The goal of any hash algorithm is to provide random and equal distribution of the hashed values over a specific range and be efficient in its execution. Most hash algorithms employ various forms of additive and rotative operations against the individual components of the value being hashed. In the case of character strings, this is usually an individual character. 
         [0004]    Character strings are composed of the machines external character set and generally do not use the entire range of the machine alphabet. For example, EBCDIC and Extended ASCII use 256 characters in its alphabet but typically define less than 100 “printable” characters. In EBCDIC these are clustered in three of the four available  64  character quadrants. With extended ASCII these are tightly grouped in two of the four available  64  character quadrants 
         [0005]    Because of the clustering and grouping, hashing algorithms which process character strings show a “bit bias” in the generated values which the various additive and rotative techniques attempt to overcome but do not eliminate. Also, depending on the algorithm, character strings that use the same characters but in a different sequence can generate the same hash value. This increases the “collision rate” for different string values. That is, different strings generate the same hash value. 
       SUMMARY OF THE INVENTION 
       [0006]    Like other hashing algorithms, this one processes each character of the string but instead of performing additive or rotative operations against the actual characters in the string, the character values are used to adjust the “seed” value sequence in a pseudo random number generator (PRNG). Very good and efficient pseudo random number generators are implemented in fewer than 10 machine instructions and easily provide 16, 32 or 64 bit pseudo random numbers. While PRNG systems are designed to produce bit strings that have random statistics, it is noted here that PRNGs are in fact deterministic devices. 
         [0007]    The final hash value is set to zero and the PRNG seed is initialized to an initial value. For each character in the input string, the PRNG seed value is adjusted using the binary character of the input data. A call to the PRNG returns a new seed and a random number which is exclusive ORed into the final hash value. This process continues for the number of characters in the string. When all of the characters have been processed, the final hash value can be used directly or a modulo of the value can be taken to constrain the hash value to a specific value range. Since the random values are used to determine the hash value and not the characters themselves, the effects of printable character clustering within the total machine character set and character sequence are minimized. 
         [0008]    The method of the present invention also includes an optional deterministic function whose input is the character value and whose output is used instead of the character itself to provide for seed adjustment. 
         [0009]    Additional features and advantages are realized through the techniques of the present invention. Other embodiments and aspects of the invention are described in detail herein and are considered a part of the claimed invention. 
         [0010]    The recitation herein of a list of desirable objects which are met by various embodiments of the present invention is not meant to imply or suggest that any or all of these objects are present as essential features, either individually or collectively, in the most general embodiment of the present invention or in any of its more specific embodiments. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0011]    The subject matter which is regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of practice, together with the further objects and advantages thereof, may best be understood by reference to the following description taken in connection with the accompanying drawings in which: 
           [0012]      FIG. 1  is a block diagram illustrating the process of the present invention and in particular showing the processing of a character string to generate a hash value. 
           [0013]      FIG. 2  is a block diagram illustrating the environment in which the present invention is employed; and 
           [0014]      FIG. 3  is a top view of a CD-ROM or other computer readable medium on which the present invention is encoded. 
       
    
    
     DETAILED DESCRIPTION 
       [0015]      FIG. 1  illustrates one of the preferred embodiments of the present invention. In particular,  FIG. 1  shows pseudorandom number generator  100 , which generates pseudorandom numbers to be supplied to exclusive or block  150  based upon the seed value present in block  110 . The beginning of the process starts with the initialization  140 , which selects an initial seed value and an initial value for the final hash value to be placed in block  160 . During each cycle of the process a value such as those labeled B 1  through B 1  in block  130  are used to adjust the current seed value in block  110  via the seed adjusting function provided in block  120 . This adjustment can be a simple addition operation, though other adjusting functions may be employed as well, such as subtraction or multiplication. Based upon the value of the seed in block  110  pseudorandom number generator  100  generates a value, which is exclusive-Ored in block  150  with the contents found in block  160 , which is the final hash value. The process is repeated for as many characters, n, as provided in the data. Furthermore, if the final value produced from block  160  may be computed modulo N to provide a final hash value that lies within a convenient range. In short, in each cycle, the seed value is changed, and in particular, it is changed in accordance with adjustments made in block  120  based upon character values from block  130  that are supplied to it. The generated random number is then exclusive-ORed with the previous hash value to produce a new hash value. 
         [0016]    As pointed out above, the output from exclusive-OR block  150  is supplied to block  160  representing the next desired hash value output. However, it is noted that the output from block  160  may be summed over a number n of input character cycles with the hash value output being a sequence of bits processed by block  170  in this manner. 
         [0017]    The segment of code below in the C programming language provides one preferred implementation of the present invention. In particular, assume that the variable “name” points to a NULL terminated “C” style string. The implementation below uses the system provided “rand_r” function to generate the random number. The variable “newKey” will contain the hash value when all the characters in the string have been processed. The initial “seed” value is arbitrarily selected and changes with each call to the “rand_r” function: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 newKey = 0; 
               
               
                   
                 seed = 7701; 
               
               
                   
                 for(; *name; ++name) { 
               
               
                   
                  seed += (unsigned char)*name; 
               
               
                   
                  newKey = newKey {circumflex over ( )} rand_r(&amp;seed); 
               
               
                   
                 } 
               
               
                   
                   
               
             
          
         
       
     
         [0018]    One use for the Hashing algorithm is to manage the symbol table in the registry to track all the resources that are created by name. However, the hashing function is independent of the registry and can be used any time some type of name hash is needed to manage a set of named resources. For example, symbol table in a compiler, named files on a data volume, etc. The intent is to provide a more even distribution across the available hash space regardless of hash size. The ideal collision rate would be number-of-items/number-of-hash-entries. This hash is more dependent on the PRNG distribution than the actual values of the items being hashed, a characteristic which renders it ideal for the applications intended herein. 
         [0019]    The present invention may be implemented in software or in firmware in a stored program digital data processing system. In such an event blocks such as  130 ,  110 , and  160  are best interpreted as storage locations. Blocks  100 ,  120 ,  140 ,  150  and  170  are best interpreted as software encoded functions. However, the present invention may also be practiced by constructing the system shown in  FIG. 1  as a plurality of components forming a dedicated signal processing device or as a programmed aspect of a programmable digital signal processing element. 
         [0020]    In any event the environment in which the present invention operates is shown in  FIG. 2 . The present invention operates in a data processing environment which effectively includes one or more of the computer elements shown in  FIG. 2 . In particular, computer  500  includes central processing unit (CPU)  520  which accesses programs and data stored within random access memory  510 . Memory  510  is typically volatile in nature and accordingly such systems are provided with nonvolatile memory typically in the form of rotatable magnetic memory  540 . While memory  540  is preferably a nonvolatile magnetic device, other media may be employed. CPU  530  communicates with users at consoles such as terminal  550  through Input/Output unit  530 . Terminal  550  is typically one of many, if not thousands, of consoles in communication with computer  500  through one or more I/O unit  530 . In particular, console unit  550  is shown as having included therein a device for reading medium of one or more types such as CD-ROM  560  shown in  FIG. 3 . Media  560  may also comprise any convenient device including, but not limited to, magnetic media, optical storage devices and chips such as flash memory devices or so-called thumb drives. Disk  560  also represents a more generic distribution medium in the form of electrical signals used to transmit data bits which represent codes for the instructions discussed herein. While such transmitted signals may be ephemeral in nature they still, nonetheless constitute a physical medium carrying the coded instruction bits and are intended for permanent capture at the signal&#39;s destination or destinations. 
         [0021]    While the invention has been described in detail herein in accordance with certain preferred embodiments thereof, many modifications and changes therein may be effected by those skilled in the art. Accordingly, it is intended by the appended claims to cover all such modifications and changes as fall within the true spirit and scope of the invention.