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  ;
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   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  [] _set;
50  
51      /** the strategy used to hash objects in this collection. */
52      protected TObjectHashingStrategy<T> _hashingStrategy;
53  
54      protected static final Object   REMOVED = new Object  (), FREE = new Object  ();
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  [])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  [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  [] 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   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  [] set;
201         Object   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  [] set;
241         Object   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   o1, Object   o2)
343         throws IllegalArgumentException   {
344         throw new IllegalArgumentException  ("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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags