0001 /*
0002 * Copyright 1994-2006 Sun Microsystems, Inc. All Rights Reserved.
0003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0004 *
0005 * This code is free software; you can redistribute it and/or modify it
0006 * under the terms of the GNU General Public License version 2 only, as
0007 * published by the Free Software Foundation. Sun designates this
0008 * particular file as subject to the "Classpath" exception as provided
0009 * by Sun in the LICENSE file that accompanied this code.
0010 *
0011 * This code is distributed in the hope that it will be useful, but WITHOUT
0012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0014 * version 2 for more details (a copy is included in the LICENSE file that
0015 * accompanied this code).
0016 *
0017 * You should have received a copy of the GNU General Public License version
0018 * 2 along with this work; if not, write to the Free Software Foundation,
0019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0020 *
0021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0022 * CA 95054 USA or visit www.sun.com if you need additional information or
0023 * have any questions.
0024 */
0025
0026 package java.util;
0027
0028 import java.io.*;
0029
0030 /**
0031 * This class implements a hashtable, which maps keys to values. Any
0032 * non-<code>null</code> object can be used as a key or as a value. <p>
0033 *
0034 * To successfully store and retrieve objects from a hashtable, the
0035 * objects used as keys must implement the <code>hashCode</code>
0036 * method and the <code>equals</code> method. <p>
0037 *
0038 * An instance of <code>Hashtable</code> has two parameters that affect its
0039 * performance: <i>initial capacity</i> and <i>load factor</i>. The
0040 * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
0041 * <i>initial capacity</i> is simply the capacity at the time the hash table
0042 * is created. Note that the hash table is <i>open</i>: in the case of a "hash
0043 * collision", a single bucket stores multiple entries, which must be searched
0044 * sequentially. The <i>load factor</i> is a measure of how full the hash
0045 * table is allowed to get before its capacity is automatically increased.
0046 * The initial capacity and load factor parameters are merely hints to
0047 * the implementation. The exact details as to when and whether the rehash
0048 * method is invoked are implementation-dependent.<p>
0049 *
0050 * Generally, the default load factor (.75) offers a good tradeoff between
0051 * time and space costs. Higher values decrease the space overhead but
0052 * increase the time cost to look up an entry (which is reflected in most
0053 * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p>
0054 *
0055 * The initial capacity controls a tradeoff between wasted space and the
0056 * need for <code>rehash</code> operations, which are time-consuming.
0057 * No <code>rehash</code> operations will <i>ever</i> occur if the initial
0058 * capacity is greater than the maximum number of entries the
0059 * <tt>Hashtable</tt> will contain divided by its load factor. However,
0060 * setting the initial capacity too high can waste space.<p>
0061 *
0062 * If many entries are to be made into a <code>Hashtable</code>,
0063 * creating it with a sufficiently large capacity may allow the
0064 * entries to be inserted more efficiently than letting it perform
0065 * automatic rehashing as needed to grow the table. <p>
0066 *
0067 * This example creates a hashtable of numbers. It uses the names of
0068 * the numbers as keys:
0069 * <pre> {@code
0070 * Hashtable<String, Integer> numbers
0071 * = new Hashtable<String, Integer>();
0072 * numbers.put("one", 1);
0073 * numbers.put("two", 2);
0074 * numbers.put("three", 3);}</pre>
0075 *
0076 * <p>To retrieve a number, use the following code:
0077 * <pre> {@code
0078 * Integer n = numbers.get("two");
0079 * if (n != null) {
0080 * System.out.println("two = " + n);
0081 * }}</pre>
0082 *
0083 * <p>The iterators returned by the <tt>iterator</tt> method of the collections
0084 * returned by all of this class's "collection view methods" are
0085 * <em>fail-fast</em>: if the Hashtable is structurally modified at any time
0086 * after the iterator is created, in any way except through the iterator's own
0087 * <tt>remove</tt> method, the iterator will throw a {@link
0088 * ConcurrentModificationException}. Thus, in the face of concurrent
0089 * modification, the iterator fails quickly and cleanly, rather than risking
0090 * arbitrary, non-deterministic behavior at an undetermined time in the future.
0091 * The Enumerations returned by Hashtable's keys and elements methods are
0092 * <em>not</em> fail-fast.
0093 *
0094 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
0095 * as it is, generally speaking, impossible to make any hard guarantees in the
0096 * presence of unsynchronized concurrent modification. Fail-fast iterators
0097 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
0098 * Therefore, it would be wrong to write a program that depended on this
0099 * exception for its correctness: <i>the fail-fast behavior of iterators
0100 * should be used only to detect bugs.</i>
0101 *
0102 * <p>As of the Java 2 platform v1.2, this class was retrofitted to
0103 * implement the {@link Map} interface, making it a member of the
0104 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> Java
0105 * Collections Framework</a>. Unlike the new collection
0106 * implementations, {@code Hashtable} is synchronized.
0107 *
0108 * @author Arthur van Hoff
0109 * @author Josh Bloch
0110 * @author Neal Gafter
0111 * @version 1.123, 07/08/07
0112 * @see Object#equals(java.lang.Object)
0113 * @see Object#hashCode()
0114 * @see Hashtable#rehash()
0115 * @see Collection
0116 * @see Map
0117 * @see HashMap
0118 * @see TreeMap
0119 * @since JDK1.0
0120 */
0121 public class Hashtable<K, V> extends Dictionary<K, V> implements
0122 Map<K, V>, Cloneable, java.io.Serializable {
0123
0124 /**
0125 * The hash table data.
0126 */
0127 private transient Entry[] table;
0128
0129 /**
0130 * The total number of entries in the hash table.
0131 */
0132 private transient int count;
0133
0134 /**
0135 * The table is rehashed when its size exceeds this threshold. (The
0136 * value of this field is (int)(capacity * loadFactor).)
0137 *
0138 * @serial
0139 */
0140 private int threshold;
0141
0142 /**
0143 * The load factor for the hashtable.
0144 *
0145 * @serial
0146 */
0147 private float loadFactor;
0148
0149 /**
0150 * The number of times this Hashtable has been structurally modified
0151 * Structural modifications are those that change the number of entries in
0152 * the Hashtable or otherwise modify its internal structure (e.g.,
0153 * rehash). This field is used to make iterators on Collection-views of
0154 * the Hashtable fail-fast. (See ConcurrentModificationException).
0155 */
0156 private transient int modCount = 0;
0157
0158 /** use serialVersionUID from JDK 1.0.2 for interoperability */
0159 private static final long serialVersionUID = 1421746759512286392L;
0160
0161 /**
0162 * Constructs a new, empty hashtable with the specified initial
0163 * capacity and the specified load factor.
0164 *
0165 * @param initialCapacity the initial capacity of the hashtable.
0166 * @param loadFactor the load factor of the hashtable.
0167 * @exception IllegalArgumentException if the initial capacity is less
0168 * than zero, or if the load factor is nonpositive.
0169 */
0170 public Hashtable(int initialCapacity, float loadFactor) {
0171 if (initialCapacity < 0)
0172 throw new IllegalArgumentException("Illegal Capacity: "
0173 + initialCapacity);
0174 if (loadFactor <= 0 || Float.isNaN(loadFactor))
0175 throw new IllegalArgumentException("Illegal Load: "
0176 + loadFactor);
0177
0178 if (initialCapacity == 0)
0179 initialCapacity = 1;
0180 this .loadFactor = loadFactor;
0181 table = new Entry[initialCapacity];
0182 threshold = (int) (initialCapacity * loadFactor);
0183 }
0184
0185 /**
0186 * Constructs a new, empty hashtable with the specified initial capacity
0187 * and default load factor (0.75).
0188 *
0189 * @param initialCapacity the initial capacity of the hashtable.
0190 * @exception IllegalArgumentException if the initial capacity is less
0191 * than zero.
0192 */
0193 public Hashtable(int initialCapacity) {
0194 this (initialCapacity, 0.75f);
0195 }
0196
0197 /**
0198 * Constructs a new, empty hashtable with a default initial capacity (11)
0199 * and load factor (0.75).
0200 */
0201 public Hashtable() {
0202 this (11, 0.75f);
0203 }
0204
0205 /**
0206 * Constructs a new hashtable with the same mappings as the given
0207 * Map. The hashtable is created with an initial capacity sufficient to
0208 * hold the mappings in the given Map and a default load factor (0.75).
0209 *
0210 * @param t the map whose mappings are to be placed in this map.
0211 * @throws NullPointerException if the specified map is null.
0212 * @since 1.2
0213 */
0214 public Hashtable(Map<? extends K, ? extends V> t) {
0215 this (Math.max(2 * t.size(), 11), 0.75f);
0216 putAll(t);
0217 }
0218
0219 /**
0220 * Returns the number of keys in this hashtable.
0221 *
0222 * @return the number of keys in this hashtable.
0223 */
0224 public synchronized int size() {
0225 return count;
0226 }
0227
0228 /**
0229 * Tests if this hashtable maps no keys to values.
0230 *
0231 * @return <code>true</code> if this hashtable maps no keys to values;
0232 * <code>false</code> otherwise.
0233 */
0234 public synchronized boolean isEmpty() {
0235 return count == 0;
0236 }
0237
0238 /**
0239 * Returns an enumeration of the keys in this hashtable.
0240 *
0241 * @return an enumeration of the keys in this hashtable.
0242 * @see Enumeration
0243 * @see #elements()
0244 * @see #keySet()
0245 * @see Map
0246 */
0247 public synchronized Enumeration<K> keys() {
0248 return this .<K> getEnumeration(KEYS);
0249 }
0250
0251 /**
0252 * Returns an enumeration of the values in this hashtable.
0253 * Use the Enumeration methods on the returned object to fetch the elements
0254 * sequentially.
0255 *
0256 * @return an enumeration of the values in this hashtable.
0257 * @see java.util.Enumeration
0258 * @see #keys()
0259 * @see #values()
0260 * @see Map
0261 */
0262 public synchronized Enumeration<V> elements() {
0263 return this .<V> getEnumeration(VALUES);
0264 }
0265
0266 /**
0267 * Tests if some key maps into the specified value in this hashtable.
0268 * This operation is more expensive than the {@link #containsKey
0269 * containsKey} method.
0270 *
0271 * <p>Note that this method is identical in functionality to
0272 * {@link #containsValue containsValue}, (which is part of the
0273 * {@link Map} interface in the collections framework).
0274 *
0275 * @param value a value to search for
0276 * @return <code>true</code> if and only if some key maps to the
0277 * <code>value</code> argument in this hashtable as
0278 * determined by the <tt>equals</tt> method;
0279 * <code>false</code> otherwise.
0280 * @exception NullPointerException if the value is <code>null</code>
0281 */
0282 public synchronized boolean contains(Object value) {
0283 if (value == null) {
0284 throw new NullPointerException();
0285 }
0286
0287 Entry tab[] = table;
0288 for (int i = tab.length; i-- > 0;) {
0289 for (Entry<K, V> e = tab[i]; e != null; e = e.next) {
0290 if (e.value.equals(value)) {
0291 return true;
0292 }
0293 }
0294 }
0295 return false;
0296 }
0297
0298 /**
0299 * Returns true if this hashtable maps one or more keys to this value.
0300 *
0301 * <p>Note that this method is identical in functionality to {@link
0302 * #contains contains} (which predates the {@link Map} interface).
0303 *
0304 * @param value value whose presence in this hashtable is to be tested
0305 * @return <tt>true</tt> if this map maps one or more keys to the
0306 * specified value
0307 * @throws NullPointerException if the value is <code>null</code>
0308 * @since 1.2
0309 */
0310 public boolean containsValue(Object value) {
0311 return contains(value);
0312 }
0313
0314 /**
0315 * Tests if the specified object is a key in this hashtable.
0316 *
0317 * @param key possible key
0318 * @return <code>true</code> if and only if the specified object
0319 * is a key in this hashtable, as determined by the
0320 * <tt>equals</tt> method; <code>false</code> otherwise.
0321 * @throws NullPointerException if the key is <code>null</code>
0322 * @see #contains(Object)
0323 */
0324 public synchronized boolean containsKey(Object key) {
0325 Entry tab[] = table;
0326 int hash = key.hashCode();
0327 int index = (hash & 0x7FFFFFFF) % tab.length;
0328 for (Entry<K, V> e = tab[index]; e != null; e = e.next) {
0329 if ((e.hash == hash) && e.key.equals(key)) {
0330 return true;
0331 }
0332 }
0333 return false;
0334 }
0335
0336 /**
0337 * Returns the value to which the specified key is mapped,
0338 * or {@code null} if this map contains no mapping for the key.
0339 *
0340 * <p>More formally, if this map contains a mapping from a key
0341 * {@code k} to a value {@code v} such that {@code (key.equals(k))},
0342 * then this method returns {@code v}; otherwise it returns
0343 * {@code null}. (There can be at most one such mapping.)
0344 *
0345 * @param key the key whose associated value is to be returned
0346 * @return the value to which the specified key is mapped, or
0347 * {@code null} if this map contains no mapping for the key
0348 * @throws NullPointerException if the specified key is null
0349 * @see #put(Object, Object)
0350 */
0351 public synchronized V get(Object key) {
0352 Entry tab[] = table;
0353 int hash = key.hashCode();
0354 int index = (hash & 0x7FFFFFFF) % tab.length;
0355 for (Entry<K, V> e = tab[index]; e != null; e = e.next) {
0356 if ((e.hash == hash) && e.key.equals(key)) {
0357 return e.value;
0358 }
0359 }
0360 return null;
0361 }
0362
0363 /**
0364 * Increases the capacity of and internally reorganizes this
0365 * hashtable, in order to accommodate and access its entries more
0366 * efficiently. This method is called automatically when the
0367 * number of keys in the hashtable exceeds this hashtable's capacity
0368 * and load factor.
0369 */
0370 protected void rehash() {
0371 int oldCapacity = table.length;
0372 Entry[] oldMap = table;
0373
0374 int newCapacity = oldCapacity * 2 + 1;
0375 Entry[] newMap = new Entry[newCapacity];
0376
0377 modCount++;
0378 threshold = (int) (newCapacity * loadFactor);
0379 table = newMap;
0380
0381 for (int i = oldCapacity; i-- > 0;) {
0382 for (Entry<K, V> old = oldMap[i]; old != null;) {
0383 Entry<K, V> e = old;
0384 old = old.next;
0385
0386 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
0387 e.next = newMap[index];
0388 newMap[index] = e;
0389 }
0390 }
0391 }
0392
0393 /**
0394 * Maps the specified <code>key</code> to the specified
0395 * <code>value</code> in this hashtable. Neither the key nor the
0396 * value can be <code>null</code>. <p>
0397 *
0398 * The value can be retrieved by calling the <code>get</code> method
0399 * with a key that is equal to the original key.
0400 *
0401 * @param key the hashtable key
0402 * @param value the value
0403 * @return the previous value of the specified key in this hashtable,
0404 * or <code>null</code> if it did not have one
0405 * @exception NullPointerException if the key or value is
0406 * <code>null</code>
0407 * @see Object#equals(Object)
0408 * @see #get(Object)
0409 */
0410 public synchronized V put(K key, V value) {
0411 // Make sure the value is not null
0412 if (value == null) {
0413 throw new NullPointerException();
0414 }
0415
0416 // Makes sure the key is not already in the hashtable.
0417 Entry tab[] = table;
0418 int hash = key.hashCode();
0419 int index = (hash & 0x7FFFFFFF) % tab.length;
0420 for (Entry<K, V> e = tab[index]; e != null; e = e.next) {
0421 if ((e.hash == hash) && e.key.equals(key)) {
0422 V old = e.value;
0423 e.value = value;
0424 return old;
0425 }
0426 }
0427
0428 modCount++;
0429 if (count >= threshold) {
0430 // Rehash the table if the threshold is exceeded
0431 rehash();
0432
0433 tab = table;
0434 index = (hash & 0x7FFFFFFF) % tab.length;
0435 }
0436
0437 // Creates the new entry.
0438 Entry<K, V> e = tab[index];
0439 tab[index] = new Entry<K, V>(hash, key, value, e);
0440 count++;
0441 return null;
0442 }
0443
0444 /**
0445 * Removes the key (and its corresponding value) from this
0446 * hashtable. This method does nothing if the key is not in the hashtable.
0447 *
0448 * @param key the key that needs to be removed
0449 * @return the value to which the key had been mapped in this hashtable,
0450 * or <code>null</code> if the key did not have a mapping
0451 * @throws NullPointerException if the key is <code>null</code>
0452 */
0453 public synchronized V remove(Object key) {
0454 Entry tab[] = table;
0455 int hash = key.hashCode();
0456 int index = (hash & 0x7FFFFFFF) % tab.length;
0457 for (Entry<K, V> e = tab[index], prev = null; e != null; prev = e, e = e.next) {
0458 if ((e.hash == hash) && e.key.equals(key)) {
0459 modCount++;
0460 if (prev != null) {
0461 prev.next = e.next;
0462 } else {
0463 tab[index] = e.next;
0464 }
0465 count--;
0466 V oldValue = e.value;
0467 e.value = null;
0468 return oldValue;
0469 }
0470 }
0471 return null;
0472 }
0473
0474 /**
0475 * Copies all of the mappings from the specified map to this hashtable.
0476 * These mappings will replace any mappings that this hashtable had for any
0477 * of the keys currently in the specified map.
0478 *
0479 * @param t mappings to be stored in this map
0480 * @throws NullPointerException if the specified map is null
0481 * @since 1.2
0482 */
0483 public synchronized void putAll(Map<? extends K, ? extends V> t) {
0484 for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
0485 put(e.getKey(), e.getValue());
0486 }
0487
0488 /**
0489 * Clears this hashtable so that it contains no keys.
0490 */
0491 public synchronized void clear() {
0492 Entry tab[] = table;
0493 modCount++;
0494 for (int index = tab.length; --index >= 0;)
0495 tab[index] = null;
0496 count = 0;
0497 }
0498
0499 /**
0500 * Creates a shallow copy of this hashtable. All the structure of the
0501 * hashtable itself is copied, but the keys and values are not cloned.
0502 * This is a relatively expensive operation.
0503 *
0504 * @return a clone of the hashtable
0505 */
0506 public synchronized Object clone() {
0507 try {
0508 Hashtable<K, V> t = (Hashtable<K, V>) super .clone();
0509 t.table = new Entry[table.length];
0510 for (int i = table.length; i-- > 0;) {
0511 t.table[i] = (table[i] != null) ? (Entry<K, V>) table[i]
0512 .clone()
0513 : null;
0514 }
0515 t.keySet = null;
0516 t.entrySet = null;
0517 t.values = null;
0518 t.modCount = 0;
0519 return t;
0520 } catch (CloneNotSupportedException e) {
0521 // this shouldn't happen, since we are Cloneable
0522 throw new InternalError();
0523 }
0524 }
0525
0526 /**
0527 * Returns a string representation of this <tt>Hashtable</tt> object
0528 * in the form of a set of entries, enclosed in braces and separated
0529 * by the ASCII characters "<tt>, </tt>" (comma and space). Each
0530 * entry is rendered as the key, an equals sign <tt>=</tt>, and the
0531 * associated element, where the <tt>toString</tt> method is used to
0532 * convert the key and element to strings.
0533 *
0534 * @return a string representation of this hashtable
0535 */
0536 public synchronized String toString() {
0537 int max = size() - 1;
0538 if (max == -1)
0539 return "{}";
0540
0541 StringBuilder sb = new StringBuilder();
0542 Iterator<Map.Entry<K, V>> it = entrySet().iterator();
0543
0544 sb.append('{');
0545 for (int i = 0;; i++) {
0546 Map.Entry<K, V> e = it.next();
0547 K key = e.getKey();
0548 V value = e.getValue();
0549 sb.append(key == this ? "(this Map)" : key.toString());
0550 sb.append('=');
0551 sb.append(value == this ? "(this Map)" : value.toString());
0552
0553 if (i == max)
0554 return sb.append('}').toString();
0555 sb.append(", ");
0556 }
0557 }
0558
0559 private <T> Enumeration<T> getEnumeration(int type) {
0560 if (count == 0) {
0561 return Collections.emptyEnumeration();
0562 } else {
0563 return new Enumerator<T>(type, false);
0564 }
0565 }
0566
0567 private <T> Iterator<T> getIterator(int type) {
0568 if (count == 0) {
0569 return Collections.emptyIterator();
0570 } else {
0571 return new Enumerator<T>(type, true);
0572 }
0573 }
0574
0575 // Views
0576
0577 /**
0578 * Each of these fields are initialized to contain an instance of the
0579 * appropriate view the first time this view is requested. The views are
0580 * stateless, so there's no reason to create more than one of each.
0581 */
0582 private transient volatile Set<K> keySet = null;
0583 private transient volatile Set<Map.Entry<K, V>> entrySet = null;
0584 private transient volatile Collection<V> values = null;
0585
0586 /**
0587 * Returns a {@link Set} view of the keys contained in this map.
0588 * The set is backed by the map, so changes to the map are
0589 * reflected in the set, and vice-versa. If the map is modified
0590 * while an iteration over the set is in progress (except through
0591 * the iterator's own <tt>remove</tt> operation), the results of
0592 * the iteration are undefined. The set supports element removal,
0593 * which removes the corresponding mapping from the map, via the
0594 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
0595 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
0596 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
0597 * operations.
0598 *
0599 * @since 1.2
0600 */
0601 public Set<K> keySet() {
0602 if (keySet == null)
0603 keySet = Collections.synchronizedSet(new KeySet(), this );
0604 return keySet;
0605 }
0606
0607 private class KeySet extends AbstractSet<K> {
0608 public Iterator<K> iterator() {
0609 return getIterator(KEYS);
0610 }
0611
0612 public int size() {
0613 return count;
0614 }
0615
0616 public boolean contains(Object o) {
0617 return containsKey(o);
0618 }
0619
0620 public boolean remove(Object o) {
0621 return Hashtable.this .remove(o) != null;
0622 }
0623
0624 public void clear() {
0625 Hashtable.this .clear();
0626 }
0627 }
0628
0629 /**
0630 * Returns a {@link Set} view of the mappings contained in this map.
0631 * The set is backed by the map, so changes to the map are
0632 * reflected in the set, and vice-versa. If the map is modified
0633 * while an iteration over the set is in progress (except through
0634 * the iterator's own <tt>remove</tt> operation, or through the
0635 * <tt>setValue</tt> operation on a map entry returned by the
0636 * iterator) the results of the iteration are undefined. The set
0637 * supports element removal, which removes the corresponding
0638 * mapping from the map, via the <tt>Iterator.remove</tt>,
0639 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
0640 * <tt>clear</tt> operations. It does not support the
0641 * <tt>add</tt> or <tt>addAll</tt> operations.
0642 *
0643 * @since 1.2
0644 */
0645 public Set<Map.Entry<K, V>> entrySet() {
0646 if (entrySet == null)
0647 entrySet = Collections
0648 .synchronizedSet(new EntrySet(), this );
0649 return entrySet;
0650 }
0651
0652 private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
0653 public Iterator<Map.Entry<K, V>> iterator() {
0654 return getIterator(ENTRIES);
0655 }
0656
0657 public boolean add(Map.Entry<K, V> o) {
0658 return super .add(o);
0659 }
0660
0661 public boolean contains(Object o) {
0662 if (!(o instanceof Map.Entry))
0663 return false;
0664 Map.Entry entry = (Map.Entry) o;
0665 Object key = entry.getKey();
0666 Entry[] tab = table;
0667 int hash = key.hashCode();
0668 int index = (hash & 0x7FFFFFFF) % tab.length;
0669
0670 for (Entry e = tab[index]; e != null; e = e.next)
0671 if (e.hash == hash && e.equals(entry))
0672 return true;
0673 return false;
0674 }
0675
0676 public boolean remove(Object o) {
0677 if (!(o instanceof Map.Entry))
0678 return false;
0679 Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
0680 K key = entry.getKey();
0681 Entry[] tab = table;
0682 int hash = key.hashCode();
0683 int index = (hash & 0x7FFFFFFF) % tab.length;
0684
0685 for (Entry<K, V> e = tab[index], prev = null; e != null; prev = e, e = e.next) {
0686 if (e.hash == hash && e.equals(entry)) {
0687 modCount++;
0688 if (prev != null)
0689 prev.next = e.next;
0690 else
0691 tab[index] = e.next;
0692
0693 count--;
0694 e.value = null;
0695 return true;
0696 }
0697 }
0698 return false;
0699 }
0700
0701 public int size() {
0702 return count;
0703 }
0704
0705 public void clear() {
0706 Hashtable.this .clear();
0707 }
0708 }
0709
0710 /**
0711 * Returns a {@link Collection} view of the values contained in this map.
0712 * The collection is backed by the map, so changes to the map are
0713 * reflected in the collection, and vice-versa. If the map is
0714 * modified while an iteration over the collection is in progress
0715 * (except through the iterator's own <tt>remove</tt> operation),
0716 * the results of the iteration are undefined. The collection
0717 * supports element removal, which removes the corresponding
0718 * mapping from the map, via the <tt>Iterator.remove</tt>,
0719 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
0720 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
0721 * support the <tt>add</tt> or <tt>addAll</tt> operations.
0722 *
0723 * @since 1.2
0724 */
0725 public Collection<V> values() {
0726 if (values == null)
0727 values = Collections.synchronizedCollection(
0728 new ValueCollection(), this );
0729 return values;
0730 }
0731
0732 private class ValueCollection extends AbstractCollection<V> {
0733 public Iterator<V> iterator() {
0734 return getIterator(VALUES);
0735 }
0736
0737 public int size() {
0738 return count;
0739 }
0740
0741 public boolean contains(Object o) {
0742 return containsValue(o);
0743 }
0744
0745 public void clear() {
0746 Hashtable.this .clear();
0747 }
0748 }
0749
0750 // Comparison and hashing
0751
0752 /**
0753 * Compares the specified Object with this Map for equality,
0754 * as per the definition in the Map interface.
0755 *
0756 * @param o object to be compared for equality with this hashtable
0757 * @return true if the specified Object is equal to this Map
0758 * @see Map#equals(Object)
0759 * @since 1.2
0760 */
0761 public synchronized boolean equals(Object o) {
0762 if (o == this )
0763 return true;
0764
0765 if (!(o instanceof Map))
0766 return false;
0767 Map<K, V> t = (Map<K, V>) o;
0768 if (t.size() != size())
0769 return false;
0770
0771 try {
0772 Iterator<Map.Entry<K, V>> i = entrySet().iterator();
0773 while (i.hasNext()) {
0774 Map.Entry<K, V> e = i.next();
0775 K key = e.getKey();
0776 V value = e.getValue();
0777 if (value == null) {
0778 if (!(t.get(key) == null && t.containsKey(key)))
0779 return false;
0780 } else {
0781 if (!value.equals(t.get(key)))
0782 return false;
0783 }
0784 }
0785 } catch (ClassCastException unused) {
0786 return false;
0787 } catch (NullPointerException unused) {
0788 return false;
0789 }
0790
0791 return true;
0792 }
0793
0794 /**
0795 * Returns the hash code value for this Map as per the definition in the
0796 * Map interface.
0797 *
0798 * @see Map#hashCode()
0799 * @since 1.2
0800 */
0801 public synchronized int hashCode() {
0802 /*
0803 * This code detects the recursion caused by computing the hash code
0804 * of a self-referential hash table and prevents the stack overflow
0805 * that would otherwise result. This allows certain 1.1-era
0806 * applets with self-referential hash tables to work. This code
0807 * abuses the loadFactor field to do double-duty as a hashCode
0808 * in progress flag, so as not to worsen the space performance.
0809 * A negative load factor indicates that hash code computation is
0810 * in progress.
0811 */
0812 int h = 0;
0813 if (count == 0 || loadFactor < 0)
0814 return h; // Returns zero
0815
0816 loadFactor = -loadFactor; // Mark hashCode computation in progress
0817 Entry[] tab = table;
0818 for (int i = 0; i < tab.length; i++)
0819 for (Entry e = tab[i]; e != null; e = e.next)
0820 h += e.key.hashCode() ^ e.value.hashCode();
0821 loadFactor = -loadFactor; // Mark hashCode computation complete
0822
0823 return h;
0824 }
0825
0826 /**
0827 * Save the state of the Hashtable to a stream (i.e., serialize it).
0828 *
0829 * @serialData The <i>capacity</i> of the Hashtable (the length of the
0830 * bucket array) is emitted (int), followed by the
0831 * <i>size</i> of the Hashtable (the number of key-value
0832 * mappings), followed by the key (Object) and value (Object)
0833 * for each key-value mapping represented by the Hashtable
0834 * The key-value mappings are emitted in no particular order.
0835 */
0836 private synchronized void writeObject(java.io.ObjectOutputStream s)
0837 throws IOException {
0838 // Write out the length, threshold, loadfactor
0839 s.defaultWriteObject();
0840
0841 // Write out length, count of elements and then the key/value objects
0842 s.writeInt(table.length);
0843 s.writeInt(count);
0844 for (int index = table.length - 1; index >= 0; index--) {
0845 Entry entry = table[index];
0846
0847 while (entry != null) {
0848 s.writeObject(entry.key);
0849 s.writeObject(entry.value);
0850 entry = entry.next;
0851 }
0852 }
0853 }
0854
0855 /**
0856 * Reconstitute the Hashtable from a stream (i.e., deserialize it).
0857 */
0858 private void readObject(java.io.ObjectInputStream s)
0859 throws IOException, ClassNotFoundException {
0860 // Read in the length, threshold, and loadfactor
0861 s.defaultReadObject();
0862
0863 // Read the original length of the array and number of elements
0864 int origlength = s.readInt();
0865 int elements = s.readInt();
0866
0867 // Compute new size with a bit of room 5% to grow but
0868 // no larger than the original size. Make the length
0869 // odd if it's large enough, this helps distribute the entries.
0870 // Guard against the length ending up zero, that's not valid.
0871 int length = (int) (elements * loadFactor) + (elements / 20)
0872 + 3;
0873 if (length > elements && (length & 1) == 0)
0874 length--;
0875 if (origlength > 0 && length > origlength)
0876 length = origlength;
0877
0878 Entry[] table = new Entry[length];
0879 count = 0;
0880
0881 // Read the number of elements and then all the key/value objects
0882 for (; elements > 0; elements--) {
0883 K key = (K) s.readObject();
0884 V value = (V) s.readObject();
0885 // synch could be eliminated for performance
0886 reconstitutionPut(table, key, value);
0887 }
0888 this .table = table;
0889 }
0890
0891 /**
0892 * The put method used by readObject. This is provided because put
0893 * is overridable and should not be called in readObject since the
0894 * subclass will not yet be initialized.
0895 *
0896 * <p>This differs from the regular put method in several ways. No
0897 * checking for rehashing is necessary since the number of elements
0898 * initially in the table is known. The modCount is not incremented
0899 * because we are creating a new instance. Also, no return value
0900 * is needed.
0901 */
0902 private void reconstitutionPut(Entry[] tab, K key, V value)
0903 throws StreamCorruptedException {
0904 if (value == null) {
0905 throw new java.io.StreamCorruptedException();
0906 }
0907 // Makes sure the key is not already in the hashtable.
0908 // This should not happen in deserialized version.
0909 int hash = key.hashCode();
0910 int index = (hash & 0x7FFFFFFF) % tab.length;
0911 for (Entry<K, V> e = tab[index]; e != null; e = e.next) {
0912 if ((e.hash == hash) && e.key.equals(key)) {
0913 throw new java.io.StreamCorruptedException();
0914 }
0915 }
0916 // Creates the new entry.
0917 Entry<K, V> e = tab[index];
0918 tab[index] = new Entry<K, V>(hash, key, value, e);
0919 count++;
0920 }
0921
0922 /**
0923 * Hashtable collision list.
0924 */
0925 private static class Entry<K, V> implements Map.Entry<K, V> {
0926 int hash;
0927 K key;
0928 V value;
0929 Entry<K, V> next;
0930
0931 protected Entry(int hash, K key, V value, Entry<K, V> next) {
0932 this .hash = hash;
0933 this .key = key;
0934 this .value = value;
0935 this .next = next;
0936 }
0937
0938 protected Object clone() {
0939 return new Entry<K, V>(hash, key, value,
0940 (next == null ? null : (Entry<K, V>) next.clone()));
0941 }
0942
0943 // Map.Entry Ops
0944
0945 public K getKey() {
0946 return key;
0947 }
0948
0949 public V getValue() {
0950 return value;
0951 }
0952
0953 public V setValue(V value) {
0954 if (value == null)
0955 throw new NullPointerException();
0956
0957 V oldValue = this .value;
0958 this .value = value;
0959 return oldValue;
0960 }
0961
0962 public boolean equals(Object o) {
0963 if (!(o instanceof Map.Entry))
0964 return false;
0965 Map.Entry e = (Map.Entry) o;
0966
0967 return (key == null ? e.getKey() == null : key.equals(e
0968 .getKey()))
0969 && (value == null ? e.getValue() == null : value
0970 .equals(e.getValue()));
0971 }
0972
0973 public int hashCode() {
0974 return hash ^ (value == null ? 0 : value.hashCode());
0975 }
0976
0977 public String toString() {
0978 return key.toString() + "=" + value.toString();
0979 }
0980 }
0981
0982 // Types of Enumerations/Iterations
0983 private static final int KEYS = 0;
0984 private static final int VALUES = 1;
0985 private static final int ENTRIES = 2;
0986
0987 /**
0988 * A hashtable enumerator class. This class implements both the
0989 * Enumeration and Iterator interfaces, but individual instances
0990 * can be created with the Iterator methods disabled. This is necessary
0991 * to avoid unintentionally increasing the capabilities granted a user
0992 * by passing an Enumeration.
0993 */
0994 private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
0995 Entry[] table = Hashtable.this .table;
0996 int index = table.length;
0997 Entry<K, V> entry = null;
0998 Entry<K, V> lastReturned = null;
0999 int type;
1000
1001 /**
1002 * Indicates whether this Enumerator is serving as an Iterator
1003 * or an Enumeration. (true -> Iterator).
1004 */
1005 boolean iterator;
1006
1007 /**
1008 * The modCount value that the iterator believes that the backing
1009 * Hashtable should have. If this expectation is violated, the iterator
1010 * has detected concurrent modification.
1011 */
1012 protected int expectedModCount = modCount;
1013
1014 Enumerator(int type, boolean iterator) {
1015 this .type = type;
1016 this .iterator = iterator;
1017 }
1018
1019 public boolean hasMoreElements() {
1020 Entry<K, V> e = entry;
1021 int i = index;
1022 Entry[] t = table;
1023 /* Use locals for faster loop iteration */
1024 while (e == null && i > 0) {
1025 e = t[--i];
1026 }
1027 entry = e;
1028 index = i;
1029 return e != null;
1030 }
1031
1032 public T nextElement() {
1033 Entry<K, V> et = entry;
1034 int i = index;
1035 Entry[] t = table;
1036 /* Use locals for faster loop iteration */
1037 while (et == null && i > 0) {
1038 et = t[--i];
1039 }
1040 entry = et;
1041 index = i;
1042 if (et != null) {
1043 Entry<K, V> e = lastReturned = entry;
1044 entry = e.next;
1045 return type == KEYS ? (T) e.key
1046 : (type == VALUES ? (T) e.value : (T) e);
1047 }
1048 throw new NoSuchElementException("Hashtable Enumerator");
1049 }
1050
1051 // Iterator methods
1052 public boolean hasNext() {
1053 return hasMoreElements();
1054 }
1055
1056 public T next() {
1057 if (modCount != expectedModCount)
1058 throw new ConcurrentModificationException();
1059 return nextElement();
1060 }
1061
1062 public void remove() {
1063 if (!iterator)
1064 throw new UnsupportedOperationException();
1065 if (lastReturned == null)
1066 throw new IllegalStateException("Hashtable Enumerator");
1067 if (modCount != expectedModCount)
1068 throw new ConcurrentModificationException();
1069
1070 synchronized (Hashtable.this ) {
1071 Entry[] tab = Hashtable.this .table;
1072 int index = (lastReturned.hash & 0x7FFFFFFF)
1073 % tab.length;
1074
1075 for (Entry<K, V> e = tab[index], prev = null; e != null; prev = e, e = e.next) {
1076 if (e == lastReturned) {
1077 modCount++;
1078 expectedModCount++;
1079 if (prev == null)
1080 tab[index] = e.next;
1081 else
1082 prev.next = e.next;
1083 count--;
1084 lastReturned = null;
1085 return;
1086 }
1087 }
1088 throw new ConcurrentModificationException();
1089 }
1090 }
1091 }
1092 }
|