Voici différents sites proposant des fonctions de hash-code parfaites:

• fonction de hash-code parfaite et minimale, de Bob Jenkins
• gperf, générateur de fonctions de hash-code parfaites écrit en C++ (licence GNU)
• l'algorithme d'Omar Alonso, en C

Quelques références "papier":

• A Linear Time Algorithm for Finding Minimal Perfect Hash Functions

  Zbigniew J. Czech¹ and Bohdan S. Majewski^{1
  1} Institutes of Computer Science, Silesia University of Technology, and Polish Academy of Sciences, 44-100 Gliwice, Poland
  ²Key Centre for Software Technology, University of Queensland, Queensland 4072, Australia

  A new algorithm for finding minimal perfect hash functions (MPHF) is proposed. The algorithm given three pseudorandom functions h0, h1 and h2, searches for a function g such that F(w) = (h₀ (w) + g(h₁ (w)) + g(h₂ (w))) mod m is a MPHF, where m is a number of input words. The algorithm involves generation of random bipartite graphs and runs in linear time. The hash function generated is represented by using 2m + 0(1) memory words of logm bits each. The empirical observations show that the algorithm runs very fast in practice.

• "Minimal Perfect Hash Functions Made Simple", by Richard J. Cichelli, CACM 23 #1 17-19 (1980) describes a method for creating perfect hash functions from character strings of the form

  hash value <- key length + key 1st char + key last char

• TITLE: An optimal algorithm for generating minimal perfect hash functions
  AUTHORS: Zbigniew J. Czech, George Havas and Bohdan S. Majewski
  CITATION: Information Processing Letters 43 (1992) 257-264
  ABSTRACT: A new algorithm for generating order preserving minimal perfect hash functions is presented. The algorithm is probabilistic, involving generation of random graphs. It uses expected linear time and requires a linear number words to represent the hash function, and thus is optimal up to constant factors. It runs very fast in practice.

• TITLE: Graph theoretic obstacles to perfect hashing
  AUTHORS: George Havas and Bohdan S. Majewski
  CITATION: Congressus Numerantium 98 (1993) 81-93
  REVIEW: Math. Rev. 95e:68039 (Ricardo Baeza-Yates)
  ABSTRACT: A number of algorithms based on quasi-random graphs for generating perfect hash functions have been published. These include Sager's mincycle algorithm, a modification by Fox et al. of it and finally probabilistic methods due to Czech, Havas and Majewski. Each of these algorithms exploits different properties of graphs, such as being bipartite or being acyclic. In this paper we formally justify the significance of these properties. Also we indicate causes of failure for some methods. In particular we show that acyclicity of a graph plays a crucial role in finding order preserving perfect hash functions. It is a sufficient, but not necessary, condition for algorithms to actually find a perfect hash function. We provide some examples for which various published methods methods fail, taking exponential time to do so. Finally, based on our considerations of graph properties, we propose yet another method for generating perfect hash functions.

• TITLE: Graphs, hypergraphs and hashing
  AUTHORS: George Havas, Bohdan S. Majewski, Nicholas C. Wormald and Zbigniew J. Czech
  CITATION: Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 790 (1994), 153-165
  ABSTRACT: Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. We present an infinite family of efficient and practical algorithms for generating minimal perfect hash functions which allow an arbitrary order to be specified for the keys. We show that almost all members of the family are space and time optimal, and we identify the one with minimum constants. Members of the family generate a minimal perfect hash function in two steps. First a special kind of function into an r-graph is computed probabilistically. Then this function is refined deterministically to a minimal perfect hash function. We give strong practical and theoretical evidence that the first step uses linear random time. The second step runs in linear deterministic time. The family not only has theoretical importance, but also offers the fastest known method for generating perfect hash functions.

• TITLE: A family of perfect hashing methods
  AUTHORS: Bohdan S. Majewski, Nicholas C. Wormald, George Havas and Zbigniew J. Czech
  CITATION: Computer Journal 39 (1996) 547-554
  ABSTRACT: Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. We present an infinite family of efficient and practical algorithms for generating order preserving minimal perfect hash functions. We show that almost all members of the family construct space and time optimal order preserving minimal perfect hash functions, and we identify the one with minimum constants. Members of the family generate a hash function in two steps. First a special kind of function into an r-graph is computed probabilistically. Then this function is refined deterministically to a minimal perfect hash function. We give strong theoretical evidence that the first step uses linear random time. The second step runs in linear deterministic time. The family not only has theoretical importance, but also offers the fastest known method for generating perfect hash functions.

• TITLE: Perfect hashing
  AUTHORS: Zbigniew J. Czech, George Havas and Bohdan S. Majewski
  CITATION: Theoretical Computer Science (to appear)
  CONTENTS:
  1. Introduction
     1. Basic definitions
     2. Trial and error
     3. Space and time requirements
     4. Bibliographic remarks
  2. Number theoretical solutions
     1. Introduction
     2. Quotient and remainder reduction
     3. Reciprocal hashing
     4. A Chinese Remainder Theorem method
     5. A letter-oriented scheme
     6. A Chinese Remainder Theorem based variation
     7. Another Chinese Remainder Theorem based variation
     8. Bibliographic remarks
  3. Perfect hashing with segmentation
     1. Introduction
     2. Bucket distribution schemes
     3. A hash indicator table method
     4. Using backtracking to find a hash indicator table
     5. A method of very small subsets
     6. Bibliographic remarks
  4. Reducing the search space
     1. Mapping, ordering, searching
     2. Using letter frequency
     3. Minimum length cycles
     4. Skewed vertex degree distribution
     5. Minimum length fundamental cycles
     6. A linear time algorithm
     7. Quadratic minimal perfect hashing
     8. Large and small buckets
     9. Bibliographic remarks
  5. Sparse table compression
     1. Introduction
     2. A single displacement method
     3. A double displacement method
     4. A letter-oriented method
     5. Another letter-oriented method
     6. Bibliographic remarks
  6. Probabilistic Perfect Hashing
     1. Introduction
     2. The FKS algorithm and its modifications reinterpreted
     3. A random graph approach
     4. Random hypergraphs methods
     5. Modifications
     6. Advanced applications
     7. Graph theoretic obstacles
     8. Bibliographic remarks
  7. Dynamic perfect hashing
     1. Introduction
     2. The FKS based method
     3. A real time dictionary
     4. Bibliographic remarks

  Appendix. Notation index
  Acknowledgements
  References

• Optimal algorithms for minimal perfect hashing, par Georges Havas et Bohdan S. Majewski. Le contenu de cette bibliographie est rapidement évoqué dans cette archive.

• Encore une autre bibliographie.

Site Hosting: Bronco