THash


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  /**
22   * Base class for hashtables that use open addressing to resolve
23   * collisions.
24   *
25   * Created: Wed Nov 28 21:11:16 2001
26   *
27   * @author Eric D. Friedman
28   * @author Rob Eden (auto-compaction)
29   *
30   * @version $Id: THash.java,v 1.8 2006/11/10 23:27:55 robeden Exp $
31   */
32  
33  abstract public class THash implements Cloneable   {
34      /** the current number of occupied slots in the hash. */
35      protected transient int _size;
36  
37      /** the current number of free slots in the hash. */
38      protected transient int _free;
39  
40      /** the load above which rehashing occurs. */
41      protected static final float DEFAULT_LOAD_FACTOR = 0.5f;
42  
43      /** the default initial capacity for the hash table.  This is one
44       * less than a prime value because one is added to it when
45       * searching for a prime capacity to account for the free slot
46       * required by open addressing. Thus, the real default capacity is
47       * 11. */
48      protected static final int DEFAULT_INITIAL_CAPACITY = 10;
49  
50      /** Determines how full the internal table can become before
51       * rehashing is required. This must be a value in the range: 0.0 <
52       * loadFactor < 1.0.  The default value is 0.5, which is about as
53       * large as you can get in open addressing without hurting
54       * performance.  Cf. Knuth, Volume 3., Chapter 6.
55       */
56      protected float _loadFactor;
57  
58      /**
59       * The maximum number of elements allowed without allocating more
60       * space.
61       */
62      protected int _maxSize;
63  
64  
65      /**
66       * The number of removes that should be performed before an auto-compaction occurs.
67       */
68      protected int _autoCompactRemovesRemaining;
69  
70      /**
71       * The auto-compaction falctor for the table.
72       *
73       * @see #setAutoCompactionFactor
74       */
75      protected float _autoCompactionFactor;
76  
77  
78  
79      /**
80       * Creates a new <code>THash</code> instance with the default
81       * capacity and load factor.
82       */
83      public THash() {
84          this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
85      }
86  
87      /**
88       * Creates a new <code>THash</code> instance with a prime capacity
89       * at or near the specified capacity and with the default load
90       * factor.
91       *
92       * @param initialCapacity an <code>int</code> value
93       */
94      public THash(int initialCapacity) {
95          this(initialCapacity, DEFAULT_LOAD_FACTOR);
96      }
97  
98      /**
99       * Creates a new <code>THash</code> instance with a prime capacity
100      * at or near the minimum needed to hold <tt>initialCapacity</tt>
101      * elements with load factor <tt>loadFactor</tt> without triggering
102      * a rehash.
103      *
104      * @param initialCapacity an <code>int</code> value
105      * @param loadFactor a <code>float</code> value
106      */
107     public THash(int initialCapacity, float loadFactor) {
108         super();
109         _loadFactor = loadFactor;
110 
111         // Through testing, the load factor (especially the default load factor) has been
112         // found to be a pretty good starting auto-compaction factor.
113         _autoCompactionFactor = loadFactor;
114         
115         setUp((int)Math.ceil(initialCapacity / loadFactor));
116     }
117 
118     public Object   clone() {
119         try {
120             return super.clone();
121         } catch (CloneNotSupportedException   cnse) {
122             return null; // it's supported
123         }
124     }
125 
126     /**
127      * Tells whether this set is currently holding any elements.
128      *
129      * @return a <code>boolean</code> value
130      */
131     public boolean isEmpty() {
132         return 0 == _size;
133     }
134 
135     /**
136      * Returns the number of distinct elements in this collection.
137      *
138      * @return an <code>int</code> value
139      */
140     public int size() {
141         return _size;
142     }
143 
144     /**
145      * @return the current physical capacity of the hash table.
146      */
147     abstract protected int capacity();
148     
149     /**
150      * Ensure that this hashtable has sufficient capacity to hold
151      * <tt>desiredCapacity<tt> <b>additional</b> elements without
152      * requiring a rehash.  This is a tuning method you can call
153      * before doing a large insert.
154      *
155      * @param desiredCapacity an <code>int</code> value
156      */
157     public void ensureCapacity(int desiredCapacity) {
158         if (desiredCapacity > (_maxSize - size())) {
159             rehash(PrimeFinder.nextPrime((int)Math.ceil(desiredCapacity + size() /
160                                                         _loadFactor) + 1));
161             computeMaxSize(capacity());
162         }
163     }
164     
165     /**
166      * Compresses the hashtable to the minimum prime size (as defined
167      * by PrimeFinder) that will hold all of the elements currently in
168      * the table.  If you have done a lot of <tt>remove</tt>
169      * operations and plan to do a lot of queries or insertions or
170      * iteration, it is a good idea to invoke this method.  Doing so
171      * will accomplish two things:
172      *
173      * <ol>
174      * <li> You'll free memory allocated to the table but no
175      * longer needed because of the remove()s.</li>
176      *
177      * <li> You'll get better query/insert/iterator performance
178      * because there won't be any <tt>REMOVED</tt> slots to skip
179      * over when probing for indices in the table.</li>
180      * </ol>
181      */
182     public void compact() {
183         // need at least one free spot for open addressing
184         rehash(PrimeFinder.nextPrime((int)Math.ceil(size()/_loadFactor) + 1));
185         computeMaxSize(capacity());
186 
187         // If auto-compaction is enabled, re-determine the compaction interval
188         if ( _autoCompactionFactor != 0 ) {
189             computeNextAutoCompactionAmount(size());
190         }
191     }
192 
193 
194     /**
195      * The auto-compaction factor controls whether and when a table performs a
196      * {@link #compact} automatcially after a certain number of remove operations.
197      * If the value is non-zero, the number of removes that need to occur for
198      * auto-compaction is the size of table at the time of the previous compaction
199      * (or the initial capacity) multiplied by this factor.
200      * <p>
201      * Setting this value to zero will disable auto-compaction.
202      */
203     public void setAutoCompactionFactor( float factor ) {
204         if ( factor < 0 ) {
205             throw new IllegalArgumentException  ( "Factor must be >= 0: " + factor );
206         }
207 
208         _autoCompactionFactor = factor;
209     }
210 
211     /**
212      * @see #setAutoCompactionFactor
213      */
214     public float getAutoCompactionFactor() {
215         return _autoCompactionFactor;
216     }
217 
218 
219     /**
220      * This simply calls {@link #compact compact}.  It is included for 
221      * symmetry with other collection classes.  Note that the name of this
222      * method is somewhat misleading (which is why we prefer
223      * <tt>compact</tt>) as the load factor may require capacity above
224      * and beyond the size of this collection.
225      *
226      * @see #compact
227      */
228     public final void trimToSize() {
229         compact();
230     }
231 
232     /**
233      * Delete the record at <tt>index</tt>.  Reduces the size of the
234      * collection by one.
235      *
236      * @param index an <code>int</code> value
237      */
238     protected void removeAt(int index) {
239         _size--;
240 
241         // If auto-compaction is enabled, see if we need to compact
242         if ( _autoCompactionFactor != 0 ) {
243             _autoCompactRemovesRemaining--;
244 
245             if ( _autoCompactRemovesRemaining == 0 ) {
246                 // Do the compact
247                 // NOTE: this will cause the next compaction interval to be calculated
248                 compact();
249             }
250         }
251     }
252 
253     /**
254      * Empties the collection.
255      */
256     public void clear() {
257         _size = 0;
258         _free = capacity();
259     }
260     
261     /**
262      * initializes the hashtable to a prime capacity which is at least
263      * <tt>initialCapacity + 1</tt>.  
264      *
265      * @param initialCapacity an <code>int</code> value
266      * @return the actual capacity chosen
267      */
268     protected int setUp(int initialCapacity) {
269         int capacity;
270 
271         capacity = PrimeFinder.nextPrime(initialCapacity);
272         computeMaxSize(capacity);
273         computeNextAutoCompactionAmount(initialCapacity);
274 
275         return capacity;
276     }
277 
278     /**
279      * Rehashes the set.
280      *
281      * @param newCapacity an <code>int</code> value
282      */
283     protected abstract void rehash(int newCapacity);
284 
285     /**
286      * Computes the values of maxSize. There will always be at least
287      * one free slot required.
288      *
289      * @param capacity an <code>int</code> value
290      */
291     private final void computeMaxSize(int capacity) {
292         // need at least one free slot for open addressing
293         _maxSize = Math.min(capacity - 1,
294                             (int)Math.floor(capacity * _loadFactor));
295         _free = capacity - _size; // reset the free element count
296     }
297 
298 
299     /**
300      * Computes the number of removes that need to happen before the next auto-compaction
301      * will occur.
302      */
303     private void computeNextAutoCompactionAmount( int size ) {
304         if ( _autoCompactionFactor != 0 ) {
305             _autoCompactRemovesRemaining = Math.round( size * _autoCompactionFactor );
306         }
307     }
308 
309 
310     /**
311      * After an insert, this hook is called to adjust the size/free
312      * values of the set and to perform rehashing if necessary.
313      */
314     protected final void postInsertHook(boolean usedFreeSlot) {
315         if (usedFreeSlot) {
316             _free--;
317         }
318         
319         // rehash whenever we exhaust the available space in the table
320         if (++_size > _maxSize || _free == 0) {
321             // choose a new capacity suited to the new state of the table
322             // if we've grown beyond our maximum size, double capacity;
323             // if we've exhausted the free spots, rehash to the same capacity,
324             // which will free up any stale removed slots for reuse.
325             int newCapacity = _size > _maxSize ? PrimeFinder.nextPrime(capacity() << 1) : capacity();
326             rehash(newCapacity);
327             computeMaxSize(capacity());
328         }
329     }
330 
331   protected int calculateGrownCapacity() {
332     return capacity() << 1;
333   }
334 }// THash
335
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags