KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > trove > TIntHash


1 ///////////////////////////////////////////////////////////////////////////////
2 // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
3 //
4 // This library is free software; you can redistribute it and/or
5 // modify it under the terms of the GNU Lesser General Public
6 // License as published by the Free Software Foundation; either
7 // version 2.1 of the License, or (at your option) any later version.
8 //
9 // This library is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU Lesser General Public
15 // License along with this program; if not, write to the Free Software
16 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 ///////////////////////////////////////////////////////////////////////////////
18
19 package gnu.trove;
20
21 import java.io.Serializable;
22
23 /**
24  * An open addressed hashing implementation for int primitives.
25  *
26  * Created: Sun Nov 4 08:56:06 2001
27  *
28  * @author Eric D. Friedman
29  * @version $Id: TIntHash.java,v 1.15 2004/11/09 15:48:46 ericdf Exp $
30  */
31
32 abstract public class TIntHash extends TPrimitiveHash
33     implements Serializable, TIntHashingStrategy {
34
35     /** the set of ints */
36     protected transient int[] _set;
37
38     /** strategy used to hash values in this collection */
39     protected TIntHashingStrategy _hashingStrategy;
40
41     /**
42      * Creates a new <code>TIntHash</code> instance with the default
43      * capacity and load factor.
44      */
45     public TIntHash() {
46         super();
47         this._hashingStrategy = this;
48     }
49
50     /**
51      * Creates a new <code>TIntHash</code> instance whose capacity
52      * is the next highest prime above <tt>initialCapacity + 1</tt>
53      * unless that value is already prime.
54      *
55      * @param initialCapacity an <code>int</code> value
56      */
57     public TIntHash(int initialCapacity) {
58         super(initialCapacity);
59         this._hashingStrategy = this;
60     }
61
62     /**
63      * Creates a new <code>TIntHash</code> instance with a prime
64      * value at or near the specified capacity and load factor.
65      *
66      * @param initialCapacity used to find a prime capacity for the table.
67      * @param loadFactor used to calculate the threshold over which
68      * rehashing takes place.
69      */
70     public TIntHash(int initialCapacity, float loadFactor) {
71         super(initialCapacity, loadFactor);
72         this._hashingStrategy = this;
73     }
74
75     /**
76      * Creates a new <code>TIntHash</code> instance with the default
77      * capacity and load factor.
78      * @param strategy used to compute hash codes and to compare keys.
79      */
80     public TIntHash(TIntHashingStrategy strategy) {
81         super();
82         this._hashingStrategy = strategy;
83     }
84
85     /**
86      * Creates a new <code>TIntHash</code> instance whose capacity
87      * is the next highest prime above <tt>initialCapacity + 1</tt>
88      * unless that value is already prime.
89      *
90      * @param initialCapacity an <code>int</code> value
91      * @param strategy used to compute hash codes and to compare keys.
92      */
93     public TIntHash(int initialCapacity, TIntHashingStrategy strategy) {
94         super(initialCapacity);
95         this._hashingStrategy = strategy;
96     }
97
98     /**
99      * Creates a new <code>TIntHash</code> instance with a prime
100      * value at or near the specified capacity and load factor.
101      *
102      * @param initialCapacity used to find a prime capacity for the table.
103      * @param loadFactor used to calculate the threshold over which
104      * rehashing takes place.
105      * @param strategy used to compute hash codes and to compare keys.
106      */
107     public TIntHash(int initialCapacity, float loadFactor, TIntHashingStrategy strategy) {
108         super(initialCapacity, loadFactor);
109         this._hashingStrategy = strategy;
110     }
111
112     /**
113      * @return a deep clone of this collection
114      */
115     public Object clone() {
116         TIntHash h = (TIntHash)super.clone();
117         h._set = (int[])this._set.clone();
118         return h;
119     }
120
121     /**
122      * initializes the hashtable to a prime capacity which is at least
123      * <tt>initialCapacity + 1</tt>.
124      *
125      * @param initialCapacity an <code>int</code> value
126      * @return the actual capacity chosen
127      */
128     protected int setUp(int initialCapacity) {
129         int capacity;
130
131         capacity = super.setUp(initialCapacity);
132         _set = new int[capacity];
133         return capacity;
134     }
135     
136     /**
137      * Searches the set for <tt>val</tt>
138      *
139      * @param val an <code>int</code> value
140      * @return a <code>boolean</code> value
141      */
142     public boolean contains(int val) {
143         return index(val) >= 0;
144     }
145
146     /**
147      * Executes <tt>procedure</tt> for each element in the set.
148      *
149      * @param procedure a <code>TObjectProcedure</code> value
150      * @return false if the loop over the set terminated because
151      * the procedure returned false for some value.
152      */
153     public boolean forEach(TIntProcedure procedure) {
154         byte[] states = _states;
155         int[] set = _set;
156         for (int i = set.length; i-- > 0;) {
157             if (states[i] == FULL && ! procedure.execute(set[i])) {
158                 return false;
159             }
160         }
161         return true;
162     }
163
164     /**
165      * Releases the element currently stored at <tt>index</tt>.
166      *
167      * @param index an <code>int</code> value
168      */
169     protected void removeAt(int index) {
170         super.removeAt(index);
171         _set[index] = (int)0;
172     }
173
174     /**
175      * Locates the index of <tt>val</tt>.
176      *
177      * @param val an <code>int</code> value
178      * @return the index of <tt>val</tt> or -1 if it isn't in the set.
179      */
180     protected int index(int val) {
181         int hash, probe, index, length;
182         int[] set;
183         byte[] states;
184
185         states = _states;
186         set = _set;
187         length = states.length;
188         hash = _hashingStrategy.computeHashCode(val) & 0x7fffffff;
189         index = hash % length;
190
191         if (states[index] != FREE &&
192             (states[index] == REMOVED || set[index] != val)) {
193             // see Knuth, p. 529
194 probe = 1 + (hash % (length - 2));
195
196             do {
197                 index -= probe;
198                 if (index < 0) {
199                     index += length;
200                 }
201             } while (states[index] != FREE &&
202                      (states[index] == REMOVED || set[index] != val));
203         }
204
205         return states[index] == FREE ? -1 : index;
206     }
207
208     /**
209      * Locates the index at which <tt>val</tt> can be inserted. if
210      * there is already a value equal()ing <tt>val</tt> in the set,
211      * returns that value as a negative integer.
212      *
213      * @param val an <code>int</code> value
214      * @return an <code>int</code> value
215      */
216     protected int insertionIndex(int val) {
217         int hash, probe, index, length;
218         int[] set;
219         byte[] states;
220
221         states = _states;
222         set = _set;
223         length = states.length;
224         hash = _hashingStrategy.computeHashCode(val) & 0x7fffffff;
225         index = hash % length;
226
227         if (states[index] == FREE) {
228             return index; // empty, all done
229 } else if (states[index] == FULL && set[index] == val) {
230             return -index -1; // already stored
231 } else { // already FULL or REMOVED, must probe
232 // compute the double hash
233 probe = 1 + (hash % (length - 2));
234
235             // if the slot we landed on is FULL (but not removed), probe
236 // until we find an empty slot, a REMOVED slot, or an element
237 // equal to the one we are trying to insert.
238 // finding an empty slot means that the value is not present
239 // and that we should use that slot as the insertion point;
240 // finding a REMOVED slot means that we need to keep searching,
241 // however we want to remember the offset of that REMOVED slot
242 // so we can reuse it in case a "new" insertion (i.e. not an update)
243 // is possible.
244 // finding a matching value means that we've found that our desired
245 // key is already in the table
246
247             if (states[index] != REMOVED) {
248                 // starting at the natural offset, probe until we find an
249 // offset that isn't full.
250 do {
251                     index -= probe;
252                     if (index < 0) {
253                         index += length;
254                     }
255                 } while (states[index] == FULL && set[index] != val);
256             }
257
258             // if the index we found was removed: continue probing until we
259 // locate a free location or an element which equal()s the
260 // one we have.
261 if (states[index] == REMOVED) {
262                 int firstRemoved = index;
263                 while (states[index] != FREE &&
264                        (states[index] == REMOVED || set[index] != val)) {
265                     index -= probe;
266                     if (index < 0) {
267                         index += length;
268                     }
269                 }
270                 return states[index] == FULL ? -index -1 : firstRemoved;
271             }
272             // if it's full, the key is already stored
273 return states[index] == FULL ? -index -1 : index;
274         }
275     }
276
277     /**
278      * Default implementation of TIntHashingStrategy:
279      * delegates hashing to HashFunctions.hash(int).
280      *
281      * @param the value to hash
282      * @return the hashcode.
283      */
284     public final int computeHashCode(int val) {
285         return HashFunctions.hash(val);
286     }
287 } // TIntHash
288
Popular Tags