001: ///////////////////////////////////////////////////////////////////////////////
002: // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
003: //
004: // This library is free software; you can redistribute it and/or
005: // modify it under the terms of the GNU Lesser General Public
006: // License as published by the Free Software Foundation; either
007: // version 2.1 of the License, or (at your option) any later version.
008: //
009: // This library is distributed in the hope that it will be useful,
010: // but WITHOUT ANY WARRANTY; without even the implied warranty of
011: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: // GNU General Public License for more details.
013: //
014: // You should have received a copy of the GNU Lesser General Public
015: // License along with this program; if not, write to the Free Software
016: // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
017: ///////////////////////////////////////////////////////////////////////////////
018:
019: package gnu.trove;
020:
021: /**
022: * Base class for hashtables that use open addressing to resolve
023: * collisions.
024: *
025: * Created: Wed Nov 28 21:11:16 2001
026: *
027: * @author Eric D. Friedman
028: * @author Rob Eden (auto-compaction)
029: *
030: * @version $Id: THash.java,v 1.10 2007/11/01 16:08:14 robeden Exp $
031: */
032:
033: abstract public class THash implements Cloneable {
034: /** the current number of occupied slots in the hash. */
035: protected transient int _size;
036:
037: /** the current number of free slots in the hash. */
038: protected transient int _free;
039:
040: /** the load above which rehashing occurs. */
041: protected static final float DEFAULT_LOAD_FACTOR = 0.5f;
042:
043: /** the default initial capacity for the hash table. This is one
044: * less than a prime value because one is added to it when
045: * searching for a prime capacity to account for the free slot
046: * required by open addressing. Thus, the real default capacity is
047: * 11. */
048: protected static final int DEFAULT_INITIAL_CAPACITY = 10;
049:
050: /** Determines how full the internal table can become before
051: * rehashing is required. This must be a value in the range: 0.0 <
052: * loadFactor < 1.0. The default value is 0.5, which is about as
053: * large as you can get in open addressing without hurting
054: * performance. Cf. Knuth, Volume 3., Chapter 6.
055: */
056: protected float _loadFactor;
057:
058: /**
059: * The maximum number of elements allowed without allocating more
060: * space.
061: */
062: protected int _maxSize;
063:
064: /**
065: * The number of removes that should be performed before an auto-compaction occurs.
066: */
067: protected int _autoCompactRemovesRemaining;
068:
069: /**
070: * The auto-compaction factor for the table.
071: *
072: * @see #setAutoCompactionFactor
073: */
074: protected float _autoCompactionFactor;
075:
076: /**
077: * @see
078: */
079: private boolean _autoCompactTemporaryDisable = false;
080:
081: /**
082: * Creates a new <code>THash</code> instance with the default
083: * capacity and load factor.
084: */
085: public THash() {
086: this (DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
087: }
088:
089: /**
090: * Creates a new <code>THash</code> instance with a prime capacity
091: * at or near the specified capacity and with the default load
092: * factor.
093: *
094: * @param initialCapacity an <code>int</code> value
095: */
096: public THash(int initialCapacity) {
097: this (initialCapacity, DEFAULT_LOAD_FACTOR);
098: }
099:
100: /**
101: * Creates a new <code>THash</code> instance with a prime capacity
102: * at or near the minimum needed to hold <tt>initialCapacity</tt>
103: * elements with load factor <tt>loadFactor</tt> without triggering
104: * a rehash.
105: *
106: * @param initialCapacity an <code>int</code> value
107: * @param loadFactor a <code>float</code> value
108: */
109: public THash(int initialCapacity, float loadFactor) {
110: super ();
111: _loadFactor = loadFactor;
112:
113: // Through testing, the load factor (especially the default load factor) has been
114: // found to be a pretty good starting auto-compaction factor.
115: _autoCompactionFactor = loadFactor;
116:
117: setUp((int) Math.ceil(initialCapacity / loadFactor));
118: }
119:
120: public Object clone() {
121: try {
122: return super .clone();
123: } catch (CloneNotSupportedException cnse) {
124: return null; // it's supported
125: }
126: }
127:
128: /**
129: * Tells whether this set is currently holding any elements.
130: *
131: * @return a <code>boolean</code> value
132: */
133: public boolean isEmpty() {
134: return 0 == _size;
135: }
136:
137: /**
138: * Returns the number of distinct elements in this collection.
139: *
140: * @return an <code>int</code> value
141: */
142: public int size() {
143: return _size;
144: }
145:
146: /**
147: * @return the current physical capacity of the hash table.
148: */
149: abstract protected int capacity();
150:
151: /**
152: * Ensure that this hashtable has sufficient capacity to hold
153: * <tt>desiredCapacity<tt> <b>additional</b> elements without
154: * requiring a rehash. This is a tuning method you can call
155: * before doing a large insert.
156: *
157: * @param desiredCapacity an <code>int</code> value
158: */
159: public void ensureCapacity(int desiredCapacity) {
160: if (desiredCapacity > (_maxSize - size())) {
161: rehash(PrimeFinder.nextPrime((int) Math
162: .ceil(desiredCapacity + size() / _loadFactor) + 1));
163: computeMaxSize(capacity());
164: }
165: }
166:
167: /**
168: * Compresses the hashtable to the minimum prime size (as defined
169: * by PrimeFinder) that will hold all of the elements currently in
170: * the table. If you have done a lot of <tt>remove</tt>
171: * operations and plan to do a lot of queries or insertions or
172: * iteration, it is a good idea to invoke this method. Doing so
173: * will accomplish two things:
174: *
175: * <ol>
176: * <li> You'll free memory allocated to the table but no
177: * longer needed because of the remove()s.</li>
178: *
179: * <li> You'll get better query/insert/iterator performance
180: * because there won't be any <tt>REMOVED</tt> slots to skip
181: * over when probing for indices in the table.</li>
182: * </ol>
183: */
184: public void compact() {
185: // need at least one free spot for open addressing
186: rehash(PrimeFinder.nextPrime((int) Math.ceil(size()
187: / _loadFactor) + 1));
188: computeMaxSize(capacity());
189:
190: // If auto-compaction is enabled, re-determine the compaction interval
191: if (_autoCompactionFactor != 0) {
192: computeNextAutoCompactionAmount(size());
193: }
194: }
195:
196: /**
197: * The auto-compaction factor controls whether and when a table performs a
198: * {@link #compact} automatically after a certain number of remove operations.
199: * If the value is non-zero, the number of removes that need to occur for
200: * auto-compaction is the size of table at the time of the previous compaction
201: * (or the initial capacity) multiplied by this factor.
202: * <p>
203: * Setting this value to zero will disable auto-compaction.
204: */
205: public void setAutoCompactionFactor(float factor) {
206: if (factor < 0) {
207: throw new IllegalArgumentException("Factor must be >= 0: "
208: + factor);
209: }
210:
211: _autoCompactionFactor = factor;
212: }
213:
214: /**
215: * @see #setAutoCompactionFactor
216: */
217: public float getAutoCompactionFactor() {
218: return _autoCompactionFactor;
219: }
220:
221: /**
222: * This simply calls {@link #compact compact}. It is included for
223: * symmetry with other collection classes. Note that the name of this
224: * method is somewhat misleading (which is why we prefer
225: * <tt>compact</tt>) as the load factor may require capacity above
226: * and beyond the size of this collection.
227: *
228: * @see #compact
229: */
230: public final void trimToSize() {
231: compact();
232: }
233:
234: /**
235: * Delete the record at <tt>index</tt>. Reduces the size of the
236: * collection by one.
237: *
238: * @param index an <code>int</code> value
239: */
240: protected void removeAt(int index) {
241: _size--;
242:
243: // If auto-compaction is enabled, see if we need to compact
244: if (_autoCompactionFactor != 0) {
245: _autoCompactRemovesRemaining--;
246:
247: if (!_autoCompactTemporaryDisable
248: && _autoCompactRemovesRemaining <= 0) {
249: // Do the compact
250: // NOTE: this will cause the next compaction interval to be calculated
251: compact();
252: }
253: }
254: }
255:
256: /**
257: * Empties the collection.
258: */
259: public void clear() {
260: _size = 0;
261: _free = capacity();
262: }
263:
264: /**
265: * initializes the hashtable to a prime capacity which is at least
266: * <tt>initialCapacity + 1</tt>.
267: *
268: * @param initialCapacity an <code>int</code> value
269: * @return the actual capacity chosen
270: */
271: protected int setUp(int initialCapacity) {
272: int capacity;
273:
274: capacity = PrimeFinder.nextPrime(initialCapacity);
275: computeMaxSize(capacity);
276: computeNextAutoCompactionAmount(initialCapacity);
277:
278: return capacity;
279: }
280:
281: /**
282: * Rehashes the set.
283: *
284: * @param newCapacity an <code>int</code> value
285: */
286: protected abstract void rehash(int newCapacity);
287:
288: /**
289: * Temporarily disables auto-compaction. MUST be followed by calling
290: * {@link #reenableAutoCompaction}.
291: */
292: protected void tempDisableAutoCompaction() {
293: _autoCompactTemporaryDisable = true;
294: }
295:
296: /**
297: * Re-enable auto-compaction after it was disabled via
298: * {@link #tempDisableAutoCompaction()}.
299: *
300: * @param check_for_compaction True if compaction should be performed if needed
301: * before returning. If false, no compaction will be
302: * performed.
303: */
304: protected void reenableAutoCompaction(boolean check_for_compaction) {
305: _autoCompactTemporaryDisable = false;
306:
307: if (check_for_compaction && _autoCompactRemovesRemaining <= 0
308: && _autoCompactionFactor != 0) {
309:
310: // Do the compact
311: // NOTE: this will cause the next compaction interval to be calculated
312: compact();
313: }
314: }
315:
316: /**
317: * Computes the values of maxSize. There will always be at least
318: * one free slot required.
319: *
320: * @param capacity an <code>int</code> value
321: */
322: private final void computeMaxSize(int capacity) {
323: // need at least one free slot for open addressing
324: _maxSize = Math.min(capacity - 1, (int) Math.floor(capacity
325: * _loadFactor));
326: _free = capacity - _size; // reset the free element count
327: }
328:
329: /**
330: * Computes the number of removes that need to happen before the next auto-compaction
331: * will occur.
332: */
333: private void computeNextAutoCompactionAmount(int size) {
334: if (_autoCompactionFactor != 0) {
335: _autoCompactRemovesRemaining = Math.round(size
336: * _autoCompactionFactor);
337: }
338: }
339:
340: /**
341: * After an insert, this hook is called to adjust the size/free
342: * values of the set and to perform rehashing if necessary.
343: */
344: protected final void postInsertHook(boolean usedFreeSlot) {
345: if (usedFreeSlot) {
346: _free--;
347: }
348:
349: // rehash whenever we exhaust the available space in the table
350: if (++_size > _maxSize || _free == 0) {
351: // choose a new capacity suited to the new state of the table
352: // if we've grown beyond our maximum size, double capacity;
353: // if we've exhausted the free spots, rehash to the same capacity,
354: // which will free up any stale removed slots for reuse.
355: int newCapacity = _size > _maxSize ? PrimeFinder
356: .nextPrime(capacity() << 1) : capacity();
357: rehash(newCapacity);
358: computeMaxSize(capacity());
359: }
360: }
361:
362: protected int calculateGrownCapacity() {
363: return capacity() << 1;
364: }
365: }// THash
|