Source code: com/memoire/acme/AcmeIntHashtable.java
1
2
3 package com.memoire.acme;
4 import com.memoire.acme.*;
5
6 // AcmeIntHashtable - a Hashtable that uses ints as the keys
7 // This is 90% based on JavaSoft's java.util.Hashtable.
8 // Visit the ACME Labs Java page for up-to-date versions of this and other
9 // fine Java utilities: http://www.acme.com/java/
10
11 import java.util.*;
12
13 /// A Hashtable that uses ints as the keys.
14 // Use just like java.util.Hashtable, except that the keys must be ints.
15 // This is much faster than creating a new Integer for each access.
16 // @see java.util.Hashtable
17
18 public class AcmeIntHashtable extends Dictionary implements Cloneable
19 {
20 /// The hash table data.
21 private AcmeIntHashtableEntry table[];
22
23 /// The total number of entries in the hash table.
24 private int count;
25
26 /// Rehashes the table when count exceeds this threshold.
27 private int threshold;
28
29 /// The load factor for the hashtable.
30 private float loadFactor;
31
32 /// Constructs a new, empty hashtable with the specified initial
33 // capacity and the specified load factor.
34 // @param initialCapacity the initial number of buckets
35 // @param loadFactor a number between 0.0 and 1.0, it defines
36 // the threshold for rehashing the hashtable into
37 // a bigger one.
38 // @exception IllegalArgumentException If the initial capacity
39 // is less than or equal to zero.
40 // @exception IllegalArgumentException If the load factor is
41 // less than or equal to zero.
42 public AcmeIntHashtable( int initialCapacity, float loadFactor )
43 {
44 if ( initialCapacity <= 0 || loadFactor <= 0.0 )
45 throw new IllegalArgumentException();
46 this.loadFactor = loadFactor;
47 table = new AcmeIntHashtableEntry[initialCapacity];
48 threshold = (int) ( initialCapacity * loadFactor );
49 }
50
51 /// Constructs a new, empty hashtable with the specified initial
52 // capacity.
53 // @param initialCapacity the initial number of buckets
54 public AcmeIntHashtable( int initialCapacity )
55 {
56 this( initialCapacity, 0.75f );
57 }
58
59 /// Constructs a new, empty hashtable. A default capacity and load factor
60 // is used. Note that the hashtable will automatically grow when it gets
61 // full.
62 public AcmeIntHashtable()
63 {
64 this( 101, 0.75f );
65 }
66
67 /// Returns the number of elements contained in the hashtable.
68 public int size()
69 {
70 return count;
71 }
72
73 /// Returns true if the hashtable contains no elements.
74 public boolean isEmpty()
75 {
76 return count == 0;
77 }
78
79 /// Returns an enumeration of the hashtable's keys.
80 // @see AcmeIntHashtable#elements
81 public synchronized Enumeration keys()
82 {
83 return new AcmeIntHashtableEnumerator( table, true );
84 }
85
86 /// Returns an enumeration of the elements. Use the Enumeration methods
87 // on the returned object to fetch the elements sequentially.
88 // @see AcmeIntHashtable#keys
89 public synchronized Enumeration elements()
90 {
91 return new AcmeIntHashtableEnumerator( table, false );
92 }
93
94 /// Returns true if the specified object is an element of the hashtable.
95 // This operation is more expensive than the containsKey() method.
96 // @param value the value that we are looking for
97 // @exception NullPointerException If the value being searched
98 // for is equal to null.
99 // @see AcmeIntHashtable#containsKey
100 public synchronized boolean contains( Object value )
101 {
102 if ( value == null )
103 throw new NullPointerException();
104 AcmeIntHashtableEntry tab[] = table;
105 for ( int i = tab.length ; i-- > 0 ; )
106 {
107 for ( AcmeIntHashtableEntry e = tab[i] ; e != null ; e = e.next )
108 {
109 if ( e.value.equals( value ) )
110 return true;
111 }
112 }
113 return false;
114 }
115
116 /// Returns true if the collection contains an element for the key.
117 // @param key the key that we are looking for
118 // @see AcmeIntHashtable#contains
119 public synchronized boolean containsKey( int key )
120 {
121 AcmeIntHashtableEntry tab[] = table;
122 int hash = key;
123 int index = ( hash & 0x7FFFFFFF ) % tab.length;
124 for ( AcmeIntHashtableEntry e = tab[index] ; e != null ; e = e.next )
125 {
126 if ( e.hash == hash && e.key == key )
127 return true;
128 }
129 return false;
130 }
131
132 /// Gets the object associated with the specified key in the
133 // hashtable.
134 // @param key the specified key
135 // @returns the element for the key or null if the key
136 // is not defined in the hash table.
137 // @see AcmeIntHashtable#put
138 public synchronized Object get( int key )
139 {
140 AcmeIntHashtableEntry tab[] = table;
141 int hash = key;
142 int index = ( hash & 0x7FFFFFFF ) % tab.length;
143 for ( AcmeIntHashtableEntry e = tab[index] ; e != null ; e = e.next )
144 {
145 if ( e.hash == hash && e.key == key )
146 return e.value;
147 }
148 return null;
149 }
150
151 /// A get method that takes an Object, for compatibility with
152 // java.util.Dictionary. The Object must be an Integer.
153 public Object get( Object okey )
154 {
155 if ( ! ( okey instanceof Integer ) )
156 throw new InternalError( "key is not an Integer" );
157 Integer ikey = (Integer) okey;
158 int key = ikey.intValue();
159 return get( key );
160 }
161
162 /// Rehashes the content of the table into a bigger table.
163 // This method is called automatically when the hashtable's
164 // size exceeds the threshold.
165 protected void rehash()
166 {
167 int oldCapacity = table.length;
168 AcmeIntHashtableEntry oldTable[] = table;
169
170 int newCapacity = oldCapacity * 2 + 1;
171 AcmeIntHashtableEntry newTable[] = new AcmeIntHashtableEntry[newCapacity];
172
173 threshold = (int) ( newCapacity * loadFactor );
174 table = newTable;
175
176 for ( int i = oldCapacity ; i-- > 0 ; )
177 {
178 for ( AcmeIntHashtableEntry old = oldTable[i] ; old != null ; )
179 {
180 AcmeIntHashtableEntry e = old;
181 old = old.next;
182
183 int index = ( e.hash & 0x7FFFFFFF ) % newCapacity;
184 e.next = newTable[index];
185 newTable[index] = e;
186 }
187 }
188 }
189
190 /// Puts the specified element into the hashtable, using the specified
191 // key. The element may be retrieved by doing a get() with the same key.
192 // The key and the element cannot be null.
193 // @param key the specified key in the hashtable
194 // @param value the specified element
195 // @exception NullPointerException If the value of the element
196 // is equal to null.
197 // @see AcmeIntHashtable#get
198 // @return the old value of the key, or null if it did not have one.
199 public synchronized Object put( int key, Object value )
200 {
201 // Make sure the value is not null.
202 if ( value == null )
203 throw new NullPointerException();
204
205 // Makes sure the key is not already in the hashtable.
206 AcmeIntHashtableEntry tab[] = table;
207 int hash = key;
208 int index = ( hash & 0x7FFFFFFF ) % tab.length;
209 for ( AcmeIntHashtableEntry e = tab[index] ; e != null ; e = e.next )
210 {
211 if ( e.hash == hash && e.key == key )
212 {
213 Object old = e.value;
214 e.value = value;
215 return old;
216 }
217 }
218
219 if ( count >= threshold )
220 {
221 // Rehash the table if the threshold is exceeded.
222 rehash();
223 return put( key, value );
224 }
225
226 // Creates the new entry.
227 AcmeIntHashtableEntry e = new AcmeIntHashtableEntry();
228 e.hash = hash;
229 e.key = key;
230 e.value = value;
231 e.next = tab[index];
232 tab[index] = e;
233 ++count;
234 return null;
235 }
236
237 /// A put method that takes an Object, for compatibility with
238 // java.util.Dictionary. The Object must be an Integer.
239 public Object put( Object okey, Object value )
240 {
241 if ( ! ( okey instanceof Integer ) )
242 throw new InternalError( "key is not an Integer" );
243 Integer ikey = (Integer) okey;
244 int key = ikey.intValue();
245 return put( key, value );
246 }
247
248 /// Removes the element corresponding to the key. Does nothing if the
249 // key is not present.
250 // @param key the key that needs to be removed
251 // @return the value of key, or null if the key was not found.
252 public synchronized Object remove( int key )
253 {
254 AcmeIntHashtableEntry tab[] = table;
255 int hash = key;
256 int index = ( hash & 0x7FFFFFFF ) % tab.length;
257 for ( AcmeIntHashtableEntry e = tab[index], prev = null ; e != null ; prev = e, e = e.next )
258 {
259 if ( e.hash == hash && e.key == key )
260 {
261 if ( prev != null )
262 prev.next = e.next;
263 else
264 tab[index] = e.next;
265 --count;
266 return e.value;
267 }
268 }
269 return null;
270 }
271
272 /// A remove method that takes an Object, for compatibility with
273 // java.util.Dictionary. The Object must be an Integer.
274 public Object remove( Object okey )
275 {
276 if ( ! ( okey instanceof Integer ) )
277 throw new InternalError( "key is not an Integer" );
278 Integer ikey = (Integer) okey;
279 int key = ikey.intValue();
280 return remove( key );
281 }
282
283 /// Clears the hash table so that it has no more elements in it.
284 public synchronized void clear()
285 {
286 AcmeIntHashtableEntry tab[] = table;
287 for ( int index = tab.length; --index >= 0; )
288 tab[index] = null;
289 count = 0;
290 }
291
292 /// Creates a clone of the hashtable. A shallow copy is made,
293 // the keys and elements themselves are NOT cloned. This is a
294 // relatively expensive operation.
295 public synchronized Object clone()
296 {
297 try
298 {
299 AcmeIntHashtable t = (AcmeIntHashtable) super.clone();
300 t.table = new AcmeIntHashtableEntry[table.length];
301 for ( int i = table.length ; i-- > 0 ; )
302 t.table[i] = ( table[i] != null ) ?
303 (AcmeIntHashtableEntry) table[i].clone() : null;
304 return t;
305 }
306 catch ( CloneNotSupportedException e)
307 {
308 // This shouldn't happen, since we are Cloneable.
309 throw new InternalError();
310 }
311 }
312
313 /// Converts to a rather lengthy String.
314 public synchronized String toString()
315 {
316 int max = size() - 1;
317 StringBuffer buf = new StringBuffer();
318 Enumeration k = keys();
319 Enumeration e = elements();
320 buf.append( "{" );
321
322 for ( int i = 0; i <= max; ++i )
323 {
324 String s1 = k.nextElement().toString();
325 String s2 = e.nextElement().toString();
326 buf.append( s1 + "=" + s2 );
327 if ( i < max )
328 buf.append( ", " );
329 }
330 buf.append( "}" );
331 return buf.toString();
332 }
333 }
334
335
336 class AcmeIntHashtableEntry
337 {
338 int hash;
339 int key;
340 Object value;
341 AcmeIntHashtableEntry next;
342
343 protected Object clone()
344 {
345 AcmeIntHashtableEntry entry = new AcmeIntHashtableEntry();
346 entry.hash = hash;
347 entry.key = key;
348 entry.value = value;
349 entry.next = ( next != null ) ? (AcmeIntHashtableEntry) next.clone() : null;
350 return entry;
351 }
352 }
353
354
355 class AcmeIntHashtableEnumerator implements Enumeration
356 {
357 boolean keys;
358 int index;
359 AcmeIntHashtableEntry table[];
360 AcmeIntHashtableEntry entry;
361
362 AcmeIntHashtableEnumerator( AcmeIntHashtableEntry table[], boolean keys )
363 {
364 this.table = table;
365 this.keys = keys;
366 this.index = table.length;
367 }
368
369 public boolean hasMoreElements()
370 {
371 if ( entry != null )
372 return true;
373 while ( index-- > 0 )
374 if ( ( entry = table[index] ) != null )
375 return true;
376 return false;
377 }
378
379 public Object nextElement()
380 {
381 if ( entry == null )
382 while ( ( index-- > 0 ) && ( ( entry = table[index] ) == null ) )
383 ;
384 if ( entry != null )
385 {
386 AcmeIntHashtableEntry e = entry;
387 entry = e.next;
388 return keys ? new Integer( e.key ) : e.value;
389 }
390 throw new NoSuchElementException( "AcmeIntHashtableEnumerator" );
391 }
392 }