General hashing

Abstract

Hashing is a method for fast data storage and retrieval in which keys are transformed by a hash function into hash values for locating data. Its performance depends partially, but essentially, on how good the hash function is. Minimizing collisions has been a principal criterion for good hash functions. It is commonly believed that, for a single hash function, key structure often shows through into hash values resulting poor performance. From these ideas come the common belief that no general hash function (which works well across applications) exists. The inventor of hashing, Hans Luhn, believed that good hash functions should destroy key structure and approximate a random variable. Random hash values perform close to the ideal and are insensitive to key structure. Closely approximating a random function is proposed as a defining characteristic for general hash functions. Cryptographic researchers focused on secure hash functions for compressing messages so that recovering the original data or forging a given compressed message is difficult Based on stronger requirements, they have developed formal models and implemented practical, secure hash functions. Their results hint at a method to create a general hash function for variable-length input. In particular, poly-random functions, which are statistically indistinguishable from random functions, could be used to construct a general hash function, the proof is given in Chapter 2. Inspired by surveys which tested existing hash functions, a more elaborated hash function test-bed is proposed. Three fast, practical hash functions were tested using the test-bed proposed in Chapter 3. These include Pearson's, Uzgalis's, and a new variant hash function that is proposed here. These were all found to be convincingly general, and the new variant corrects minor deficiencies in the other two. Besides general-purpose function libraries, general hash functions can be applied to strongly-typed programming languages. Chapter 4 introduces the notion of hash data types, which allows derivation of hash values for compound data objects from those of their components. A formalism for manipulating hash values is introduced which can be incorporated to programming transformation formalisms for deriving hash-based programs. To show the usefulness of general hashing several new hash based applications are described in Chapters 5, 6, and 7. (5) aperiodic pseudorandom number generation; (6) flexible and reliable non-algebraic error correction; and (7) simulated random input arrival. These show a range of possible applications for general hashing.