0001 /*
0002 * Copyright 1997-2007 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 * Hash table based implementation of the <tt>Map</tt> interface. This
0032 * implementation provides all of the optional map operations, and permits
0033 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
0034 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
0035 * unsynchronized and permits nulls.) This class makes no guarantees as to
0036 * the order of the map; in particular, it does not guarantee that the order
0037 * will remain constant over time.
0038 *
0039 * <p>This implementation provides constant-time performance for the basic
0040 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
0041 * disperses the elements properly among the buckets. Iteration over
0042 * collection views requires time proportional to the "capacity" of the
0043 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
0044 * of key-value mappings). Thus, it's very important not to set the initial
0045 * capacity too high (or the load factor too low) if iteration performance is
0046 * important.
0047 *
0048 * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
0049 * performance: <i>initial capacity</i> and <i>load factor</i>. The
0050 * <i>capacity</i> is the number of buckets in the hash table, and the initial
0051 * capacity is simply the capacity at the time the hash table is created. The
0052 * <i>load factor</i> is a measure of how full the hash table is allowed to
0053 * get before its capacity is automatically increased. When the number of
0054 * entries in the hash table exceeds the product of the load factor and the
0055 * current capacity, the hash table is <i>rehashed</i> (that is, internal data
0056 * structures are rebuilt) so that the hash table has approximately twice the
0057 * number of buckets.
0058 *
0059 * <p>As a general rule, the default load factor (.75) offers a good tradeoff
0060 * between time and space costs. Higher values decrease the space overhead
0061 * but increase the lookup cost (reflected in most of the operations of the
0062 * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The
0063 * expected number of entries in the map and its load factor should be taken
0064 * into account when setting its initial capacity, so as to minimize the
0065 * number of rehash operations. If the initial capacity is greater
0066 * than the maximum number of entries divided by the load factor, no
0067 * rehash operations will ever occur.
0068 *
0069 * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
0070 * creating it with a sufficiently large capacity will allow the mappings to
0071 * be stored more efficiently than letting it perform automatic rehashing as
0072 * needed to grow the table.
0073 *
0074 * <p><strong>Note that this implementation is not synchronized.</strong>
0075 * If multiple threads access a hash map concurrently, and at least one of
0076 * the threads modifies the map structurally, it <i>must</i> be
0077 * synchronized externally. (A structural modification is any operation
0078 * that adds or deletes one or more mappings; merely changing the value
0079 * associated with a key that an instance already contains is not a
0080 * structural modification.) This is typically accomplished by
0081 * synchronizing on some object that naturally encapsulates the map.
0082 *
0083 * If no such object exists, the map should be "wrapped" using the
0084 * {@link Collections#synchronizedMap Collections.synchronizedMap}
0085 * method. This is best done at creation time, to prevent accidental
0086 * unsynchronized access to the map:<pre>
0087 * Map m = Collections.synchronizedMap(new HashMap(...));</pre>
0088 *
0089 * <p>The iterators returned by all of this class's "collection view methods"
0090 * are <i>fail-fast</i>: if the map is structurally modified at any time after
0091 * the iterator is created, in any way except through the iterator's own
0092 * <tt>remove</tt> method, the iterator will throw a
0093 * {@link ConcurrentModificationException}. Thus, in the face of concurrent
0094 * modification, the iterator fails quickly and cleanly, rather than risking
0095 * arbitrary, non-deterministic behavior at an undetermined time in the
0096 * future.
0097 *
0098 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
0099 * as it is, generally speaking, impossible to make any hard guarantees in the
0100 * presence of unsynchronized concurrent modification. Fail-fast iterators
0101 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
0102 * Therefore, it would be wrong to write a program that depended on this
0103 * exception for its correctness: <i>the fail-fast behavior of iterators
0104 * should be used only to detect bugs.</i>
0105 *
0106 * <p>This class is a member of the
0107 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
0108 * Java Collections Framework</a>.
0109 *
0110 * @param <K> the type of keys maintained by this map
0111 * @param <V> the type of mapped values
0112 *
0113 * @author Doug Lea
0114 * @author Josh Bloch
0115 * @author Arthur van Hoff
0116 * @author Neal Gafter
0117 * @version 1.79, 05/05/07
0118 * @see Object#hashCode()
0119 * @see Collection
0120 * @see Map
0121 * @see TreeMap
0122 * @see Hashtable
0123 * @since 1.2
0124 */
0125
0126 public class HashMap<K, V> extends AbstractMap<K, V> implements
0127 Map<K, V>, Cloneable, Serializable {
0128
0129 /**
0130 * The default initial capacity - MUST be a power of two.
0131 */
0132 static final int DEFAULT_INITIAL_CAPACITY = 16;
0133
0134 /**
0135 * The maximum capacity, used if a higher value is implicitly specified
0136 * by either of the constructors with arguments.
0137 * MUST be a power of two <= 1<<30.
0138 */
0139 static final int MAXIMUM_CAPACITY = 1 << 30;
0140
0141 /**
0142 * The load factor used when none specified in constructor.
0143 */
0144 static final float DEFAULT_LOAD_FACTOR = 0.75f;
0145
0146 /**
0147 * The table, resized as necessary. Length MUST Always be a power of two.
0148 */
0149 transient Entry[] table;
0150
0151 /**
0152 * The number of key-value mappings contained in this map.
0153 */
0154 transient int size;
0155
0156 /**
0157 * The next size value at which to resize (capacity * load factor).
0158 * @serial
0159 */
0160 int threshold;
0161
0162 /**
0163 * The load factor for the hash table.
0164 *
0165 * @serial
0166 */
0167 final float loadFactor;
0168
0169 /**
0170 * The number of times this HashMap has been structurally modified
0171 * Structural modifications are those that change the number of mappings in
0172 * the HashMap or otherwise modify its internal structure (e.g.,
0173 * rehash). This field is used to make iterators on Collection-views of
0174 * the HashMap fail-fast. (See ConcurrentModificationException).
0175 */
0176 transient volatile int modCount;
0177
0178 /**
0179 * Constructs an empty <tt>HashMap</tt> with the specified initial
0180 * capacity and load factor.
0181 *
0182 * @param initialCapacity the initial capacity
0183 * @param loadFactor the load factor
0184 * @throws IllegalArgumentException if the initial capacity is negative
0185 * or the load factor is nonpositive
0186 */
0187 public HashMap(int initialCapacity, float loadFactor) {
0188 if (initialCapacity < 0)
0189 throw new IllegalArgumentException(
0190 "Illegal initial capacity: " + initialCapacity);
0191 if (initialCapacity > MAXIMUM_CAPACITY)
0192 initialCapacity = MAXIMUM_CAPACITY;
0193 if (loadFactor <= 0 || Float.isNaN(loadFactor))
0194 throw new IllegalArgumentException("Illegal load factor: "
0195 + loadFactor);
0196
0197 // Find a power of 2 >= initialCapacity
0198 int capacity = 1;
0199 while (capacity < initialCapacity)
0200 capacity <<= 1;
0201
0202 this .loadFactor = loadFactor;
0203 threshold = (int) (capacity * loadFactor);
0204 table = new Entry[capacity];
0205 init();
0206 }
0207
0208 /**
0209 * Constructs an empty <tt>HashMap</tt> with the specified initial
0210 * capacity and the default load factor (0.75).
0211 *
0212 * @param initialCapacity the initial capacity.
0213 * @throws IllegalArgumentException if the initial capacity is negative.
0214 */
0215 public HashMap(int initialCapacity) {
0216 this (initialCapacity, DEFAULT_LOAD_FACTOR);
0217 }
0218
0219 /**
0220 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
0221 * (16) and the default load factor (0.75).
0222 */
0223 public HashMap() {
0224 this .loadFactor = DEFAULT_LOAD_FACTOR;
0225 threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
0226 table = new Entry[DEFAULT_INITIAL_CAPACITY];
0227 init();
0228 }
0229
0230 /**
0231 * Constructs a new <tt>HashMap</tt> with the same mappings as the
0232 * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
0233 * default load factor (0.75) and an initial capacity sufficient to
0234 * hold the mappings in the specified <tt>Map</tt>.
0235 *
0236 * @param m the map whose mappings are to be placed in this map
0237 * @throws NullPointerException if the specified map is null
0238 */
0239 public HashMap(Map<? extends K, ? extends V> m) {
0240 this (Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
0241 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
0242 putAllForCreate(m);
0243 }
0244
0245 // internal utilities
0246
0247 /**
0248 * Initialization hook for subclasses. This method is called
0249 * in all constructors and pseudo-constructors (clone, readObject)
0250 * after HashMap has been initialized but before any entries have
0251 * been inserted. (In the absence of this method, readObject would
0252 * require explicit knowledge of subclasses.)
0253 */
0254 void init() {
0255 }
0256
0257 /**
0258 * Applies a supplemental hash function to a given hashCode, which
0259 * defends against poor quality hash functions. This is critical
0260 * because HashMap uses power-of-two length hash tables, that
0261 * otherwise encounter collisions for hashCodes that do not differ
0262 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
0263 */
0264 static int hash(int h) {
0265 // This function ensures that hashCodes that differ only by
0266 // constant multiples at each bit position have a bounded
0267 // number of collisions (approximately 8 at default load factor).
0268 h ^= (h >>> 20) ^ (h >>> 12);
0269 return h ^ (h >>> 7) ^ (h >>> 4);
0270 }
0271
0272 /**
0273 * Returns index for hash code h.
0274 */
0275 static int indexFor(int h, int length) {
0276 return h & (length - 1);
0277 }
0278
0279 /**
0280 * Returns the number of key-value mappings in this map.
0281 *
0282 * @return the number of key-value mappings in this map
0283 */
0284 public int size() {
0285 return size;
0286 }
0287
0288 /**
0289 * Returns <tt>true</tt> if this map contains no key-value mappings.
0290 *
0291 * @return <tt>true</tt> if this map contains no key-value mappings
0292 */
0293 public boolean isEmpty() {
0294 return size == 0;
0295 }
0296
0297 /**
0298 * Returns the value to which the specified key is mapped,
0299 * or {@code null} if this map contains no mapping for the key.
0300 *
0301 * <p>More formally, if this map contains a mapping from a key
0302 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
0303 * key.equals(k))}, then this method returns {@code v}; otherwise
0304 * it returns {@code null}. (There can be at most one such mapping.)
0305 *
0306 * <p>A return value of {@code null} does not <i>necessarily</i>
0307 * indicate that the map contains no mapping for the key; it's also
0308 * possible that the map explicitly maps the key to {@code null}.
0309 * The {@link #containsKey containsKey} operation may be used to
0310 * distinguish these two cases.
0311 *
0312 * @see #put(Object, Object)
0313 */
0314 public V get(Object key) {
0315 if (key == null)
0316 return getForNullKey();
0317 int hash = hash(key.hashCode());
0318 for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
0319 Object k;
0320 if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
0321 return e.value;
0322 }
0323 return null;
0324 }
0325
0326 /**
0327 * Offloaded version of get() to look up null keys. Null keys map
0328 * to index 0. This null case is split out into separate methods
0329 * for the sake of performance in the two most commonly used
0330 * operations (get and put), but incorporated with conditionals in
0331 * others.
0332 */
0333 private V getForNullKey() {
0334 for (Entry<K, V> e = table[0]; e != null; e = e.next) {
0335 if (e.key == null)
0336 return e.value;
0337 }
0338 return null;
0339 }
0340
0341 /**
0342 * Returns <tt>true</tt> if this map contains a mapping for the
0343 * specified key.
0344 *
0345 * @param key The key whose presence in this map is to be tested
0346 * @return <tt>true</tt> if this map contains a mapping for the specified
0347 * key.
0348 */
0349 public boolean containsKey(Object key) {
0350 return getEntry(key) != null;
0351 }
0352
0353 /**
0354 * Returns the entry associated with the specified key in the
0355 * HashMap. Returns null if the HashMap contains no mapping
0356 * for the key.
0357 */
0358 final Entry<K, V> getEntry(Object key) {
0359 int hash = (key == null) ? 0 : hash(key.hashCode());
0360 for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
0361 Object k;
0362 if (e.hash == hash
0363 && ((k = e.key) == key || (key != null && key
0364 .equals(k))))
0365 return e;
0366 }
0367 return null;
0368 }
0369
0370 /**
0371 * Associates the specified value with the specified key in this map.
0372 * If the map previously contained a mapping for the key, the old
0373 * value is replaced.
0374 *
0375 * @param key key with which the specified value is to be associated
0376 * @param value value to be associated with the specified key
0377 * @return the previous value associated with <tt>key</tt>, or
0378 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
0379 * (A <tt>null</tt> return can also indicate that the map
0380 * previously associated <tt>null</tt> with <tt>key</tt>.)
0381 */
0382 public V put(K key, V value) {
0383 if (key == null)
0384 return putForNullKey(value);
0385 int hash = hash(key.hashCode());
0386 int i = indexFor(hash, table.length);
0387 for (Entry<K, V> e = table[i]; e != null; e = e.next) {
0388 Object k;
0389 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
0390 V oldValue = e.value;
0391 e.value = value;
0392 e.recordAccess(this );
0393 return oldValue;
0394 }
0395 }
0396
0397 modCount++;
0398 addEntry(hash, key, value, i);
0399 return null;
0400 }
0401
0402 /**
0403 * Offloaded version of put for null keys
0404 */
0405 private V putForNullKey(V value) {
0406 for (Entry<K, V> e = table[0]; e != null; e = e.next) {
0407 if (e.key == null) {
0408 V oldValue = e.value;
0409 e.value = value;
0410 e.recordAccess(this );
0411 return oldValue;
0412 }
0413 }
0414 modCount++;
0415 addEntry(0, null, value, 0);
0416 return null;
0417 }
0418
0419 /**
0420 * This method is used instead of put by constructors and
0421 * pseudoconstructors (clone, readObject). It does not resize the table,
0422 * check for comodification, etc. It calls createEntry rather than
0423 * addEntry.
0424 */
0425 private void putForCreate(K key, V value) {
0426 int hash = (key == null) ? 0 : hash(key.hashCode());
0427 int i = indexFor(hash, table.length);
0428
0429 /**
0430 * Look for preexisting entry for key. This will never happen for
0431 * clone or deserialize. It will only happen for construction if the
0432 * input Map is a sorted map whose ordering is inconsistent w/ equals.
0433 */
0434 for (Entry<K, V> e = table[i]; e != null; e = e.next) {
0435 Object k;
0436 if (e.hash == hash
0437 && ((k = e.key) == key || (key != null && key
0438 .equals(k)))) {
0439 e.value = value;
0440 return;
0441 }
0442 }
0443
0444 createEntry(hash, key, value, i);
0445 }
0446
0447 private void putAllForCreate(Map<? extends K, ? extends V> m) {
0448 for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m
0449 .entrySet().iterator(); i.hasNext();) {
0450 Map.Entry<? extends K, ? extends V> e = i.next();
0451 putForCreate(e.getKey(), e.getValue());
0452 }
0453 }
0454
0455 /**
0456 * Rehashes the contents of this map into a new array with a
0457 * larger capacity. This method is called automatically when the
0458 * number of keys in this map reaches its threshold.
0459 *
0460 * If current capacity is MAXIMUM_CAPACITY, this method does not
0461 * resize the map, but sets threshold to Integer.MAX_VALUE.
0462 * This has the effect of preventing future calls.
0463 *
0464 * @param newCapacity the new capacity, MUST be a power of two;
0465 * must be greater than current capacity unless current
0466 * capacity is MAXIMUM_CAPACITY (in which case value
0467 * is irrelevant).
0468 */
0469 void resize(int newCapacity) {
0470 Entry[] oldTable = table;
0471 int oldCapacity = oldTable.length;
0472 if (oldCapacity == MAXIMUM_CAPACITY) {
0473 threshold = Integer.MAX_VALUE;
0474 return;
0475 }
0476
0477 Entry[] newTable = new Entry[newCapacity];
0478 transfer(newTable);
0479 table = newTable;
0480 threshold = (int) (newCapacity * loadFactor);
0481 }
0482
0483 /**
0484 * Transfers all entries from current table to newTable.
0485 */
0486 void transfer(Entry[] newTable) {
0487 Entry[] src = table;
0488 int newCapacity = newTable.length;
0489 for (int j = 0; j < src.length; j++) {
0490 Entry<K, V> e = src[j];
0491 if (e != null) {
0492 src[j] = null;
0493 do {
0494 Entry<K, V> next = e.next;
0495 int i = indexFor(e.hash, newCapacity);
0496 e.next = newTable[i];
0497 newTable[i] = e;
0498 e = next;
0499 } while (e != null);
0500 }
0501 }
0502 }
0503
0504 /**
0505 * Copies all of the mappings from the specified map to this map.
0506 * These mappings will replace any mappings that this map had for
0507 * any of the keys currently in the specified map.
0508 *
0509 * @param m mappings to be stored in this map
0510 * @throws NullPointerException if the specified map is null
0511 */
0512 public void putAll(Map<? extends K, ? extends V> m) {
0513 int numKeysToBeAdded = m.size();
0514 if (numKeysToBeAdded == 0)
0515 return;
0516
0517 /*
0518 * Expand the map if the map if the number of mappings to be added
0519 * is greater than or equal to threshold. This is conservative; the
0520 * obvious condition is (m.size() + size) >= threshold, but this
0521 * condition could result in a map with twice the appropriate capacity,
0522 * if the keys to be added overlap with the keys already in this map.
0523 * By using the conservative calculation, we subject ourself
0524 * to at most one extra resize.
0525 */
0526 if (numKeysToBeAdded > threshold) {
0527 int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1);
0528 if (targetCapacity > MAXIMUM_CAPACITY)
0529 targetCapacity = MAXIMUM_CAPACITY;
0530 int newCapacity = table.length;
0531 while (newCapacity < targetCapacity)
0532 newCapacity <<= 1;
0533 if (newCapacity > table.length)
0534 resize(newCapacity);
0535 }
0536
0537 for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m
0538 .entrySet().iterator(); i.hasNext();) {
0539 Map.Entry<? extends K, ? extends V> e = i.next();
0540 put(e.getKey(), e.getValue());
0541 }
0542 }
0543
0544 /**
0545 * Removes the mapping for the specified key from this map if present.
0546 *
0547 * @param key key whose mapping is to be removed from the map
0548 * @return the previous value associated with <tt>key</tt>, or
0549 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
0550 * (A <tt>null</tt> return can also indicate that the map
0551 * previously associated <tt>null</tt> with <tt>key</tt>.)
0552 */
0553 public V remove(Object key) {
0554 Entry<K, V> e = removeEntryForKey(key);
0555 return (e == null ? null : e.value);
0556 }
0557
0558 /**
0559 * Removes and returns the entry associated with the specified key
0560 * in the HashMap. Returns null if the HashMap contains no mapping
0561 * for this key.
0562 */
0563 final Entry<K, V> removeEntryForKey(Object key) {
0564 int hash = (key == null) ? 0 : hash(key.hashCode());
0565 int i = indexFor(hash, table.length);
0566 Entry<K, V> prev = table[i];
0567 Entry<K, V> e = prev;
0568
0569 while (e != null) {
0570 Entry<K, V> next = e.next;
0571 Object k;
0572 if (e.hash == hash
0573 && ((k = e.key) == key || (key != null && key
0574 .equals(k)))) {
0575 modCount++;
0576 size--;
0577 if (prev == e)
0578 table[i] = next;
0579 else
0580 prev.next = next;
0581 e.recordRemoval(this );
0582 return e;
0583 }
0584 prev = e;
0585 e = next;
0586 }
0587
0588 return e;
0589 }
0590
0591 /**
0592 * Special version of remove for EntrySet.
0593 */
0594 final Entry<K, V> removeMapping(Object o) {
0595 if (!(o instanceof Map.Entry))
0596 return null;
0597
0598 Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
0599 Object key = entry.getKey();
0600 int hash = (key == null) ? 0 : hash(key.hashCode());
0601 int i = indexFor(hash, table.length);
0602 Entry<K, V> prev = table[i];
0603 Entry<K, V> e = prev;
0604
0605 while (e != null) {
0606 Entry<K, V> next = e.next;
0607 if (e.hash == hash && e.equals(entry)) {
0608 modCount++;
0609 size--;
0610 if (prev == e)
0611 table[i] = next;
0612 else
0613 prev.next = next;
0614 e.recordRemoval(this );
0615 return e;
0616 }
0617 prev = e;
0618 e = next;
0619 }
0620
0621 return e;
0622 }
0623
0624 /**
0625 * Removes all of the mappings from this map.
0626 * The map will be empty after this call returns.
0627 */
0628 public void clear() {
0629 modCount++;
0630 Entry[] tab = table;
0631 for (int i = 0; i < tab.length; i++)
0632 tab[i] = null;
0633 size = 0;
0634 }
0635
0636 /**
0637 * Returns <tt>true</tt> if this map maps one or more keys to the
0638 * specified value.
0639 *
0640 * @param value value whose presence in this map is to be tested
0641 * @return <tt>true</tt> if this map maps one or more keys to the
0642 * specified value
0643 */
0644 public boolean containsValue(Object value) {
0645 if (value == null)
0646 return containsNullValue();
0647
0648 Entry[] tab = table;
0649 for (int i = 0; i < tab.length; i++)
0650 for (Entry e = tab[i]; e != null; e = e.next)
0651 if (value.equals(e.value))
0652 return true;
0653 return false;
0654 }
0655
0656 /**
0657 * Special-case code for containsValue with null argument
0658 */
0659 private boolean containsNullValue() {
0660 Entry[] tab = table;
0661 for (int i = 0; i < tab.length; i++)
0662 for (Entry e = tab[i]; e != null; e = e.next)
0663 if (e.value == null)
0664 return true;
0665 return false;
0666 }
0667
0668 /**
0669 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
0670 * values themselves are not cloned.
0671 *
0672 * @return a shallow copy of this map
0673 */
0674 public Object clone() {
0675 HashMap<K, V> result = null;
0676 try {
0677 result = (HashMap<K, V>) super .clone();
0678 } catch (CloneNotSupportedException e) {
0679 // assert false;
0680 }
0681 result.table = new Entry[table.length];
0682 result.entrySet = null;
0683 result.modCount = 0;
0684 result.size = 0;
0685 result.init();
0686 result.putAllForCreate(this );
0687
0688 return result;
0689 }
0690
0691 static class Entry<K, V> implements Map.Entry<K, V> {
0692 final K key;
0693 V value;
0694 Entry<K, V> next;
0695 final int hash;
0696
0697 /**
0698 * Creates new entry.
0699 */
0700 Entry(int h, K k, V v, Entry<K, V> n) {
0701 value = v;
0702 next = n;
0703 key = k;
0704 hash = h;
0705 }
0706
0707 public final K getKey() {
0708 return key;
0709 }
0710
0711 public final V getValue() {
0712 return value;
0713 }
0714
0715 public final V setValue(V newValue) {
0716 V oldValue = value;
0717 value = newValue;
0718 return oldValue;
0719 }
0720
0721 public final boolean equals(Object o) {
0722 if (!(o instanceof Map.Entry))
0723 return false;
0724 Map.Entry e = (Map.Entry) o;
0725 Object k1 = getKey();
0726 Object k2 = e.getKey();
0727 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
0728 Object v1 = getValue();
0729 Object v2 = e.getValue();
0730 if (v1 == v2 || (v1 != null && v1.equals(v2)))
0731 return true;
0732 }
0733 return false;
0734 }
0735
0736 public final int hashCode() {
0737 return (key == null ? 0 : key.hashCode())
0738 ^ (value == null ? 0 : value.hashCode());
0739 }
0740
0741 public final String toString() {
0742 return getKey() + "=" + getValue();
0743 }
0744
0745 /**
0746 * This method is invoked whenever the value in an entry is
0747 * overwritten by an invocation of put(k,v) for a key k that's already
0748 * in the HashMap.
0749 */
0750 void recordAccess(HashMap<K, V> m) {
0751 }
0752
0753 /**
0754 * This method is invoked whenever the entry is
0755 * removed from the table.
0756 */
0757 void recordRemoval(HashMap<K, V> m) {
0758 }
0759 }
0760
0761 /**
0762 * Adds a new entry with the specified key, value and hash code to
0763 * the specified bucket. It is the responsibility of this
0764 * method to resize the table if appropriate.
0765 *
0766 * Subclass overrides this to alter the behavior of put method.
0767 */
0768 void addEntry(int hash, K key, V value, int bucketIndex) {
0769 Entry<K, V> e = table[bucketIndex];
0770 table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
0771 if (size++ >= threshold)
0772 resize(2 * table.length);
0773 }
0774
0775 /**
0776 * Like addEntry except that this version is used when creating entries
0777 * as part of Map construction or "pseudo-construction" (cloning,
0778 * deserialization). This version needn't worry about resizing the table.
0779 *
0780 * Subclass overrides this to alter the behavior of HashMap(Map),
0781 * clone, and readObject.
0782 */
0783 void createEntry(int hash, K key, V value, int bucketIndex) {
0784 Entry<K, V> e = table[bucketIndex];
0785 table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
0786 size++;
0787 }
0788
0789 private abstract class HashIterator<E> implements Iterator<E> {
0790 Entry<K, V> next; // next entry to return
0791 int expectedModCount; // For fast-fail
0792 int index; // current slot
0793 Entry<K, V> current; // current entry
0794
0795 HashIterator() {
0796 expectedModCount = modCount;
0797 if (size > 0) { // advance to first entry
0798 Entry[] t = table;
0799 while (index < t.length && (next = t[index++]) == null)
0800 ;
0801 }
0802 }
0803
0804 public final boolean hasNext() {
0805 return next != null;
0806 }
0807
0808 final Entry<K, V> nextEntry() {
0809 if (modCount != expectedModCount)
0810 throw new ConcurrentModificationException();
0811 Entry<K, V> e = next;
0812 if (e == null)
0813 throw new NoSuchElementException();
0814
0815 if ((next = e.next) == null) {
0816 Entry[] t = table;
0817 while (index < t.length && (next = t[index++]) == null)
0818 ;
0819 }
0820 current = e;
0821 return e;
0822 }
0823
0824 public void remove() {
0825 if (current == null)
0826 throw new IllegalStateException();
0827 if (modCount != expectedModCount)
0828 throw new ConcurrentModificationException();
0829 Object k = current.key;
0830 current = null;
0831 HashMap.this .removeEntryForKey(k);
0832 expectedModCount = modCount;
0833 }
0834
0835 }
0836
0837 private final class ValueIterator extends HashIterator<V> {
0838 public V next() {
0839 return nextEntry().value;
0840 }
0841 }
0842
0843 private final class KeyIterator extends HashIterator<K> {
0844 public K next() {
0845 return nextEntry().getKey();
0846 }
0847 }
0848
0849 private final class EntryIterator extends
0850 HashIterator<Map.Entry<K, V>> {
0851 public Map.Entry<K, V> next() {
0852 return nextEntry();
0853 }
0854 }
0855
0856 // Subclass overrides these to alter behavior of views' iterator() method
0857 Iterator<K> newKeyIterator() {
0858 return new KeyIterator();
0859 }
0860
0861 Iterator<V> newValueIterator() {
0862 return new ValueIterator();
0863 }
0864
0865 Iterator<Map.Entry<K, V>> newEntryIterator() {
0866 return new EntryIterator();
0867 }
0868
0869 // Views
0870
0871 private transient Set<Map.Entry<K, V>> entrySet = null;
0872
0873 /**
0874 * Returns a {@link Set} view of the keys contained in this map.
0875 * The set is backed by the map, so changes to the map are
0876 * reflected in the set, and vice-versa. If the map is modified
0877 * while an iteration over the set is in progress (except through
0878 * the iterator's own <tt>remove</tt> operation), the results of
0879 * the iteration are undefined. The set supports element removal,
0880 * which removes the corresponding mapping from the map, via the
0881 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
0882 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
0883 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
0884 * operations.
0885 */
0886 public Set<K> keySet() {
0887 Set<K> ks = keySet;
0888 return (ks != null ? ks : (keySet = new KeySet()));
0889 }
0890
0891 private final class KeySet extends AbstractSet<K> {
0892 public Iterator<K> iterator() {
0893 return newKeyIterator();
0894 }
0895
0896 public int size() {
0897 return size;
0898 }
0899
0900 public boolean contains(Object o) {
0901 return containsKey(o);
0902 }
0903
0904 public boolean remove(Object o) {
0905 return HashMap.this .removeEntryForKey(o) != null;
0906 }
0907
0908 public void clear() {
0909 HashMap.this .clear();
0910 }
0911 }
0912
0913 /**
0914 * Returns a {@link Collection} view of the values contained in this map.
0915 * The collection is backed by the map, so changes to the map are
0916 * reflected in the collection, and vice-versa. If the map is
0917 * modified while an iteration over the collection is in progress
0918 * (except through the iterator's own <tt>remove</tt> operation),
0919 * the results of the iteration are undefined. The collection
0920 * supports element removal, which removes the corresponding
0921 * mapping from the map, via the <tt>Iterator.remove</tt>,
0922 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
0923 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
0924 * support the <tt>add</tt> or <tt>addAll</tt> operations.
0925 */
0926 public Collection<V> values() {
0927 Collection<V> vs = values;
0928 return (vs != null ? vs : (values = new Values()));
0929 }
0930
0931 private final class Values extends AbstractCollection<V> {
0932 public Iterator<V> iterator() {
0933 return newValueIterator();
0934 }
0935
0936 public int size() {
0937 return size;
0938 }
0939
0940 public boolean contains(Object o) {
0941 return containsValue(o);
0942 }
0943
0944 public void clear() {
0945 HashMap.this .clear();
0946 }
0947 }
0948
0949 /**
0950 * Returns a {@link Set} view of the mappings contained in this map.
0951 * The set is backed by the map, so changes to the map are
0952 * reflected in the set, and vice-versa. If the map is modified
0953 * while an iteration over the set is in progress (except through
0954 * the iterator's own <tt>remove</tt> operation, or through the
0955 * <tt>setValue</tt> operation on a map entry returned by the
0956 * iterator) the results of the iteration are undefined. The set
0957 * supports element removal, which removes the corresponding
0958 * mapping from the map, via the <tt>Iterator.remove</tt>,
0959 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
0960 * <tt>clear</tt> operations. It does not support the
0961 * <tt>add</tt> or <tt>addAll</tt> operations.
0962 *
0963 * @return a set view of the mappings contained in this map
0964 */
0965 public Set<Map.Entry<K, V>> entrySet() {
0966 return entrySet0();
0967 }
0968
0969 private Set<Map.Entry<K, V>> entrySet0() {
0970 Set<Map.Entry<K, V>> es = entrySet;
0971 return es != null ? es : (entrySet = new EntrySet());
0972 }
0973
0974 private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
0975 public Iterator<Map.Entry<K, V>> iterator() {
0976 return newEntryIterator();
0977 }
0978
0979 public boolean contains(Object o) {
0980 if (!(o instanceof Map.Entry))
0981 return false;
0982 Map.Entry<K, V> e = (Map.Entry<K, V>) o;
0983 Entry<K, V> candidate = getEntry(e.getKey());
0984 return candidate != null && candidate.equals(e);
0985 }
0986
0987 public boolean remove(Object o) {
0988 return removeMapping(o) != null;
0989 }
0990
0991 public int size() {
0992 return size;
0993 }
0994
0995 public void clear() {
0996 HashMap.this .clear();
0997 }
0998 }
0999
1000 /**
1001 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
1002 * serialize it).
1003 *
1004 * @serialData The <i>capacity</i> of the HashMap (the length of the
1005 * bucket array) is emitted (int), followed by the
1006 * <i>size</i> (an int, the number of key-value
1007 * mappings), followed by the key (Object) and value (Object)
1008 * for each key-value mapping. The key-value mappings are
1009 * emitted in no particular order.
1010 */
1011 private void writeObject(java.io.ObjectOutputStream s)
1012 throws IOException {
1013 Iterator<Map.Entry<K, V>> i = (size > 0) ? entrySet0()
1014 .iterator() : null;
1015
1016 // Write out the threshold, loadfactor, and any hidden stuff
1017 s.defaultWriteObject();
1018
1019 // Write out number of buckets
1020 s.writeInt(table.length);
1021
1022 // Write out size (number of Mappings)
1023 s.writeInt(size);
1024
1025 // Write out keys and values (alternating)
1026 if (i != null) {
1027 while (i.hasNext()) {
1028 Map.Entry<K, V> e = i.next();
1029 s.writeObject(e.getKey());
1030 s.writeObject(e.getValue());
1031 }
1032 }
1033 }
1034
1035 private static final long serialVersionUID = 362498820763181265L;
1036
1037 /**
1038 * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
1039 * deserialize it).
1040 */
1041 private void readObject(java.io.ObjectInputStream s)
1042 throws IOException, ClassNotFoundException {
1043 // Read in the threshold, loadfactor, and any hidden stuff
1044 s.defaultReadObject();
1045
1046 // Read in number of buckets and allocate the bucket array;
1047 int numBuckets = s.readInt();
1048 table = new Entry[numBuckets];
1049
1050 init(); // Give subclass a chance to do its thing.
1051
1052 // Read in size (number of Mappings)
1053 int size = s.readInt();
1054
1055 // Read the keys and values, and put the mappings in the HashMap
1056 for (int i = 0; i < size; i++) {
1057 K key = (K) s.readObject();
1058 V value = (V) s.readObject();
1059 putForCreate(key, value);
1060 }
1061 }
1062
1063 // These methods are used when serializing HashSets
1064 int capacity() {
1065 return table.length;
1066 }
1067
1068 float loadFactor() {
1069 return loadFactor;
1070 }
1071 }
|