KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > trove > TObjectHash


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.util.Arrays JavaDoc;
22
23
24 /**
25  * An open addressed hashing implementation for Object types.
26  *
27  * Created: Sun Nov 4 08:56:06 2001
28  *
29  * @author Eric D. Friedman
30  * @version $Id: TObjectHash.java,v 1.19 2006/11/15 21:31:42 robeden Exp $
31  */

32 abstract public class TObjectHash<T> extends THash implements TObjectHashingStrategy<T> {
33     static final long serialVersionUID = -3461112548087185871L;
34
35     private static final boolean USE_EXPERIMENTAL_PROBE;
36     static {
37         boolean use_new_probe;
38         try {
39             use_new_probe = System.getProperty( "gnu.trove.use_experimatal_probe" ) != null;
40         }
41         catch( Exception JavaDoc ex ) { // for security exceptions
42
use_new_probe = false;
43         }
44         USE_EXPERIMENTAL_PROBE = use_new_probe;
45     }
46
47
48     /** the set of Objects */
49     protected transient Object JavaDoc[] _set;
50
51     /** the strategy used to hash objects in this collection. */
52     protected TObjectHashingStrategy<T> _hashingStrategy;
53
54     protected static final Object JavaDoc REMOVED = new Object JavaDoc(), FREE = new Object JavaDoc();
55
56     /**
57      * Creates a new <code>TObjectHash</code> instance with the
58      * default capacity and load factor.
59      */

60     public TObjectHash() {
61         super();
62         this._hashingStrategy = this;
63     }
64
65     /**
66      * Creates a new <code>TObjectHash</code> instance with the
67      * default capacity and load factor and a custom hashing strategy.
68      *
69      * @param strategy used to compute hash codes and to compare objects.
70      */

71     public TObjectHash(TObjectHashingStrategy<T> strategy) {
72         super();
73         this._hashingStrategy = strategy;
74     }
75
76     /**
77      * Creates a new <code>TObjectHash</code> instance whose capacity
78      * is the next highest prime above <tt>initialCapacity + 1</tt>
79      * unless that value is already prime.
80      *
81      * @param initialCapacity an <code>int</code> value
82      */

83     public TObjectHash(int initialCapacity) {
84         super(initialCapacity);
85         this._hashingStrategy = this;
86     }
87
88     /**
89      * Creates a new <code>TObjectHash</code> instance whose capacity
90      * is the next highest prime above <tt>initialCapacity + 1</tt>
91      * unless that value is already prime. Uses the specified custom
92      * hashing strategy.
93      *
94      * @param initialCapacity an <code>int</code> value
95      * @param strategy used to compute hash codes and to compare objects.
96      */

97     public TObjectHash(int initialCapacity, TObjectHashingStrategy<T> strategy) {
98         super(initialCapacity);
99         this._hashingStrategy = strategy;
100     }
101
102     /**
103      * Creates a new <code>TObjectHash</code> instance with a prime
104      * value at or near the specified capacity and load factor.
105      *
106      * @param initialCapacity used to find a prime capacity for the table.
107      * @param loadFactor used to calculate the threshold over which
108      * rehashing takes place.
109      */

110     public TObjectHash(int initialCapacity, float loadFactor) {
111         super(initialCapacity, loadFactor);
112         this._hashingStrategy = this;
113     }
114
115     /**
116      * Creates a new <code>TObjectHash</code> instance with a prime
117      * value at or near the specified capacity and load factor. Uses
118      * the specified custom hashing strategy.
119      *
120      * @param initialCapacity used to find a prime capacity for the table.
121      * @param loadFactor used to calculate the threshold over which
122      * rehashing takes place.
123      * @param strategy used to compute hash codes and to compare objects.
124      */

125     public TObjectHash(int initialCapacity, float loadFactor, TObjectHashingStrategy<T> strategy) {
126         super(initialCapacity, loadFactor);
127         this._hashingStrategy = strategy;
128     }
129
130     /**
131      * @return a shallow clone of this collection
132      */

133     public TObjectHash<T> clone() {
134         TObjectHash<T> h = (TObjectHash<T>)super.clone();
135         h._set = (Object JavaDoc[])this._set.clone();
136         return h;
137     }
138
139     protected int capacity() {
140         return _set.length;
141     }
142
143     protected void removeAt(int index) {
144         _set[index] = REMOVED;
145         super.removeAt(index);
146     }
147
148     /**
149      * initializes the Object set of this hash table.
150      *
151      * @param initialCapacity an <code>int</code> value
152      * @return an <code>int</code> value
153      */

154     protected int setUp(int initialCapacity) {
155         int capacity;
156
157         capacity = super.setUp(initialCapacity);
158         _set = new Object JavaDoc[capacity];
159         Arrays.fill(_set,FREE);
160         return capacity;
161     }
162
163     /**
164      * Executes <tt>procedure</tt> for each element in the set.
165      *
166      * @param procedure a <code>TObjectProcedure</code> value
167      * @return false if the loop over the set terminated because
168      * the procedure returned false for some value.
169      */

170     public boolean forEach(TObjectProcedure<T> procedure) {
171         Object JavaDoc[] set = _set;
172         for (int i = set.length; i-- > 0;) {
173             if (set[i] != FREE
174                 && set[i] != REMOVED
175                 && ! procedure.execute((T) set[i])) {
176                 return false;
177             }
178         }
179         return true;
180     }
181
182     /**
183      * Searches the set for <tt>obj</tt>
184      *
185      * @param obj an <code>Object</code> value
186      * @return a <code>boolean</code> value
187      */

188     public boolean contains(Object JavaDoc obj) {
189         return index((T) obj) >= 0;
190     }
191
192     /**
193      * Locates the index of <tt>obj</tt>.
194      *
195      * @param obj an <code>Object</code> value
196      * @return the index of <tt>obj</tt> or -1 if it isn't in the set.
197      */

198     protected int index(T obj) {
199         int hash, probe, index, length;
200         Object JavaDoc[] set;
201         Object JavaDoc cur;
202
203         set = _set;
204         length = set.length;
205         hash = _hashingStrategy.computeHashCode(obj) & 0x7fffffff;
206         index = hash % length;
207         cur = set[index];
208
209         if (cur != FREE
210             && (cur == REMOVED || ! _hashingStrategy.equals((T) cur, obj))) {
211             // see Knuth, p. 529
212
if ( USE_EXPERIMENTAL_PROBE ) probe = 1 + ((hash*9 & 0x7FFFFFFF) % (length - 2));
213             else probe = 1 + (hash % (length - 2));
214
215             do {
216                 index -= probe;
217                 if (index < 0) {
218                     index += length;
219                 }
220                 cur = set[index];
221             } while (cur != FREE
222                      && (cur == REMOVED || ! _hashingStrategy.equals((T) cur, obj)));
223         }
224
225         return cur == FREE ? -1 : index;
226     }
227
228     /**
229      * Locates the index at which <tt>obj</tt> can be inserted. if
230      * there is already a value equal()ing <tt>obj</tt> in the set,
231      * returns that value's index as <tt>-index - 1</tt>.
232      *
233      * @param obj an <code>Object</code> value
234      * @return the index of a FREE slot at which obj can be inserted
235      * or, if obj is already stored in the hash, the negative value of
236      * that index, minus 1: -index -1.
237      */

238     protected int insertionIndex(T obj) {
239         int hash, probe, index, length;
240         Object JavaDoc[] set;
241         Object JavaDoc cur;
242
243         set = _set;
244         length = set.length;
245         hash = _hashingStrategy.computeHashCode(obj) & 0x7fffffff;
246         index = hash % length;
247         cur = set[index];
248
249         if (cur == FREE) {
250             return index; // empty, all done
251
} else if (_hashingStrategy.equals((T) cur, obj)) {
252             return -index -1; // already stored
253
} else { // already FULL or REMOVED, must probe
254
// compute the double hash
255
if ( USE_EXPERIMENTAL_PROBE ) probe = 1 + ((hash*9 & 0x7FFFFFFF) % (length - 2));
256             else probe = 1 + (hash % (length - 2));
257
258             // if the slot we landed on is FULL (but not removed), probe
259
// until we find an empty slot, a REMOVED slot, or an element
260
// equal to the one we are trying to insert.
261
// finding an empty slot means that the value is not present
262
// and that we should use that slot as the insertion point;
263
// finding a REMOVED slot means that we need to keep searching,
264
// however we want to remember the offset of that REMOVED slot
265
// so we can reuse it in case a "new" insertion (i.e. not an update)
266
// is possible.
267
// finding a matching value means that we've found that our desired
268
// key is already in the table
269
if (cur != REMOVED) {
270                 // starting at the natural offset, probe until we find an
271
// offset that isn't full.
272
do {
273                     index -= probe;
274                     if (index < 0) {
275                         index += length;
276                     }
277                     cur = set[index];
278                 } while (cur != FREE
279                          && cur != REMOVED
280                          && ! _hashingStrategy.equals((T) cur, obj));
281             }
282
283             // if the index we found was removed: continue probing until we
284
// locate a free location or an element which equal()s the
285
// one we have.
286
if (cur == REMOVED) {
287                 int firstRemoved = index;
288                 while (cur != FREE
289                        && (cur == REMOVED || ! _hashingStrategy.equals((T) cur, obj))) {
290                     index -= probe;
291                     if (index < 0) {
292                         index += length;
293                     }
294                     cur = set[index];
295                 }
296                 // NOTE: cur cannot == REMOVED in this block
297
return (cur != FREE) ? -index -1 : firstRemoved;
298             }
299             // if it's full, the key is already stored
300
// NOTE: cur cannot equal REMOVE here (would have retuned already (see above)
301
return (cur != FREE) ? -index -1 : index;
302         }
303     }
304
305     /**
306      * This is the default implementation of TObjectHashingStrategy:
307      * it delegates hashing to the Object's hashCode method.
308      *
309      * @param o for which the hashcode is to be computed
310      * @return the hashCode
311      * @see Object#hashCode()
312      */

313     public final int computeHashCode(T o) {
314         return o == null ? 0 : o.hashCode();
315     }
316
317     /**
318      * This is the default implementation of TObjectHashingStrategy:
319      * it delegates equality comparisons to the first parameter's
320      * equals() method.
321      *
322      * @param o1 an <code>Object</code> value
323      * @param o2 an <code>Object</code> value
324      * @return true if the objects are equal
325      * @see Object#equals(Object)
326      */

327     public final boolean equals(T o1, T o2) {
328         return o1 == null ? o2 == null : o1.equals(o2);
329     }
330
331     /**
332      * Convenience methods for subclasses to use in throwing exceptions about
333      * badly behaved user objects employed as keys. We have to throw an
334      * IllegalArgumentException with a rather verbose message telling the
335      * user that they need to fix their object implementation to conform
336      * to the general contract for java.lang.Object.
337      *
338      * @param o1 the first of the equal elements with unequal hash codes.
339      * @param o2 the second of the equal elements with unequal hash codes.
340      * @exception IllegalArgumentException the whole point of this method.
341      */

342     protected final void throwObjectContractViolation(Object JavaDoc o1, Object JavaDoc o2)
343         throws IllegalArgumentException JavaDoc {
344         throw new IllegalArgumentException JavaDoc("Equal objects must have equal hashcodes. "
345                                            + "During rehashing, Trove discovered that "
346                                            + "the following two objects claim to be "
347                                            + "equal (as in java.lang.Object.equals()) "
348                                            + "but their hashCodes (or those calculated by "
349                                            + "your TObjectHashingStrategy) are not equal."
350                                            + "This violates the general contract of "
351                                            + "java.lang.Object.hashCode(). See bullet point two "
352                                            + "in that method's documentation. "
353                                            + "object #1 =" + o1
354                                            + "; object #2 =" + o2);
355     }
356 } // TObjectHash
357
Popular Tags