1 ------------------------------------------------------------------------------
3 -- GNAT COMPILER COMPONENTS --
5 -- G N A T . P E R F E C T _ H A S H --
9 -- Copyright (C) 2002-2003 Ada Core Technologies, Inc. --
11 -- GNAT is free software; you can redistribute it and/or modify it under --
12 -- terms of the GNU General Public License as published by the Free Soft- --
13 -- ware Foundation; either version 2, or (at your option) any later ver- --
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
16 -- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License --
17 -- for more details. You should have received a copy of the GNU General --
18 -- Public License distributed with GNAT; see file COPYING. If not, write --
19 -- to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, --
20 -- MA 02111-1307, USA. --
22 -- As a special exception, if other files instantiate generics from this --
23 -- unit, or you link this unit with other files to produce an executable, --
24 -- this unit does not by itself cause the resulting executable to be --
25 -- covered by the GNU General Public License. This exception does not --
26 -- however invalidate any other reasons why the executable file might be --
27 -- covered by the GNU Public License. --
29 -- GNAT was originally developed by the GNAT team at New York University. --
30 -- Extensive contributions were provided by Ada Core Technologies Inc. --
32 ------------------------------------------------------------------------------
34 package GNAT.Perfect_Hash is
35 pragma Pure (Perfect_Hash);
37 -- The packages in this hierarchy implement perfect hash
38 -- functions. To understand what a perfect hash function is, we
39 -- define several notions. These definitions are inspired from the
42 -- Zbigniew J. Czech, George Havas, and Bohdan S. Majewski ``An
43 -- Optimal Algorithm for Generating Minimal Perfect Hash Functions'',
44 -- Information Processing Letters, 43(1992) pp.257-264, Oct.1992
46 -- Let W be a set of m words. A hash function h is a function that
47 -- maps the set of words W into some given interval of integers
48 -- [0, k-1], where k is an integer, usually k >= m. h (w) where w
49 -- is a word computes an address or an integer from I for the
50 -- storage or the retrieval of that item. The storage area used to
51 -- store items is known as a hash table. Words for which the same
52 -- address is computed are called synonyms. Due to the existence
53 -- of synonyms a situation called collision may arise in which two
54 -- items w1 and w2 have the same address. Several schemes for
55 -- resolving known. A perfect hash function is an injection from
56 -- the word set W to the integer interval I with k >= m. If k = m,
57 -- then h is a minimal perfect hash function. A hash function is
58 -- order preserving if it puts entries into the hash table in a
59 -- prespecified order.
61 -- A minimal perfect hash function is defined by two properties:
62 -- * Since no collisions occur each item can be retrieved from the
63 -- table in *one* probe. This represents the "perfect" property.
64 -- * The hash table size corresponds to the exact size of W and
65 -- *no larger*. This represents the "minimal" property.
67 end GNAT.Perfect_Hash;