1 |
/* Hashtable.java -- a class providing a basic hashtable data structure, |
2 |
mapping Object --> Object |
3 |
Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc. |
4 |
|
5 |
This file is part of GNU Classpath. |
6 |
|
7 |
GNU Classpath is free software; you can redistribute it and/or modify |
8 |
it under the terms of the GNU General Public License as published by |
9 |
the Free Software Foundation; either version 2, or (at your option) |
10 |
any later version. |
11 |
|
12 |
GNU Classpath is distributed in the hope that it will be useful, but |
13 |
WITHOUT ANY WARRANTY; without even the implied warranty of |
14 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
15 |
General Public License for more details. |
16 |
|
17 |
You should have received a copy of the GNU General Public License |
18 |
along with GNU Classpath; see the file COPYING. If not, write to the |
19 |
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
20 |
02111-1307 USA. |
21 |
|
22 |
Linking this library statically or dynamically with other modules is |
23 |
making a combined work based on this library. Thus, the terms and |
24 |
conditions of the GNU General Public License cover the whole |
25 |
combination. |
26 |
|
27 |
As a special exception, the copyright holders of this library give you |
28 |
permission to link this library with independent modules to produce an |
29 |
executable, regardless of the license terms of these independent |
30 |
modules, and to copy and distribute the resulting executable under |
31 |
terms of your choice, provided that you also meet, for each linked |
32 |
independent module, the terms and conditions of the license of that |
33 |
module. An independent module is a module which is not derived from |
34 |
or based on this library. If you modify this library, you may extend |
35 |
this exception to your version of the library, but you are not |
36 |
obligated to do so. If you do not wish to do so, delete this |
37 |
exception statement from your version. */ |
38 |
|
39 |
package java.util; |
40 |
|
41 |
import java.io.IOException; |
42 |
import java.io.Serializable; |
43 |
import java.io.ObjectInputStream; |
44 |
import java.io.ObjectOutputStream; |
45 |
|
46 |
// NOTE: This implementation is very similar to that of HashMap. If you fix |
47 |
// a bug in here, chances are you should make a similar change to the HashMap |
48 |
// code. |
49 |
|
50 |
/** |
51 |
* A class which implements a hashtable data structure. |
52 |
* <p> |
53 |
* |
54 |
* This implementation of Hashtable uses a hash-bucket approach. That is: |
55 |
* linear probing and rehashing is avoided; instead, each hashed value maps |
56 |
* to a simple linked-list which, in the best case, only has one node. |
57 |
* Assuming a large enough table, low enough load factor, and / or well |
58 |
* implemented hashCode() methods, Hashtable should provide O(1) |
59 |
* insertion, deletion, and searching of keys. Hashtable is O(n) in |
60 |
* the worst case for all of these (if all keys hash to the same bucket). |
61 |
* <p> |
62 |
* |
63 |
* This is a JDK-1.2 compliant implementation of Hashtable. As such, it |
64 |
* belongs, partially, to the Collections framework (in that it implements |
65 |
* Map). For backwards compatibility, it inherits from the obsolete and |
66 |
* utterly useless Dictionary class. |
67 |
* <p> |
68 |
* |
69 |
* Being a hybrid of old and new, Hashtable has methods which provide redundant |
70 |
* capability, but with subtle and even crucial differences. |
71 |
* For example, one can iterate over various aspects of a Hashtable with |
72 |
* either an Iterator (which is the JDK-1.2 way of doing things) or with an |
73 |
* Enumeration. The latter can end up in an undefined state if the Hashtable |
74 |
* changes while the Enumeration is open. |
75 |
* <p> |
76 |
* |
77 |
* Unlike HashMap, Hashtable does not accept `null' as a key value. Also, |
78 |
* all accesses are synchronized: in a single thread environment, this is |
79 |
* expensive, but in a multi-thread environment, this saves you the effort |
80 |
* of extra synchronization. However, the old-style enumerators are not |
81 |
* synchronized, because they can lead to unspecified behavior even if |
82 |
* they were synchronized. You have been warned. |
83 |
* <p> |
84 |
* |
85 |
* The iterators are <i>fail-fast</i>, meaning that any structural |
86 |
* modification, except for <code>remove()</code> called on the iterator |
87 |
* itself, cause the iterator to throw a |
88 |
* <code>ConcurrentModificationException</code> rather than exhibit |
89 |
* non-deterministic behavior. |
90 |
* |
91 |
* @author Jon Zeppieri |
92 |
* @author Warren Levy |
93 |
* @author Bryce McKinlay |
94 |
* @author Eric Blake <ebb9@email.byu.edu> |
95 |
* @see HashMap |
96 |
* @see TreeMap |
97 |
* @see IdentityHashMap |
98 |
* @see LinkedHashMap |
99 |
* @since 1.0 |
100 |
* @status updated to 1.4 |
101 |
*/ |
102 |
public class Hashtable extends Dictionary |
103 |
implements Map, Cloneable, Serializable |
104 |
{ |
105 |
// WARNING: Hashtable is a CORE class in the bootstrap cycle. See the |
106 |
// comments in vm/reference/java/lang/Runtime for implications of this fact. |
107 |
|
108 |
/** Default number of buckets. This is the value the JDK 1.3 uses. Some |
109 |
* early documentation specified this value as 101. That is incorrect. |
110 |
*/ |
111 |
private static final int DEFAULT_CAPACITY = 11; |
112 |
|
113 |
/** An "enum" of iterator types. */ |
114 |
// Package visible for use by nested classes. |
115 |
static final int KEYS = 0, |
116 |
VALUES = 1, |
117 |
ENTRIES = 2; |
118 |
|
119 |
/** |
120 |
* The default load factor; this is explicitly specified by the spec. |
121 |
*/ |
122 |
private static final float DEFAULT_LOAD_FACTOR = 0.75f; |
123 |
|
124 |
/** |
125 |
* Compatible with JDK 1.0+. |
126 |
*/ |
127 |
private static final long serialVersionUID = 1421746759512286392L; |
128 |
|
129 |
/** |
130 |
* The rounded product of the capacity and the load factor; when the number |
131 |
* of elements exceeds the threshold, the Hashtable calls |
132 |
* <code>rehash()</code>. |
133 |
* @serial |
134 |
*/ |
135 |
private int threshold; |
136 |
|
137 |
/** |
138 |
* Load factor of this Hashtable: used in computing the threshold. |
139 |
* @serial |
140 |
*/ |
141 |
private final float loadFactor; |
142 |
|
143 |
/** |
144 |
* Array containing the actual key-value mappings. |
145 |
*/ |
146 |
// Package visible for use by nested classes. |
147 |
transient HashEntry[] buckets; |
148 |
|
149 |
/** |
150 |
* Counts the number of modifications this Hashtable has undergone, used |
151 |
* by Iterators to know when to throw ConcurrentModificationExceptions. |
152 |
*/ |
153 |
// Package visible for use by nested classes. |
154 |
transient int modCount; |
155 |
|
156 |
/** |
157 |
* The size of this Hashtable: denotes the number of key-value pairs. |
158 |
*/ |
159 |
// Package visible for use by nested classes. |
160 |
transient int size; |
161 |
|
162 |
/** |
163 |
* The cache for {@link #keySet()}. |
164 |
*/ |
165 |
private transient Set keys; |
166 |
|
167 |
/** |
168 |
* The cache for {@link #values()}. |
169 |
*/ |
170 |
private transient Collection values; |
171 |
|
172 |
/** |
173 |
* The cache for {@link #entrySet()}. |
174 |
*/ |
175 |
private transient Set entries; |
176 |
|
177 |
/** |
178 |
* Class to represent an entry in the hash table. Holds a single key-value |
179 |
* pair. A Hashtable Entry is identical to a HashMap Entry, except that |
180 |
* `null' is not allowed for keys and values. |
181 |
*/ |
182 |
private static final class HashEntry extends AbstractMap.BasicMapEntry |
183 |
{ |
184 |
/** The next entry in the linked list. */ |
185 |
HashEntry next; |
186 |
|
187 |
/** |
188 |
* Simple constructor. |
189 |
* @param key the key, already guaranteed non-null |
190 |
* @param value the value, already guaranteed non-null |
191 |
*/ |
192 |
HashEntry(Object key, Object value) |
193 |
{ |
194 |
super(key, value); |
195 |
} |
196 |
|
197 |
/** |
198 |
* Resets the value. |
199 |
* @param newValue the new value |
200 |
* @return the prior value |
201 |
* @throws NullPointerException if <code>newVal</code> is null |
202 |
*/ |
203 |
public Object setValue(Object newVal) |
204 |
{ |
205 |
if (newVal == null) |
206 |
throw new NullPointerException(); |
207 |
return super.setValue(newVal); |
208 |
} |
209 |
} |
210 |
|
211 |
/** |
212 |
* Construct a new Hashtable with the default capacity (11) and the default |
213 |
* load factor (0.75). |
214 |
*/ |
215 |
public Hashtable() |
216 |
{ |
217 |
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); |
218 |
} |
219 |
|
220 |
/** |
221 |
* Construct a new Hashtable from the given Map, with initial capacity |
222 |
* the greater of the size of <code>m</code> or the default of 11. |
223 |
* <p> |
224 |
* |
225 |
* Every element in Map m will be put into this new Hashtable. |
226 |
* |
227 |
* @param m a Map whose key / value pairs will be put into |
228 |
* the new Hashtable. <b>NOTE: key / value pairs |
229 |
* are not cloned in this constructor.</b> |
230 |
* @throws NullPointerException if m is null, or if m contains a mapping |
231 |
* to or from `null'. |
232 |
* @since 1.2 |
233 |
*/ |
234 |
public Hashtable(Map m) |
235 |
{ |
236 |
this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); |
237 |
putAllInternal(m); |
238 |
} |
239 |
|
240 |
/** |
241 |
* Construct a new Hashtable with a specific inital capacity and |
242 |
* default load factor of 0.75. |
243 |
* |
244 |
* @param initialCapacity the initial capacity of this Hashtable (>= 0) |
245 |
* @throws IllegalArgumentException if (initialCapacity < 0) |
246 |
*/ |
247 |
public Hashtable(int initialCapacity) |
248 |
{ |
249 |
this(initialCapacity, DEFAULT_LOAD_FACTOR); |
250 |
} |
251 |
|
252 |
/** |
253 |
* Construct a new Hashtable with a specific initial capacity and |
254 |
* load factor. |
255 |
* |
256 |
* @param initialCapacity the initial capacity (>= 0) |
257 |
* @param loadFactor the load factor (> 0, not NaN) |
258 |
* @throws IllegalArgumentException if (initialCapacity < 0) || |
259 |
* ! (loadFactor > 0.0) |
260 |
*/ |
261 |
public Hashtable(int initialCapacity, float loadFactor) |
262 |
{ |
263 |
if (initialCapacity < 0) |
264 |
throw new IllegalArgumentException("Illegal Capacity: " |
265 |
+ initialCapacity); |
266 |
if (! (loadFactor > 0)) // check for NaN too |
267 |
throw new IllegalArgumentException("Illegal Load: " + loadFactor); |
268 |
|
269 |
if (initialCapacity == 0) |
270 |
initialCapacity = 1; |
271 |
buckets = new HashEntry[initialCapacity]; |
272 |
this.loadFactor = loadFactor; |
273 |
threshold = (int) (initialCapacity * loadFactor); |
274 |
} |
275 |
|
276 |
/** |
277 |
* Returns the number of key-value mappings currently in this hashtable. |
278 |
* @return the size |
279 |
*/ |
280 |
public synchronized int size() |
281 |
{ |
282 |
return size; |
283 |
} |
284 |
|
285 |
/** |
286 |
* Returns true if there are no key-value mappings currently in this table. |
287 |
* @return <code>size() == 0</code> |
288 |
*/ |
289 |
public synchronized boolean isEmpty() |
290 |
{ |
291 |
return size == 0; |
292 |
} |
293 |
|
294 |
/** |
295 |
* Return an enumeration of the keys of this table. There's no point |
296 |
* in synchronizing this, as you have already been warned that the |
297 |
* enumeration is not specified to be thread-safe. |
298 |
* |
299 |
* @return the keys |
300 |
* @see #elements() |
301 |
* @see #keySet() |
302 |
*/ |
303 |
public Enumeration keys() |
304 |
{ |
305 |
return new Enumerator(KEYS); |
306 |
} |
307 |
|
308 |
/** |
309 |
* Return an enumeration of the values of this table. There's no point |
310 |
* in synchronizing this, as you have already been warned that the |
311 |
* enumeration is not specified to be thread-safe. |
312 |
* |
313 |
* @return the values |
314 |
* @see #keys() |
315 |
* @see #values() |
316 |
*/ |
317 |
public Enumeration elements() |
318 |
{ |
319 |
return new Enumerator(VALUES); |
320 |
} |
321 |
|
322 |
/** |
323 |
* Returns true if this Hashtable contains a value <code>o</code>, |
324 |
* such that <code>o.equals(value)</code>. This is the same as |
325 |
* <code>containsValue()</code>, and is O(n). |
326 |
* <p> |
327 |
* |
328 |
* @param value the value to search for in this Hashtable |
329 |
* @return true if at least one key maps to the value |
330 |
* @throws NullPointerException if <code>value</code> is null |
331 |
* @see #containsValue(Object) |
332 |
* @see #containsKey(Object) |
333 |
*/ |
334 |
public synchronized boolean contains(Object value) |
335 |
{ |
336 |
return containsValue(value); |
337 |
} |
338 |
|
339 |
/** |
340 |
* Returns true if this Hashtable contains a value <code>o</code>, such that |
341 |
* <code>o.equals(value)</code>. This is the new API for the old |
342 |
* <code>contains()</code>. |
343 |
* |
344 |
* @param value the value to search for in this Hashtable |
345 |
* @return true if at least one key maps to the value |
346 |
* @see #contains(Object) |
347 |
* @see #containsKey(Object) |
348 |
* @throws NullPointerException if <code>value</code> is null |
349 |
* @since 1.2 |
350 |
*/ |
351 |
public boolean containsValue(Object value) |
352 |
{ |
353 |
for (int i = buckets.length - 1; i >= 0; i--) |
354 |
{ |
355 |
HashEntry e = buckets[i]; |
356 |
while (e != null) |
357 |
{ |
358 |
if (value.equals(e.value)) |
359 |
return true; |
360 |
e = e.next; |
361 |
} |
362 |
} |
363 |
|
364 |
// Must throw on null argument even if the table is empty |
365 |
if (value == null) |
366 |
throw new NullPointerException(); |
367 |
|
368 |
return false; |
369 |
} |
370 |
|
371 |
/** |
372 |
* Returns true if the supplied object <code>equals()</code> a key |
373 |
* in this Hashtable. |
374 |
* |
375 |
* @param key the key to search for in this Hashtable |
376 |
* @return true if the key is in the table |
377 |
* @throws NullPointerException if key is null |
378 |
* @see #containsValue(Object) |
379 |
*/ |
380 |
public synchronized boolean containsKey(Object key) |
381 |
{ |
382 |
int idx = hash(key); |
383 |
HashEntry e = buckets[idx]; |
384 |
while (e != null) |
385 |
{ |
386 |
if (key.equals(e.key)) |
387 |
return true; |
388 |
e = e.next; |
389 |
} |
390 |
return false; |
391 |
} |
392 |
|
393 |
/** |
394 |
* Return the value in this Hashtable associated with the supplied key, |
395 |
* or <code>null</code> if the key maps to nothing. |
396 |
* |
397 |
* @param key the key for which to fetch an associated value |
398 |
* @return what the key maps to, if present |
399 |
* @throws NullPointerException if key is null |
400 |
* @see #put(Object, Object) |
401 |
* @see #containsKey(Object) |
402 |
*/ |
403 |
public synchronized Object get(Object key) |
404 |
{ |
405 |
int idx = hash(key); |
406 |
HashEntry e = buckets[idx]; |
407 |
while (e != null) |
408 |
{ |
409 |
if (key.equals(e.key)) |
410 |
return e.value; |
411 |
e = e.next; |
412 |
} |
413 |
return null; |
414 |
} |
415 |
|
416 |
/** |
417 |
* Puts the supplied value into the Map, mapped by the supplied key. |
418 |
* Neither parameter may be null. The value may be retrieved by any |
419 |
* object which <code>equals()</code> this key. |
420 |
* |
421 |
* @param key the key used to locate the value |
422 |
* @param value the value to be stored in the table |
423 |
* @return the prior mapping of the key, or null if there was none |
424 |
* @throws NullPointerException if key or value is null |
425 |
* @see #get(Object) |
426 |
* @see Object#equals(Object) |
427 |
*/ |
428 |
public synchronized Object put(Object key, Object value) |
429 |
{ |
430 |
int idx = hash(key); |
431 |
HashEntry e = buckets[idx]; |
432 |
|
433 |
// Check if value is null since it is not permitted. |
434 |
if (value == null) |
435 |
throw new NullPointerException(); |
436 |
|
437 |
while (e != null) |
438 |
{ |
439 |
if (key.equals(e.key)) |
440 |
{ |
441 |
// Bypass e.setValue, since we already know value is non-null. |
442 |
Object r = e.value; |
443 |
e.value = value; |
444 |
return r; |
445 |
} |
446 |
else |
447 |
{ |
448 |
e = e.next; |
449 |
} |
450 |
} |
451 |
|
452 |
// At this point, we know we need to add a new entry. |
453 |
modCount++; |
454 |
if (++size > threshold) |
455 |
{ |
456 |
rehash(); |
457 |
// Need a new hash value to suit the bigger table. |
458 |
idx = hash(key); |
459 |
} |
460 |
|
461 |
e = new HashEntry(key, value); |
462 |
|
463 |
e.next = buckets[idx]; |
464 |
buckets[idx] = e; |
465 |
|
466 |
return null; |
467 |
} |
468 |
|
469 |
/** |
470 |
* Removes from the table and returns the value which is mapped by the |
471 |
* supplied key. If the key maps to nothing, then the table remains |
472 |
* unchanged, and <code>null</code> is returned. |
473 |
* |
474 |
* @param key the key used to locate the value to remove |
475 |
* @return whatever the key mapped to, if present |
476 |
*/ |
477 |
public synchronized Object remove(Object key) |
478 |
{ |
479 |
int idx = hash(key); |
480 |
HashEntry e = buckets[idx]; |
481 |
HashEntry last = null; |
482 |
|
483 |
while (e != null) |
484 |
{ |
485 |
if (key.equals(e.key)) |
486 |
{ |
487 |
modCount++; |
488 |
if (last == null) |
489 |
buckets[idx] = e.next; |
490 |
else |
491 |
last.next = e.next; |
492 |
size--; |
493 |
return e.value; |
494 |
} |
495 |
last = e; |
496 |
e = e.next; |
497 |
} |
498 |
return null; |
499 |
} |
500 |
|
501 |
/** |
502 |
* Copies all elements of the given map into this hashtable. However, no |
503 |
* mapping can contain null as key or value. If this table already has |
504 |
* a mapping for a key, the new mapping replaces the current one. |
505 |
* |
506 |
* @param m the map to be hashed into this |
507 |
* @throws NullPointerException if m is null, or contains null keys or values |
508 |
*/ |
509 |
public synchronized void putAll(Map m) |
510 |
{ |
511 |
Iterator itr = m.entrySet().iterator(); |
512 |
|
513 |
for (int msize = m.size(); msize > 0; msize--) |
514 |
{ |
515 |
Map.Entry e = (Map.Entry) itr.next(); |
516 |
// Optimize in case the Entry is one of our own. |
517 |
if (e instanceof AbstractMap.BasicMapEntry) |
518 |
{ |
519 |
AbstractMap.BasicMapEntry entry = (AbstractMap.BasicMapEntry) e; |
520 |
put(entry.key, entry.value); |
521 |
} |
522 |
else |
523 |
{ |
524 |
put(e.getKey(), e.getValue()); |
525 |
} |
526 |
} |
527 |
} |
528 |
|
529 |
/** |
530 |
* Clears the hashtable so it has no keys. This is O(1). |
531 |
*/ |
532 |
public synchronized void clear() |
533 |
{ |
534 |
if (size > 0) |
535 |
{ |
536 |
modCount++; |
537 |
Arrays.fill(buckets, null); |
538 |
size = 0; |
539 |
} |
540 |
} |
541 |
|
542 |
/** |
543 |
* Returns a shallow clone of this Hashtable. The Map itself is cloned, |
544 |
* but its contents are not. This is O(n). |
545 |
* |
546 |
* @return the clone |
547 |
*/ |
548 |
public synchronized Object clone() |
549 |
{ |
550 |
Hashtable copy = null; |
551 |
try |
552 |
{ |
553 |
copy = (Hashtable) super.clone(); |
554 |
} |
555 |
catch (CloneNotSupportedException x) |
556 |
{ |
557 |
// This is impossible. |
558 |
} |
559 |
copy.buckets = new HashEntry[buckets.length]; |
560 |
copy.putAllInternal(this); |
561 |
// Clear the caches. |
562 |
copy.keys = null; |
563 |
copy.values = null; |
564 |
copy.entries = null; |
565 |
return copy; |
566 |
} |
567 |
|
568 |
/** |
569 |
* Converts this Hashtable to a String, surrounded by braces, and with |
570 |
* key/value pairs listed with an equals sign between, separated by a |
571 |
* comma and space. For example, <code>"{a=1, b=2}"</code>.<p> |
572 |
* |
573 |
* NOTE: if the <code>toString()</code> method of any key or value |
574 |
* throws an exception, this will fail for the same reason. |
575 |
* |
576 |
* @return the string representation |
577 |
*/ |
578 |
public synchronized String toString() |
579 |
{ |
580 |
// Since we are already synchronized, and entrySet().iterator() |
581 |
// would repeatedly re-lock/release the monitor, we directly use the |
582 |
// unsynchronized HashIterator instead. |
583 |
Iterator entries = new HashIterator(ENTRIES); |
584 |
StringBuffer r = new StringBuffer("{"); |
585 |
for (int pos = size; pos > 0; pos--) |
586 |
{ |
587 |
r.append(entries.next()); |
588 |
if (pos > 1) |
589 |
r.append(", "); |
590 |
} |
591 |
r.append("}"); |
592 |
return r.toString(); |
593 |
} |
594 |
|
595 |
/** |
596 |
* Returns a "set view" of this Hashtable's keys. The set is backed by |
597 |
* the hashtable, so changes in one show up in the other. The set supports |
598 |
* element removal, but not element addition. The set is properly |
599 |
* synchronized on the original hashtable. Sun has not documented the |
600 |
* proper interaction of null with this set, but has inconsistent behavior |
601 |
* in the JDK. Therefore, in this implementation, contains, remove, |
602 |
* containsAll, retainAll, removeAll, and equals just ignore a null key |
603 |
* rather than throwing a {@link NullPointerException}. |
604 |
* |
605 |
* @return a set view of the keys |
606 |
* @see #values() |
607 |
* @see #entrySet() |
608 |
* @since 1.2 |
609 |
*/ |
610 |
public Set keySet() |
611 |
{ |
612 |
if (keys == null) |
613 |
{ |
614 |
// Create a synchronized AbstractSet with custom implementations of |
615 |
// those methods that can be overridden easily and efficiently. |
616 |
Set r = new AbstractSet() |
617 |
{ |
618 |
public int size() |
619 |
{ |
620 |
return size; |
621 |
} |
622 |
|
623 |
public Iterator iterator() |
624 |
{ |
625 |
return new HashIterator(KEYS); |
626 |
} |
627 |
|
628 |
public void clear() |
629 |
{ |
630 |
Hashtable.this.clear(); |
631 |
} |
632 |
|
633 |
public boolean contains(Object o) |
634 |
{ |
635 |
if (o == null) |
636 |
return false; |
637 |
return containsKey(o); |
638 |
} |
639 |
|
640 |
public boolean remove(Object o) |
641 |
{ |
642 |
return Hashtable.this.remove(o) != null; |
643 |
} |
644 |
}; |
645 |
// We must specify the correct object to synchronize upon, hence the |
646 |
// use of a non-public API |
647 |
keys = new Collections.SynchronizedSet(this, r); |
648 |
} |
649 |
return keys; |
650 |
} |
651 |
|
652 |
/** |
653 |
* Returns a "collection view" (or "bag view") of this Hashtable's values. |
654 |
* The collection is backed by the hashtable, so changes in one show up |
655 |
* in the other. The collection supports element removal, but not element |
656 |
* addition. The collection is properly synchronized on the original |
657 |
* hashtable. Sun has not documented the proper interaction of null with |
658 |
* this set, but has inconsistent behavior in the JDK. Therefore, in this |
659 |
* implementation, contains, remove, containsAll, retainAll, removeAll, and |
660 |
* equals just ignore a null value rather than throwing a |
661 |
* {@link NullPointerException}. |
662 |
* |
663 |
* @return a bag view of the values |
664 |
* @see #keySet() |
665 |
* @see #entrySet() |
666 |
* @since 1.2 |
667 |
*/ |
668 |
public Collection values() |
669 |
{ |
670 |
if (values == null) |
671 |
{ |
672 |
// We don't bother overriding many of the optional methods, as doing so |
673 |
// wouldn't provide any significant performance advantage. |
674 |
Collection r = new AbstractCollection() |
675 |
{ |
676 |
public int size() |
677 |
{ |
678 |
return size; |
679 |
} |
680 |
|
681 |
public Iterator iterator() |
682 |
{ |
683 |
return new HashIterator(VALUES); |
684 |
} |
685 |
|
686 |
public void clear() |
687 |
{ |
688 |
Hashtable.this.clear(); |
689 |
} |
690 |
}; |
691 |
// We must specify the correct object to synchronize upon, hence the |
692 |
// use of a non-public API |
693 |
values = new Collections.SynchronizedCollection(this, r); |
694 |
} |
695 |
return values; |
696 |
} |
697 |
|
698 |
/** |
699 |
* Returns a "set view" of this Hashtable's entries. The set is backed by |
700 |
* the hashtable, so changes in one show up in the other. The set supports |
701 |
* element removal, but not element addition. The set is properly |
702 |
* synchronized on the original hashtable. Sun has not documented the |
703 |
* proper interaction of null with this set, but has inconsistent behavior |
704 |
* in the JDK. Therefore, in this implementation, contains, remove, |
705 |
* containsAll, retainAll, removeAll, and equals just ignore a null entry, |
706 |
* or an entry with a null key or value, rather than throwing a |
707 |
* {@link NullPointerException}. However, calling entry.setValue(null) |
708 |
* will fail. |
709 |
* <p> |
710 |
* |
711 |
* Note that the iterators for all three views, from keySet(), entrySet(), |
712 |
* and values(), traverse the hashtable in the same sequence. |
713 |
* |
714 |
* @return a set view of the entries |
715 |
* @see #keySet() |
716 |
* @see #values() |
717 |
* @see Map.Entry |
718 |
* @since 1.2 |
719 |
*/ |
720 |
public Set entrySet() |
721 |
{ |
722 |
if (entries == null) |
723 |
{ |
724 |
// Create an AbstractSet with custom implementations of those methods |
725 |
// that can be overridden easily and efficiently. |
726 |
Set r = new AbstractSet() |
727 |
{ |
728 |
public int size() |
729 |
{ |
730 |
return size; |
731 |
} |
732 |
|
733 |
public Iterator iterator() |
734 |
{ |
735 |
return new HashIterator(ENTRIES); |
736 |
} |
737 |
|
738 |
public void clear() |
739 |
{ |
740 |
Hashtable.this.clear(); |
741 |
} |
742 |
|
743 |
public boolean contains(Object o) |
744 |
{ |
745 |
return getEntry(o) != null; |
746 |
} |
747 |
|
748 |
public boolean remove(Object o) |
749 |
{ |
750 |
HashEntry e = getEntry(o); |
751 |
if (e != null) |
752 |
{ |
753 |
Hashtable.this.remove(e.key); |
754 |
return true; |
755 |
} |
756 |
return false; |
757 |
} |
758 |
}; |
759 |
// We must specify the correct object to synchronize upon, hence the |
760 |
// use of a non-public API |
761 |
entries = new Collections.SynchronizedSet(this, r); |
762 |
} |
763 |
return entries; |
764 |
} |
765 |
|
766 |
/** |
767 |
* Returns true if this Hashtable equals the supplied Object <code>o</code>. |
768 |
* As specified by Map, this is: |
769 |
* <code> |
770 |
* (o instanceof Map) && entrySet().equals(((Map) o).entrySet()); |
771 |
* </code> |
772 |
* |
773 |
* @param o the object to compare to |
774 |
* @return true if o is an equal map |
775 |
* @since 1.2 |
776 |
*/ |
777 |
public boolean equals(Object o) |
778 |
{ |
779 |
// no need to synchronize, entrySet().equals() does that |
780 |
if (o == this) |
781 |
return true; |
782 |
if (!(o instanceof Map)) |
783 |
return false; |
784 |
|
785 |
return entrySet().equals(((Map) o).entrySet()); |
786 |
} |
787 |
|
788 |
/** |
789 |
* Returns the hashCode for this Hashtable. As specified by Map, this is |
790 |
* the sum of the hashCodes of all of its Map.Entry objects |
791 |
* |
792 |
* @return the sum of the hashcodes of the entries |
793 |
* @since 1.2 |
794 |
*/ |
795 |
public synchronized int hashCode() |
796 |
{ |
797 |
// Since we are already synchronized, and entrySet().iterator() |
798 |
// would repeatedly re-lock/release the monitor, we directly use the |
799 |
// unsynchronized HashIterator instead. |
800 |
Iterator itr = new HashIterator(ENTRIES); |
801 |
int hashcode = 0; |
802 |
for (int pos = size; pos > 0; pos--) |
803 |
hashcode += itr.next().hashCode(); |
804 |
|
805 |
return hashcode; |
806 |
} |
807 |
|
808 |
/** |
809 |
* Helper method that returns an index in the buckets array for `key' |
810 |
* based on its hashCode(). |
811 |
* |
812 |
* @param key the key |
813 |
* @return the bucket number |
814 |
* @throws NullPointerException if key is null |
815 |
*/ |
816 |
private int hash(Object key) |
817 |
{ |
818 |
// Note: Inline Math.abs here, for less method overhead, and to avoid |
819 |
// a bootstrap dependency, since Math relies on native methods. |
820 |
int hash = key.hashCode() % buckets.length; |
821 |
return hash < 0 ? -hash : hash; |
822 |
} |
823 |
|
824 |
/** |
825 |
* Helper method for entrySet(), which matches both key and value |
826 |
* simultaneously. Ignores null, as mentioned in entrySet(). |
827 |
* |
828 |
* @param o the entry to match |
829 |
* @return the matching entry, if found, or null |
830 |
* @see #entrySet() |
831 |
*/ |
832 |
// Package visible, for use in nested classes. |
833 |
HashEntry getEntry(Object o) |
834 |
{ |
835 |
if (! (o instanceof Map.Entry)) |
836 |
return null; |
837 |
Object key = ((Map.Entry) o).getKey(); |
838 |
if (key == null) |
839 |
return null; |
840 |
|
841 |
int idx = hash(key); |
842 |
HashEntry e = buckets[idx]; |
843 |
while (e != null) |
844 |
{ |
845 |
if (o.equals(e)) |
846 |
return e; |
847 |
e = e.next; |
848 |
} |
849 |
return null; |
850 |
} |
851 |
|
852 |
/** |
853 |
* A simplified, more efficient internal implementation of putAll(). The |
854 |
* Map constructor and clone() should not call putAll or put, in order to |
855 |
* be compatible with the JDK implementation with respect to subclasses. |
856 |
* |
857 |
* @param m the map to initialize this from |
858 |
*/ |
859 |
void putAllInternal(Map m) |
860 |
{ |
861 |
Iterator itr = m.entrySet().iterator(); |
862 |
int msize = m.size(); |
863 |
this.size = msize; |
864 |
|
865 |
for (; msize > 0; msize--) |
866 |
{ |
867 |
Map.Entry e = (Map.Entry) itr.next(); |
868 |
Object key = e.getKey(); |
869 |
int idx = hash(key); |
870 |
HashEntry he = new HashEntry(key, e.getValue()); |
871 |
he.next = buckets[idx]; |
872 |
buckets[idx] = he; |
873 |
} |
874 |
} |
875 |
|
876 |
/** |
877 |
* Increases the size of the Hashtable and rehashes all keys to new array |
878 |
* indices; this is called when the addition of a new value would cause |
879 |
* size() > threshold. Note that the existing Entry objects are reused in |
880 |
* the new hash table. |
881 |
* <p> |
882 |
* |
883 |
* This is not specified, but the new size is twice the current size plus |
884 |
* one; this number is not always prime, unfortunately. This implementation |
885 |
* is not synchronized, as it is only invoked from synchronized methods. |
886 |
*/ |
887 |
protected void rehash() |
888 |
{ |
889 |
HashEntry[] oldBuckets = buckets; |
890 |
|
891 |
int newcapacity = (buckets.length * 2) + 1; |
892 |
threshold = (int) (newcapacity * loadFactor); |
893 |
buckets = new HashEntry[newcapacity]; |
894 |
|
895 |
for (int i = oldBuckets.length - 1; i >= 0; i--) |
896 |
{ |
897 |
HashEntry e = oldBuckets[i]; |
898 |
while (e != null) |
899 |
{ |
900 |
int idx = hash(e.key); |
901 |
HashEntry dest = buckets[idx]; |
902 |
|
903 |
if (dest != null) |
904 |
{ |
905 |
while (dest.next != null) |
906 |
dest = dest.next; |
907 |
dest.next = e; |
908 |
} |
909 |
else |
910 |
{ |
911 |
buckets[idx] = e; |
912 |
} |
913 |
|
914 |
HashEntry next = e.next; |
915 |
e.next = null; |
916 |
e = next; |
917 |
} |
918 |
} |
919 |
} |
920 |
|
921 |
/** |
922 |
* Serializes this object to the given stream. |
923 |
* |
924 |
* @param s the stream to write to |
925 |
* @throws IOException if the underlying stream fails |
926 |
* @serialData the <i>capacity</i> (int) that is the length of the |
927 |
* bucket array, the <i>size</i> (int) of the hash map |
928 |
* are emitted first. They are followed by size entries, |
929 |
* each consisting of a key (Object) and a value (Object). |
930 |
*/ |
931 |
private synchronized void writeObject(ObjectOutputStream s) |
932 |
throws IOException |
933 |
{ |
934 |
// Write the threshold and loadFactor fields. |
935 |
s.defaultWriteObject(); |
936 |
|
937 |
s.writeInt(buckets.length); |
938 |
s.writeInt(size); |
939 |
// Since we are already synchronized, and entrySet().iterator() |
940 |
// would repeatedly re-lock/release the monitor, we directly use the |
941 |
// unsynchronized HashIterator instead. |
942 |
Iterator it = new HashIterator(ENTRIES); |
943 |
while (it.hasNext()) |
944 |
{ |
945 |
HashEntry entry = (HashEntry) it.next(); |
946 |
s.writeObject(entry.key); |
947 |
s.writeObject(entry.value); |
948 |
} |
949 |
} |
950 |
|
951 |
/** |
952 |
* Deserializes this object from the given stream. |
953 |
* |
954 |
* @param s the stream to read from |
955 |
* @throws ClassNotFoundException if the underlying stream fails |
956 |
* @throws IOException if the underlying stream fails |
957 |
* @serialData the <i>capacity</i> (int) that is the length of the |
958 |
* bucket array, the <i>size</i> (int) of the hash map |
959 |
* are emitted first. They are followed by size entries, |
960 |
* each consisting of a key (Object) and a value (Object). |
961 |
*/ |
962 |
private void readObject(ObjectInputStream s) |
963 |
throws IOException, ClassNotFoundException |
964 |
{ |
965 |
// Read the threshold and loadFactor fields. |
966 |
s.defaultReadObject(); |
967 |
|
968 |
// Read and use capacity. |
969 |
buckets = new HashEntry[s.readInt()]; |
970 |
int len = s.readInt(); |
971 |
|
972 |
// Read and use key/value pairs. |
973 |
// TODO: should we be defensive programmers, and check for illegal nulls? |
974 |
while (--len >= 0) |
975 |
put(s.readObject(), s.readObject()); |
976 |
} |
977 |
|
978 |
/** |
979 |
* A class which implements the Iterator interface and is used for |
980 |
* iterating over Hashtables. |
981 |
* This implementation is parameterized to give a sequential view of |
982 |
* keys, values, or entries; it also allows the removal of elements, |
983 |
* as per the Javasoft spec. Note that it is not synchronized; this is |
984 |
* a performance enhancer since it is never exposed externally and is |
985 |
* only used within synchronized blocks above. |
986 |
* |
987 |
* @author Jon Zeppieri |
988 |
*/ |
989 |
private final class HashIterator implements Iterator |
990 |
{ |
991 |
/** |
992 |
* The type of this Iterator: {@link #KEYS}, {@link #VALUES}, |
993 |
* or {@link #ENTRIES}. |
994 |
*/ |
995 |
final int type; |
996 |
/** |
997 |
* The number of modifications to the backing Hashtable that we know about. |
998 |
*/ |
999 |
int knownMod = modCount; |
1000 |
/** The number of elements remaining to be returned by next(). */ |
1001 |
int count = size; |
1002 |
/** Current index in the physical hash table. */ |
1003 |
int idx = buckets.length; |
1004 |
/** The last Entry returned by a next() call. */ |
1005 |
HashEntry last; |
1006 |
/** |
1007 |
* The next entry that should be returned by next(). It is set to something |
1008 |
* if we're iterating through a bucket that contains multiple linked |
1009 |
* entries. It is null if next() needs to find a new bucket. |
1010 |
*/ |
1011 |
HashEntry next; |
1012 |
|
1013 |
/** |
1014 |
* Construct a new HashIterator with the supplied type. |
1015 |
* @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} |
1016 |
*/ |
1017 |
HashIterator(int type) |
1018 |
{ |
1019 |
this.type = type; |
1020 |
} |
1021 |
|
1022 |
/** |
1023 |
* Returns true if the Iterator has more elements. |
1024 |
* @return true if there are more elements |
1025 |
* @throws ConcurrentModificationException if the hashtable was modified |
1026 |
*/ |
1027 |
public boolean hasNext() |
1028 |
{ |
1029 |
if (knownMod != modCount) |
1030 |
throw new ConcurrentModificationException(); |
1031 |
return count > 0; |
1032 |
} |
1033 |
|
1034 |
/** |
1035 |
* Returns the next element in the Iterator's sequential view. |
1036 |
* @return the next element |
1037 |
* @throws ConcurrentModificationException if the hashtable was modified |
1038 |
* @throws NoSuchElementException if there is none |
1039 |
*/ |
1040 |
public Object next() |
1041 |
{ |
1042 |
if (knownMod != modCount) |
1043 |
throw new ConcurrentModificationException(); |
1044 |
if (count == 0) |
1045 |
throw new NoSuchElementException(); |
1046 |
count--; |
1047 |
HashEntry e = next; |
1048 |
|
1049 |
while (e == null) |
1050 |
e = buckets[--idx]; |
1051 |
|
1052 |
next = e.next; |
1053 |
last = e; |
1054 |
if (type == VALUES) |
1055 |
return e.value; |
1056 |
if (type == KEYS) |
1057 |
return e.key; |
1058 |
return e; |
1059 |
} |
1060 |
|
1061 |
/** |
1062 |
* Removes from the backing Hashtable the last element which was fetched |
1063 |
* with the <code>next()</code> method. |
1064 |
* @throws ConcurrentModificationException if the hashtable was modified |
1065 |
* @throws IllegalStateException if called when there is no last element |
1066 |
*/ |
1067 |
public void remove() |
1068 |
{ |
1069 |
if (knownMod != modCount) |
1070 |
throw new ConcurrentModificationException(); |
1071 |
if (last == null) |
1072 |
throw new IllegalStateException(); |
1073 |
|
1074 |
Hashtable.this.remove(last.key); |
1075 |
last = null; |
1076 |
knownMod++; |
1077 |
} |
1078 |
} // class HashIterator |
1079 |
|
1080 |
|
1081 |
/** |
1082 |
* Enumeration view of this Hashtable, providing sequential access to its |
1083 |
* elements; this implementation is parameterized to provide access either |
1084 |
* to the keys or to the values in the Hashtable. |
1085 |
* |
1086 |
* <b>NOTE</b>: Enumeration is not safe if new elements are put in the table |
1087 |
* as this could cause a rehash and we'd completely lose our place. Even |
1088 |
* without a rehash, it is undetermined if a new element added would |
1089 |
* appear in the enumeration. The spec says nothing about this, but |
1090 |
* the "Java Class Libraries" book infers that modifications to the |
1091 |
* hashtable during enumeration causes indeterminate results. Don't do it! |
1092 |
* |
1093 |
* @author Jon Zeppieri |
1094 |
*/ |
1095 |
private final class Enumerator implements Enumeration |
1096 |
{ |
1097 |
/** |
1098 |
* The type of this Iterator: {@link #KEYS} or {@link #VALUES}. |
1099 |
*/ |
1100 |
final int type; |
1101 |
/** The number of elements remaining to be returned by next(). */ |
1102 |
int count = size; |
1103 |
/** Current index in the physical hash table. */ |
1104 |
int idx = buckets.length; |
1105 |
/** |
1106 |
* Entry which will be returned by the next nextElement() call. It is |
1107 |
* set if we are iterating through a bucket with multiple entries, or null |
1108 |
* if we must look in the next bucket. |
1109 |
*/ |
1110 |
HashEntry next; |
1111 |
|
1112 |
/** |
1113 |
* Construct the enumeration. |
1114 |
* @param type either {@link #KEYS} or {@link #VALUES}. |
1115 |
*/ |
1116 |
Enumerator(int type) |
1117 |
{ |
1118 |
this.type = type; |
1119 |
} |
1120 |
|
1121 |
/** |
1122 |
* Checks whether more elements remain in the enumeration. |
1123 |
* @return true if nextElement() will not fail. |
1124 |
*/ |
1125 |
public boolean hasMoreElements() |
1126 |
{ |
1127 |
return count > 0; |
1128 |
} |
1129 |
|
1130 |
/** |
1131 |
* Returns the next element. |
1132 |
* @return the next element |
1133 |
* @throws NoSuchElementException if there is none. |
1134 |
*/ |
1135 |
public Object nextElement() |
1136 |
{ |
1137 |
if (count == 0) |
1138 |
throw new NoSuchElementException("Hashtable Enumerator"); |
1139 |
count--; |
1140 |
HashEntry e = next; |
1141 |
|
1142 |
while (e == null) |
1143 |
e = buckets[--idx]; |
1144 |
|
1145 |
next = e.next; |
1146 |
return type == VALUES ? e.value : e.key; |
1147 |
} |
1148 |
} // class Enumerator |
1149 |
} // class Hashtable |