KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > it > unimi > dsi > fastutil > Hash


1 package it.unimi.dsi.fastutil;
2
3 /*
4  * fastutil: Fast & compact type-specific collections for Java
5  *
6  * Copyright (C) 2002, 2003, 2004, 2005, 2006 Sebastiano Vigna
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Lesser General Public
10  * License as published by the Free Software Foundation; either
11  * version 2.1 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public
19  * License along with this library; if not, write to the Free Software
20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21  *
22  */
23
24 /** Basic data for all hash-based classes.
25  *
26  * <p>The classes in <code>fastutil</code> are built around open-addressing hashing
27  * implemented <em>via</em> double hashing. Following Knuth's suggestions in the third volume of <em>The Art of Computer
28  * Programming</em>, we use for the table size a prime <var>p</var> such that
29  * <var>p</var>-2 is also prime. In this way hashing is implemented with modulo <var>p</var>,
30  * and secondary hashing with modulo <var>p</var>-2.
31  *
32  * <p>Entries in a table can be in three states: {@link #FREE}, {@link #OCCUPIED} or {@link #REMOVED}.
33  * The naive handling of removed entries requires that you search for a free entry as if they were occupied. However,
34  * <code>fastutil</code> implements two useful optimizations, based on the following invariant:
35  * <blockquote>
36  * Let <var>i</var><sub>0</sub>, <var>i</var><sub>1</sub>, &hellip, <var>i</var><sub><var>p</var>-1</sub> be
37  * the permutation of the table indices induced by the key <var>k</var>, that is, <var>i</var><sub>0</sub> is the hash
38  * of <var>k</var> and the following indices are obtained by adding (modulo <var>p</var>) the secondary hash plus one.
39  * If there is a {@link #OCCUPIED} entry with key <var>k</var>, its index in the sequence above comes <em>before</em>
40  * the indices of any {@link #REMOVED} entries with key <var>k</var>.
41  * </blockquote>
42  *
43  * <p>When we search for the key <var>k</var> we scan the entries in the
44  * sequence <var>i</var><sub>0</sub>, <var>i</var><sub>1</sub>, &hellip,
45  * <var>i</var><sub><var>p</var>-1</sub> and stop when <var>k</var> is found,
46  * when we finished the sequence or when we find a {@link #FREE} entry. Note
47  * that the correctness of this procedure it is not completely trivial. Indeed,
48  * when we stop at a {@link #REMOVED} entry with key <var>k</var> we must rely
49  * on the invariant to be sure that no {@link #OCCUPIED} entry with the same
50  * key can appear later. If we insert and remove frequently the same entries,
51  * this optimization can be very effective (note, however, that when using
52  * objects as keys or values deleted entries are set to a special fixed value to
53  * optimize garbage collection).
54  *
55  * <p>Moreover, during the probe we keep the index of the first {@link #REMOVED} entry we meet.
56  * If we actually have to insert a new element, we use that
57  * entry if we can, thus avoiding to pollute another {@link #FREE} entry. Since this position comes
58  * <i>a fortiori</i> before any {@link #REMOVED} entries with the same key, we are also keeping the invariant true.
59  */
60
61 public interface Hash {
62
63     /** The initial default size of a hash table. */
64     final public int DEFAULT_INITIAL_SIZE = 16;
65     /** The default load factor of a hash table. */
66     final public float DEFAULT_LOAD_FACTOR = .75f;
67     /** The load factor for a (usually small) table that is meant to be particularly fast. */
68     final public float FAST_LOAD_FACTOR = .5f;
69     /** The load factor for a (usually very small) table that is meant to be extremely fast. */
70     final public float VERY_FAST_LOAD_FACTOR = .25f;
71     /** The default growth factor of a hash table. */
72     final public int DEFAULT_GROWTH_FACTOR = 16;
73     /** The state of a free hash table entry. */
74     final public byte FREE = 0;
75     /** The state of a occupied hash table entry. */
76     final public byte OCCUPIED = -1;
77     /** The state of a hash table entry freed by a deletion. */
78     final public byte REMOVED = 1;
79      
80     /** A list of primes to be used as table sizes. The <var>i</var>-th element is
81      * the largest prime <var>p</var> smaller than 2<sup>(<var>i</var>+28)/16</sup>
82      * and such that <var>p</var>-2 is also prime (or 1, for the first few entries). */
83
84     final public int PRIMES[] = { 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 7, 7, 7,
85                                   7, 7, 7, 7, 7, 7, 7, 7, 13, 13, 13, 13, 13, 13, 13, 13, 19, 19, 19, 19, 19,
86                                   19, 19, 19, 19, 19, 19, 19, 31, 31, 31, 31, 31, 31, 31, 43, 43, 43, 43, 43,
87                                   43, 43, 43, 61, 61, 61, 61, 61, 73, 73, 73, 73, 73, 73, 73, 103, 103, 109,
88                                   109, 109, 109, 109, 139, 139, 151, 151, 151, 151, 181, 181, 193, 199, 199,
89                                   199, 229, 241, 241, 241, 271, 283, 283, 313, 313, 313, 349, 349, 349, 349,
90                                   421, 433, 463, 463, 463, 523, 523, 571, 601, 619, 661, 661, 661, 661, 661,
91                                   823, 859, 883, 883, 883, 1021, 1063, 1093, 1153, 1153, 1231, 1321, 1321,
92                                   1429, 1489, 1489, 1621, 1699, 1789, 1873, 1951, 2029, 2131, 2143, 2311,
93                                   2383, 2383, 2593, 2731, 2803, 3001, 3121, 3259, 3391, 3583, 3673, 3919,
94                                   4093, 4273, 4423, 4651, 4801, 5023, 5281, 5521, 5743, 5881, 6301, 6571,
95                                   6871, 7129, 7489, 7759, 8089, 8539, 8863, 9283, 9721, 10141, 10531, 11071,
96                                   11551, 12073, 12613, 13009, 13759, 14323, 14869, 15649, 16363, 17029,
97                                   17839, 18541, 19471, 20233, 21193, 22159, 23059, 24181, 25171, 26263,
98                                   27541, 28753, 30013, 31321, 32719, 34213, 35731, 37309, 38923, 40639,
99                                   42463, 44281, 46309, 48313, 50461, 52711, 55051, 57529, 60091, 62299,
100                                   65521, 68281, 71413, 74611, 77713, 81373, 84979, 88663, 92671, 96739,
101                                   100801, 105529, 109849, 115021, 120079, 125509, 131011, 136861, 142873,
102                                   149251, 155863, 162751, 169891, 177433, 185071, 193381, 202129, 211063,
103                                   220021, 229981, 240349, 250969, 262111, 273643, 285841, 298411, 311713,
104                                   325543, 339841, 355009, 370663, 386989, 404269, 422113, 440809, 460081,
105                                   480463, 501829, 524221, 547399, 571603, 596929, 623353, 651019, 679909,
106                                   709741, 741343, 774133, 808441, 844201, 881539, 920743, 961531, 1004119,
107                                   1048573, 1094923, 1143283, 1193911, 1246963, 1302181, 1359733, 1420039,
108                                   1482853, 1548541, 1616899, 1688413, 1763431, 1841293, 1922773, 2008081,
109                                   2097133, 2189989, 2286883, 2388163, 2493853, 2604013, 2719669, 2840041,
110                                   2965603, 3097123, 3234241, 3377191, 3526933, 3682363, 3845983, 4016041,
111                                   4193803, 4379719, 4573873, 4776223, 4987891, 5208523, 5439223, 5680153,
112                                   5931313, 6194191, 6468463, 6754879, 7053331, 7366069, 7692343, 8032639,
113                                   8388451, 8759953, 9147661, 9552733, 9975193, 10417291, 10878619, 11360203,
114                                   11863153, 12387841, 12936529, 13509343, 14107801, 14732413, 15384673,
115                                   16065559, 16777141, 17519893, 18295633, 19105483, 19951231, 20834689,
116                                   21757291, 22720591, 23726449, 24776953, 25873963, 27018853, 28215619,
117                                   29464579, 30769093, 32131711, 33554011, 35039911, 36591211, 38211163,
118                                   39903121, 41669479, 43514521, 45441199, 47452879, 49553941, 51747991,
119                                   54039079, 56431513, 58930021, 61539091, 64263571, 67108669, 70079959,
120                                   73182409, 76422793, 79806229, 83339383, 87029053, 90881083, 94906249,
121                                   99108043, 103495879, 108077731, 112863013, 117860053, 123078019, 128526943,
122                                   134217439, 140159911, 146365159, 152845393, 159612601, 166679173,
123                                   174058849, 181765093, 189812341, 198216103, 206991601, 216156043,
124                                   225726379, 235720159, 246156271, 257054491, 268435009, 280319203,
125                                   292730833, 305691181, 319225021, 333358513, 348117151, 363529759,
126                                   379624279, 396432481, 413983771, 432312511, 451452613, 471440161,
127                                   492312523, 514109251, 536870839, 560640001, 585461743, 611382451,
128                                   638450569, 666717199, 696235363, 727060069, 759249643, 792864871,
129                                   827967631, 864625033, 902905501, 942880663, 984625531, 1028218189,
130                                   1073741719, 1121280091, 1170923713, 1222764841, 1276901371, 1333434301,
131                                   1392470281, 1454120779, 1518500173, 1585729993, 1655935399, 1729249999,
132                                   1805811253, 1885761133, 1969251079, 2056437379, 2147482951 };
133
134
135     /** A generic hash strategy.
136      *
137      * <P>Custom hash structures (e.g., {@link
138      * it.unimi.dsi.fastutil.objects.ObjectOpenCustomHashSet}) allow to hash objects
139      * using arbitrary functions, a typical example being that of {@linkplain
140      * it.unimi.dsi.fastutil.ints.IntArrays#HASH_STRATEGY arrays}. Of course,
141      * one has to compare objects for equality consistently with the chosen
142      * function. A <em>hash strategy</em>, thus, specifies an {@linkplain
143      * #equals(Object,Object) equality method} and a {@linkplain
144      * #hashCode(Object) hash function}, with the obvious property that
145      * equal objects must have the same hash code.
146      *
147      * <P>If your custom collection must be able to contain <code>null</code>,
148      * then your strategy must be able to handle <code>null</code>, too.
149      */
150
151     public interface Strategy<K> {
152
153         /** Returns the hash code of the specified object with respect to this hash strategy.
154          *
155          * @param o an object (or <code>null</code>).
156          * @return the hash code of the given object with respect to this hash strategy.
157          */
158
159         public int hashCode( K o );
160
161         /** Returns true if the given objects are equal with respect to this hash strategy.
162          *
163          * @param a an object (or <code>null</code>).
164          * @param b another object (or <code>null</code>).
165          * @return true if the two specified objects are equal with respect to this hash strategy.
166          */
167         public boolean equals( K a, K b );
168     }
169
170 }
171
Popular Tags