KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > trove > TPrimitiveHash


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  * The base class for hashtables of primitive values. Since there is
23  * no notion of object equality for primitives, it isn't possible to
24  * use a `REMOVED' object to track deletions in an open-addressed table.
25  * So, we have to resort to using a parallel `bookkeeping' array of bytes,
26  * in which flags can be set to indicate that a particular slot in the
27  * hash table is FREE, FULL, or REMOVED.
28  *
29  * Created: Fri Jan 11 18:55:16 2002
30  *
31  * @author Eric D. Friedman
32  * @version $Id: TPrimitiveHash.java,v 1.4 2006/11/10 23:27:57 robeden Exp $
33  */
34
35 abstract public class TPrimitiveHash extends THash {
36     /** flags indicating whether each position in the hash is
37      * FREE, FULL, or REMOVED */
38     protected transient byte[] _states;
39
40     /* constants used for state flags */
41
42     /** flag indicating that a slot in the hashtable is available */
43     protected static final byte FREE = 0;
44
45     /** flag indicating that a slot in the hashtable is occupied */
46     protected static final byte FULL = 1;
47
48     /** flag indicating that the value of a slot in the hashtable
49      * was deleted */
50     protected static final byte REMOVED = 2;
51
52     /**
53      * Creates a new <code>THash</code> instance with the default
54      * capacity and load factor.
55      */
56     public TPrimitiveHash() {
57         super();
58     }
59
60     /**
61      * Creates a new <code>TPrimitiveHash</code> instance with a prime
62      * capacity at or near the specified capacity and with the default
63      * load factor.
64      *
65      * @param initialCapacity an <code>int</code> value
66      */
67     public TPrimitiveHash(int initialCapacity) {
68         this(initialCapacity, DEFAULT_LOAD_FACTOR);
69     }
70
71     /**
72      * Creates a new <code>TPrimitiveHash</code> instance with a prime
73      * capacity at or near the minimum needed to hold
74      * <tt>initialCapacity<tt> elements with load factor
75      * <tt>loadFactor</tt> without triggering a rehash.
76      *
77      * @param initialCapacity an <code>int</code> value
78      * @param loadFactor a <code>float</code> value
79      */
80     public TPrimitiveHash(int initialCapacity, float loadFactor) {
81         super();
82         _loadFactor = loadFactor;
83         setUp((int)Math.ceil(initialCapacity / loadFactor));
84     }
85
86     public Object JavaDoc clone() {
87         TPrimitiveHash h = (TPrimitiveHash)super.clone();
88         h._states = (byte[])this._states.clone();
89         return h;
90     }
91
92     /**
93      * Returns the capacity of the hash table. This is the true
94      * physical capacity, without adjusting for the load factor.
95      *
96      * @return the physical capacity of the hash table.
97      */
98     protected int capacity() {
99         return _states.length;
100     }
101
102     /**
103      * Delete the record at <tt>index</tt>.
104      *
105      * @param index an <code>int</code> value
106      */
107     protected void removeAt(int index) {
108         _states[index] = REMOVED;
109         super.removeAt(index);
110     }
111
112     /**
113      * initializes the hashtable to a prime capacity which is at least
114      * <tt>initialCapacity + 1</tt>.
115      *
116      * @param initialCapacity an <code>int</code> value
117      * @return the actual capacity chosen
118      */
119     protected int setUp(int initialCapacity) {
120         int capacity;
121
122         capacity = super.setUp(initialCapacity);
123         _states = new byte[capacity];
124         return capacity;
125     }
126 } // TPrimitiveHash
127
Popular Tags