1.1 --- a/emul/compact/src/main/java/java/util/HashMap.java Tue Feb 26 14:55:55 2013 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,990 +0,0 @@
1.4 -/*
1.5 - * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
1.6 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 - *
1.8 - * This code is free software; you can redistribute it and/or modify it
1.9 - * under the terms of the GNU General Public License version 2 only, as
1.10 - * published by the Free Software Foundation. Oracle designates this
1.11 - * particular file as subject to the "Classpath" exception as provided
1.12 - * by Oracle in the LICENSE file that accompanied this code.
1.13 - *
1.14 - * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 - * version 2 for more details (a copy is included in the LICENSE file that
1.18 - * accompanied this code).
1.19 - *
1.20 - * You should have received a copy of the GNU General Public License version
1.21 - * 2 along with this work; if not, write to the Free Software Foundation,
1.22 - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 - *
1.24 - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 - * or visit www.oracle.com if you need additional information or have any
1.26 - * questions.
1.27 - */
1.28 -
1.29 -package java.util;
1.30 -import java.io.*;
1.31 -
1.32 -/**
1.33 - * Hash table based implementation of the <tt>Map</tt> interface. This
1.34 - * implementation provides all of the optional map operations, and permits
1.35 - * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
1.36 - * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
1.37 - * unsynchronized and permits nulls.) This class makes no guarantees as to
1.38 - * the order of the map; in particular, it does not guarantee that the order
1.39 - * will remain constant over time.
1.40 - *
1.41 - * <p>This implementation provides constant-time performance for the basic
1.42 - * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
1.43 - * disperses the elements properly among the buckets. Iteration over
1.44 - * collection views requires time proportional to the "capacity" of the
1.45 - * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
1.46 - * of key-value mappings). Thus, it's very important not to set the initial
1.47 - * capacity too high (or the load factor too low) if iteration performance is
1.48 - * important.
1.49 - *
1.50 - * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
1.51 - * performance: <i>initial capacity</i> and <i>load factor</i>. The
1.52 - * <i>capacity</i> is the number of buckets in the hash table, and the initial
1.53 - * capacity is simply the capacity at the time the hash table is created. The
1.54 - * <i>load factor</i> is a measure of how full the hash table is allowed to
1.55 - * get before its capacity is automatically increased. When the number of
1.56 - * entries in the hash table exceeds the product of the load factor and the
1.57 - * current capacity, the hash table is <i>rehashed</i> (that is, internal data
1.58 - * structures are rebuilt) so that the hash table has approximately twice the
1.59 - * number of buckets.
1.60 - *
1.61 - * <p>As a general rule, the default load factor (.75) offers a good tradeoff
1.62 - * between time and space costs. Higher values decrease the space overhead
1.63 - * but increase the lookup cost (reflected in most of the operations of the
1.64 - * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The
1.65 - * expected number of entries in the map and its load factor should be taken
1.66 - * into account when setting its initial capacity, so as to minimize the
1.67 - * number of rehash operations. If the initial capacity is greater
1.68 - * than the maximum number of entries divided by the load factor, no
1.69 - * rehash operations will ever occur.
1.70 - *
1.71 - * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
1.72 - * creating it with a sufficiently large capacity will allow the mappings to
1.73 - * be stored more efficiently than letting it perform automatic rehashing as
1.74 - * needed to grow the table.
1.75 - *
1.76 - * <p><strong>Note that this implementation is not synchronized.</strong>
1.77 - * If multiple threads access a hash map concurrently, and at least one of
1.78 - * the threads modifies the map structurally, it <i>must</i> be
1.79 - * synchronized externally. (A structural modification is any operation
1.80 - * that adds or deletes one or more mappings; merely changing the value
1.81 - * associated with a key that an instance already contains is not a
1.82 - * structural modification.) This is typically accomplished by
1.83 - * synchronizing on some object that naturally encapsulates the map.
1.84 - *
1.85 - * If no such object exists, the map should be "wrapped" using the
1.86 - * {@link Collections#synchronizedMap Collections.synchronizedMap}
1.87 - * method. This is best done at creation time, to prevent accidental
1.88 - * unsynchronized access to the map:<pre>
1.89 - * Map m = Collections.synchronizedMap(new HashMap(...));</pre>
1.90 - *
1.91 - * <p>The iterators returned by all of this class's "collection view methods"
1.92 - * are <i>fail-fast</i>: if the map is structurally modified at any time after
1.93 - * the iterator is created, in any way except through the iterator's own
1.94 - * <tt>remove</tt> method, the iterator will throw a
1.95 - * {@link ConcurrentModificationException}. Thus, in the face of concurrent
1.96 - * modification, the iterator fails quickly and cleanly, rather than risking
1.97 - * arbitrary, non-deterministic behavior at an undetermined time in the
1.98 - * future.
1.99 - *
1.100 - * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
1.101 - * as it is, generally speaking, impossible to make any hard guarantees in the
1.102 - * presence of unsynchronized concurrent modification. Fail-fast iterators
1.103 - * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
1.104 - * Therefore, it would be wrong to write a program that depended on this
1.105 - * exception for its correctness: <i>the fail-fast behavior of iterators
1.106 - * should be used only to detect bugs.</i>
1.107 - *
1.108 - * <p>This class is a member of the
1.109 - * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.110 - * Java Collections Framework</a>.
1.111 - *
1.112 - * @param <K> the type of keys maintained by this map
1.113 - * @param <V> the type of mapped values
1.114 - *
1.115 - * @author Doug Lea
1.116 - * @author Josh Bloch
1.117 - * @author Arthur van Hoff
1.118 - * @author Neal Gafter
1.119 - * @see Object#hashCode()
1.120 - * @see Collection
1.121 - * @see Map
1.122 - * @see TreeMap
1.123 - * @see Hashtable
1.124 - * @since 1.2
1.125 - */
1.126 -
1.127 -public class HashMap<K,V>
1.128 - extends AbstractMap<K,V>
1.129 - implements Map<K,V>, Cloneable, Serializable
1.130 -{
1.131 -
1.132 - /**
1.133 - * The default initial capacity - MUST be a power of two.
1.134 - */
1.135 - static final int DEFAULT_INITIAL_CAPACITY = 16;
1.136 -
1.137 - /**
1.138 - * The maximum capacity, used if a higher value is implicitly specified
1.139 - * by either of the constructors with arguments.
1.140 - * MUST be a power of two <= 1<<30.
1.141 - */
1.142 - static final int MAXIMUM_CAPACITY = 1 << 30;
1.143 -
1.144 - /**
1.145 - * The load factor used when none specified in constructor.
1.146 - */
1.147 - static final float DEFAULT_LOAD_FACTOR = 0.75f;
1.148 -
1.149 - /**
1.150 - * The table, resized as necessary. Length MUST Always be a power of two.
1.151 - */
1.152 - transient Entry[] table;
1.153 -
1.154 - /**
1.155 - * The number of key-value mappings contained in this map.
1.156 - */
1.157 - transient int size;
1.158 -
1.159 - /**
1.160 - * The next size value at which to resize (capacity * load factor).
1.161 - * @serial
1.162 - */
1.163 - int threshold;
1.164 -
1.165 - /**
1.166 - * The load factor for the hash table.
1.167 - *
1.168 - * @serial
1.169 - */
1.170 - final float loadFactor;
1.171 -
1.172 - /**
1.173 - * The number of times this HashMap has been structurally modified
1.174 - * Structural modifications are those that change the number of mappings in
1.175 - * the HashMap or otherwise modify its internal structure (e.g.,
1.176 - * rehash). This field is used to make iterators on Collection-views of
1.177 - * the HashMap fail-fast. (See ConcurrentModificationException).
1.178 - */
1.179 - transient int modCount;
1.180 -
1.181 - /**
1.182 - * Constructs an empty <tt>HashMap</tt> with the specified initial
1.183 - * capacity and load factor.
1.184 - *
1.185 - * @param initialCapacity the initial capacity
1.186 - * @param loadFactor the load factor
1.187 - * @throws IllegalArgumentException if the initial capacity is negative
1.188 - * or the load factor is nonpositive
1.189 - */
1.190 - public HashMap(int initialCapacity, float loadFactor) {
1.191 - if (initialCapacity < 0)
1.192 - throw new IllegalArgumentException("Illegal initial capacity: " +
1.193 - initialCapacity);
1.194 - if (initialCapacity > MAXIMUM_CAPACITY)
1.195 - initialCapacity = MAXIMUM_CAPACITY;
1.196 - if (loadFactor <= 0 || Float.isNaN(loadFactor))
1.197 - throw new IllegalArgumentException("Illegal load factor: " +
1.198 - loadFactor);
1.199 -
1.200 - // Find a power of 2 >= initialCapacity
1.201 - int capacity = 1;
1.202 - while (capacity < initialCapacity)
1.203 - capacity <<= 1;
1.204 -
1.205 - this.loadFactor = loadFactor;
1.206 - threshold = (int)(capacity * loadFactor);
1.207 - table = new Entry[capacity];
1.208 - init();
1.209 - }
1.210 -
1.211 - /**
1.212 - * Constructs an empty <tt>HashMap</tt> with the specified initial
1.213 - * capacity and the default load factor (0.75).
1.214 - *
1.215 - * @param initialCapacity the initial capacity.
1.216 - * @throws IllegalArgumentException if the initial capacity is negative.
1.217 - */
1.218 - public HashMap(int initialCapacity) {
1.219 - this(initialCapacity, DEFAULT_LOAD_FACTOR);
1.220 - }
1.221 -
1.222 - /**
1.223 - * Constructs an empty <tt>HashMap</tt> with the default initial capacity
1.224 - * (16) and the default load factor (0.75).
1.225 - */
1.226 - public HashMap() {
1.227 - this.loadFactor = DEFAULT_LOAD_FACTOR;
1.228 - threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
1.229 - table = new Entry[DEFAULT_INITIAL_CAPACITY];
1.230 - init();
1.231 - }
1.232 -
1.233 - /**
1.234 - * Constructs a new <tt>HashMap</tt> with the same mappings as the
1.235 - * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
1.236 - * default load factor (0.75) and an initial capacity sufficient to
1.237 - * hold the mappings in the specified <tt>Map</tt>.
1.238 - *
1.239 - * @param m the map whose mappings are to be placed in this map
1.240 - * @throws NullPointerException if the specified map is null
1.241 - */
1.242 - public HashMap(Map<? extends K, ? extends V> m) {
1.243 - this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
1.244 - DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
1.245 - putAllForCreate(m);
1.246 - }
1.247 -
1.248 - // internal utilities
1.249 -
1.250 - /**
1.251 - * Initialization hook for subclasses. This method is called
1.252 - * in all constructors and pseudo-constructors (clone, readObject)
1.253 - * after HashMap has been initialized but before any entries have
1.254 - * been inserted. (In the absence of this method, readObject would
1.255 - * require explicit knowledge of subclasses.)
1.256 - */
1.257 - void init() {
1.258 - }
1.259 -
1.260 - /**
1.261 - * Applies a supplemental hash function to a given hashCode, which
1.262 - * defends against poor quality hash functions. This is critical
1.263 - * because HashMap uses power-of-two length hash tables, that
1.264 - * otherwise encounter collisions for hashCodes that do not differ
1.265 - * in lower bits. Note: Null keys always map to hash 0, thus index 0.
1.266 - */
1.267 - static int hash(int h) {
1.268 - // This function ensures that hashCodes that differ only by
1.269 - // constant multiples at each bit position have a bounded
1.270 - // number of collisions (approximately 8 at default load factor).
1.271 - h ^= (h >>> 20) ^ (h >>> 12);
1.272 - return h ^ (h >>> 7) ^ (h >>> 4);
1.273 - }
1.274 -
1.275 - /**
1.276 - * Returns index for hash code h.
1.277 - */
1.278 - static int indexFor(int h, int length) {
1.279 - return h & (length-1);
1.280 - }
1.281 -
1.282 - /**
1.283 - * Returns the number of key-value mappings in this map.
1.284 - *
1.285 - * @return the number of key-value mappings in this map
1.286 - */
1.287 - public int size() {
1.288 - return size;
1.289 - }
1.290 -
1.291 - /**
1.292 - * Returns <tt>true</tt> if this map contains no key-value mappings.
1.293 - *
1.294 - * @return <tt>true</tt> if this map contains no key-value mappings
1.295 - */
1.296 - public boolean isEmpty() {
1.297 - return size == 0;
1.298 - }
1.299 -
1.300 - /**
1.301 - * Returns the value to which the specified key is mapped,
1.302 - * or {@code null} if this map contains no mapping for the key.
1.303 - *
1.304 - * <p>More formally, if this map contains a mapping from a key
1.305 - * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
1.306 - * key.equals(k))}, then this method returns {@code v}; otherwise
1.307 - * it returns {@code null}. (There can be at most one such mapping.)
1.308 - *
1.309 - * <p>A return value of {@code null} does not <i>necessarily</i>
1.310 - * indicate that the map contains no mapping for the key; it's also
1.311 - * possible that the map explicitly maps the key to {@code null}.
1.312 - * The {@link #containsKey containsKey} operation may be used to
1.313 - * distinguish these two cases.
1.314 - *
1.315 - * @see #put(Object, Object)
1.316 - */
1.317 - public V get(Object key) {
1.318 - if (key == null)
1.319 - return getForNullKey();
1.320 - int hash = hash(key.hashCode());
1.321 - for (Entry<K,V> e = table[indexFor(hash, table.length)];
1.322 - e != null;
1.323 - e = e.next) {
1.324 - Object k;
1.325 - if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
1.326 - return e.value;
1.327 - }
1.328 - return null;
1.329 - }
1.330 -
1.331 - /**
1.332 - * Offloaded version of get() to look up null keys. Null keys map
1.333 - * to index 0. This null case is split out into separate methods
1.334 - * for the sake of performance in the two most commonly used
1.335 - * operations (get and put), but incorporated with conditionals in
1.336 - * others.
1.337 - */
1.338 - private V getForNullKey() {
1.339 - for (Entry<K,V> e = table[0]; e != null; e = e.next) {
1.340 - if (e.key == null)
1.341 - return e.value;
1.342 - }
1.343 - return null;
1.344 - }
1.345 -
1.346 - /**
1.347 - * Returns <tt>true</tt> if this map contains a mapping for the
1.348 - * specified key.
1.349 - *
1.350 - * @param key The key whose presence in this map is to be tested
1.351 - * @return <tt>true</tt> if this map contains a mapping for the specified
1.352 - * key.
1.353 - */
1.354 - public boolean containsKey(Object key) {
1.355 - return getEntry(key) != null;
1.356 - }
1.357 -
1.358 - /**
1.359 - * Returns the entry associated with the specified key in the
1.360 - * HashMap. Returns null if the HashMap contains no mapping
1.361 - * for the key.
1.362 - */
1.363 - final Entry<K,V> getEntry(Object key) {
1.364 - int hash = (key == null) ? 0 : hash(key.hashCode());
1.365 - for (Entry<K,V> e = table[indexFor(hash, table.length)];
1.366 - e != null;
1.367 - e = e.next) {
1.368 - Object k;
1.369 - if (e.hash == hash &&
1.370 - ((k = e.key) == key || (key != null && key.equals(k))))
1.371 - return e;
1.372 - }
1.373 - return null;
1.374 - }
1.375 -
1.376 -
1.377 - /**
1.378 - * Associates the specified value with the specified key in this map.
1.379 - * If the map previously contained a mapping for the key, the old
1.380 - * value is replaced.
1.381 - *
1.382 - * @param key key with which the specified value is to be associated
1.383 - * @param value value to be associated with the specified key
1.384 - * @return the previous value associated with <tt>key</tt>, or
1.385 - * <tt>null</tt> if there was no mapping for <tt>key</tt>.
1.386 - * (A <tt>null</tt> return can also indicate that the map
1.387 - * previously associated <tt>null</tt> with <tt>key</tt>.)
1.388 - */
1.389 - public V put(K key, V value) {
1.390 - if (key == null)
1.391 - return putForNullKey(value);
1.392 - int hash = hash(key.hashCode());
1.393 - int i = indexFor(hash, table.length);
1.394 - for (Entry<K,V> e = table[i]; e != null; e = e.next) {
1.395 - Object k;
1.396 - if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
1.397 - V oldValue = e.value;
1.398 - e.value = value;
1.399 - e.recordAccess(this);
1.400 - return oldValue;
1.401 - }
1.402 - }
1.403 -
1.404 - modCount++;
1.405 - addEntry(hash, key, value, i);
1.406 - return null;
1.407 - }
1.408 -
1.409 - /**
1.410 - * Offloaded version of put for null keys
1.411 - */
1.412 - private V putForNullKey(V value) {
1.413 - for (Entry<K,V> e = table[0]; e != null; e = e.next) {
1.414 - if (e.key == null) {
1.415 - V oldValue = e.value;
1.416 - e.value = value;
1.417 - e.recordAccess(this);
1.418 - return oldValue;
1.419 - }
1.420 - }
1.421 - modCount++;
1.422 - addEntry(0, null, value, 0);
1.423 - return null;
1.424 - }
1.425 -
1.426 - /**
1.427 - * This method is used instead of put by constructors and
1.428 - * pseudoconstructors (clone, readObject). It does not resize the table,
1.429 - * check for comodification, etc. It calls createEntry rather than
1.430 - * addEntry.
1.431 - */
1.432 - private void putForCreate(K key, V value) {
1.433 - int hash = (key == null) ? 0 : hash(key.hashCode());
1.434 - int i = indexFor(hash, table.length);
1.435 -
1.436 - /**
1.437 - * Look for preexisting entry for key. This will never happen for
1.438 - * clone or deserialize. It will only happen for construction if the
1.439 - * input Map is a sorted map whose ordering is inconsistent w/ equals.
1.440 - */
1.441 - for (Entry<K,V> e = table[i]; e != null; e = e.next) {
1.442 - Object k;
1.443 - if (e.hash == hash &&
1.444 - ((k = e.key) == key || (key != null && key.equals(k)))) {
1.445 - e.value = value;
1.446 - return;
1.447 - }
1.448 - }
1.449 -
1.450 - createEntry(hash, key, value, i);
1.451 - }
1.452 -
1.453 - private void putAllForCreate(Map<? extends K, ? extends V> m) {
1.454 - for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1.455 - putForCreate(e.getKey(), e.getValue());
1.456 - }
1.457 -
1.458 - /**
1.459 - * Rehashes the contents of this map into a new array with a
1.460 - * larger capacity. This method is called automatically when the
1.461 - * number of keys in this map reaches its threshold.
1.462 - *
1.463 - * If current capacity is MAXIMUM_CAPACITY, this method does not
1.464 - * resize the map, but sets threshold to Integer.MAX_VALUE.
1.465 - * This has the effect of preventing future calls.
1.466 - *
1.467 - * @param newCapacity the new capacity, MUST be a power of two;
1.468 - * must be greater than current capacity unless current
1.469 - * capacity is MAXIMUM_CAPACITY (in which case value
1.470 - * is irrelevant).
1.471 - */
1.472 - void resize(int newCapacity) {
1.473 - Entry[] oldTable = table;
1.474 - int oldCapacity = oldTable.length;
1.475 - if (oldCapacity == MAXIMUM_CAPACITY) {
1.476 - threshold = Integer.MAX_VALUE;
1.477 - return;
1.478 - }
1.479 -
1.480 - Entry[] newTable = new Entry[newCapacity];
1.481 - transfer(newTable);
1.482 - table = newTable;
1.483 - threshold = (int)(newCapacity * loadFactor);
1.484 - }
1.485 -
1.486 - /**
1.487 - * Transfers all entries from current table to newTable.
1.488 - */
1.489 - void transfer(Entry[] newTable) {
1.490 - Entry[] src = table;
1.491 - int newCapacity = newTable.length;
1.492 - for (int j = 0; j < src.length; j++) {
1.493 - Entry<K,V> e = src[j];
1.494 - if (e != null) {
1.495 - src[j] = null;
1.496 - do {
1.497 - Entry<K,V> next = e.next;
1.498 - int i = indexFor(e.hash, newCapacity);
1.499 - e.next = newTable[i];
1.500 - newTable[i] = e;
1.501 - e = next;
1.502 - } while (e != null);
1.503 - }
1.504 - }
1.505 - }
1.506 -
1.507 - /**
1.508 - * Copies all of the mappings from the specified map to this map.
1.509 - * These mappings will replace any mappings that this map had for
1.510 - * any of the keys currently in the specified map.
1.511 - *
1.512 - * @param m mappings to be stored in this map
1.513 - * @throws NullPointerException if the specified map is null
1.514 - */
1.515 - public void putAll(Map<? extends K, ? extends V> m) {
1.516 - int numKeysToBeAdded = m.size();
1.517 - if (numKeysToBeAdded == 0)
1.518 - return;
1.519 -
1.520 - /*
1.521 - * Expand the map if the map if the number of mappings to be added
1.522 - * is greater than or equal to threshold. This is conservative; the
1.523 - * obvious condition is (m.size() + size) >= threshold, but this
1.524 - * condition could result in a map with twice the appropriate capacity,
1.525 - * if the keys to be added overlap with the keys already in this map.
1.526 - * By using the conservative calculation, we subject ourself
1.527 - * to at most one extra resize.
1.528 - */
1.529 - if (numKeysToBeAdded > threshold) {
1.530 - int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
1.531 - if (targetCapacity > MAXIMUM_CAPACITY)
1.532 - targetCapacity = MAXIMUM_CAPACITY;
1.533 - int newCapacity = table.length;
1.534 - while (newCapacity < targetCapacity)
1.535 - newCapacity <<= 1;
1.536 - if (newCapacity > table.length)
1.537 - resize(newCapacity);
1.538 - }
1.539 -
1.540 - for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1.541 - put(e.getKey(), e.getValue());
1.542 - }
1.543 -
1.544 - /**
1.545 - * Removes the mapping for the specified key from this map if present.
1.546 - *
1.547 - * @param key key whose mapping is to be removed from the map
1.548 - * @return the previous value associated with <tt>key</tt>, or
1.549 - * <tt>null</tt> if there was no mapping for <tt>key</tt>.
1.550 - * (A <tt>null</tt> return can also indicate that the map
1.551 - * previously associated <tt>null</tt> with <tt>key</tt>.)
1.552 - */
1.553 - public V remove(Object key) {
1.554 - Entry<K,V> e = removeEntryForKey(key);
1.555 - return (e == null ? null : e.value);
1.556 - }
1.557 -
1.558 - /**
1.559 - * Removes and returns the entry associated with the specified key
1.560 - * in the HashMap. Returns null if the HashMap contains no mapping
1.561 - * for this key.
1.562 - */
1.563 - final Entry<K,V> removeEntryForKey(Object key) {
1.564 - int hash = (key == null) ? 0 : hash(key.hashCode());
1.565 - int i = indexFor(hash, table.length);
1.566 - Entry<K,V> prev = table[i];
1.567 - Entry<K,V> e = prev;
1.568 -
1.569 - while (e != null) {
1.570 - Entry<K,V> next = e.next;
1.571 - Object k;
1.572 - if (e.hash == hash &&
1.573 - ((k = e.key) == key || (key != null && key.equals(k)))) {
1.574 - modCount++;
1.575 - size--;
1.576 - if (prev == e)
1.577 - table[i] = next;
1.578 - else
1.579 - prev.next = next;
1.580 - e.recordRemoval(this);
1.581 - return e;
1.582 - }
1.583 - prev = e;
1.584 - e = next;
1.585 - }
1.586 -
1.587 - return e;
1.588 - }
1.589 -
1.590 - /**
1.591 - * Special version of remove for EntrySet.
1.592 - */
1.593 - final Entry<K,V> removeMapping(Object o) {
1.594 - if (!(o instanceof Map.Entry))
1.595 - return null;
1.596 -
1.597 - Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1.598 - Object key = entry.getKey();
1.599 - int hash = (key == null) ? 0 : hash(key.hashCode());
1.600 - int i = indexFor(hash, table.length);
1.601 - Entry<K,V> prev = table[i];
1.602 - Entry<K,V> e = prev;
1.603 -
1.604 - while (e != null) {
1.605 - Entry<K,V> next = e.next;
1.606 - if (e.hash == hash && e.equals(entry)) {
1.607 - modCount++;
1.608 - size--;
1.609 - if (prev == e)
1.610 - table[i] = next;
1.611 - else
1.612 - prev.next = next;
1.613 - e.recordRemoval(this);
1.614 - return e;
1.615 - }
1.616 - prev = e;
1.617 - e = next;
1.618 - }
1.619 -
1.620 - return e;
1.621 - }
1.622 -
1.623 - /**
1.624 - * Removes all of the mappings from this map.
1.625 - * The map will be empty after this call returns.
1.626 - */
1.627 - public void clear() {
1.628 - modCount++;
1.629 - Entry[] tab = table;
1.630 - for (int i = 0; i < tab.length; i++)
1.631 - tab[i] = null;
1.632 - size = 0;
1.633 - }
1.634 -
1.635 - /**
1.636 - * Returns <tt>true</tt> if this map maps one or more keys to the
1.637 - * specified value.
1.638 - *
1.639 - * @param value value whose presence in this map is to be tested
1.640 - * @return <tt>true</tt> if this map maps one or more keys to the
1.641 - * specified value
1.642 - */
1.643 - public boolean containsValue(Object value) {
1.644 - if (value == null)
1.645 - return containsNullValue();
1.646 -
1.647 - Entry[] tab = table;
1.648 - for (int i = 0; i < tab.length ; i++)
1.649 - for (Entry e = tab[i] ; e != null ; e = e.next)
1.650 - if (value.equals(e.value))
1.651 - return true;
1.652 - return false;
1.653 - }
1.654 -
1.655 - /**
1.656 - * Special-case code for containsValue with null argument
1.657 - */
1.658 - private boolean containsNullValue() {
1.659 - Entry[] tab = table;
1.660 - for (int i = 0; i < tab.length ; i++)
1.661 - for (Entry e = tab[i] ; e != null ; e = e.next)
1.662 - if (e.value == null)
1.663 - return true;
1.664 - return false;
1.665 - }
1.666 -
1.667 - /**
1.668 - * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
1.669 - * values themselves are not cloned.
1.670 - *
1.671 - * @return a shallow copy of this map
1.672 - */
1.673 - public Object clone() {
1.674 - HashMap<K,V> result = null;
1.675 - try {
1.676 - result = (HashMap<K,V>)super.clone();
1.677 - } catch (CloneNotSupportedException e) {
1.678 - // assert false;
1.679 - }
1.680 - result.table = new Entry[table.length];
1.681 - result.entrySet = null;
1.682 - result.modCount = 0;
1.683 - result.size = 0;
1.684 - result.init();
1.685 - result.putAllForCreate(this);
1.686 -
1.687 - return result;
1.688 - }
1.689 -
1.690 - static class Entry<K,V> implements Map.Entry<K,V> {
1.691 - final K key;
1.692 - V value;
1.693 - Entry<K,V> next;
1.694 - final int hash;
1.695 -
1.696 - /**
1.697 - * Creates new entry.
1.698 - */
1.699 - Entry(int h, K k, V v, Entry<K,V> n) {
1.700 - value = v;
1.701 - next = n;
1.702 - key = k;
1.703 - hash = h;
1.704 - }
1.705 -
1.706 - public final K getKey() {
1.707 - return key;
1.708 - }
1.709 -
1.710 - public final V getValue() {
1.711 - return value;
1.712 - }
1.713 -
1.714 - public final V setValue(V newValue) {
1.715 - V oldValue = value;
1.716 - value = newValue;
1.717 - return oldValue;
1.718 - }
1.719 -
1.720 - public final boolean equals(Object o) {
1.721 - if (!(o instanceof Map.Entry))
1.722 - return false;
1.723 - Map.Entry e = (Map.Entry)o;
1.724 - Object k1 = getKey();
1.725 - Object k2 = e.getKey();
1.726 - if (k1 == k2 || (k1 != null && k1.equals(k2))) {
1.727 - Object v1 = getValue();
1.728 - Object v2 = e.getValue();
1.729 - if (v1 == v2 || (v1 != null && v1.equals(v2)))
1.730 - return true;
1.731 - }
1.732 - return false;
1.733 - }
1.734 -
1.735 - public final int hashCode() {
1.736 - return (key==null ? 0 : key.hashCode()) ^
1.737 - (value==null ? 0 : value.hashCode());
1.738 - }
1.739 -
1.740 - public final String toString() {
1.741 - return getKey() + "=" + getValue();
1.742 - }
1.743 -
1.744 - /**
1.745 - * This method is invoked whenever the value in an entry is
1.746 - * overwritten by an invocation of put(k,v) for a key k that's already
1.747 - * in the HashMap.
1.748 - */
1.749 - void recordAccess(HashMap<K,V> m) {
1.750 - }
1.751 -
1.752 - /**
1.753 - * This method is invoked whenever the entry is
1.754 - * removed from the table.
1.755 - */
1.756 - void recordRemoval(HashMap<K,V> m) {
1.757 - }
1.758 - }
1.759 -
1.760 - /**
1.761 - * Adds a new entry with the specified key, value and hash code to
1.762 - * the specified bucket. It is the responsibility of this
1.763 - * method to resize the table if appropriate.
1.764 - *
1.765 - * Subclass overrides this to alter the behavior of put method.
1.766 - */
1.767 - void addEntry(int hash, K key, V value, int bucketIndex) {
1.768 - Entry<K,V> e = table[bucketIndex];
1.769 - table[bucketIndex] = new Entry<>(hash, key, value, e);
1.770 - if (size++ >= threshold)
1.771 - resize(2 * table.length);
1.772 - }
1.773 -
1.774 - /**
1.775 - * Like addEntry except that this version is used when creating entries
1.776 - * as part of Map construction or "pseudo-construction" (cloning,
1.777 - * deserialization). This version needn't worry about resizing the table.
1.778 - *
1.779 - * Subclass overrides this to alter the behavior of HashMap(Map),
1.780 - * clone, and readObject.
1.781 - */
1.782 - void createEntry(int hash, K key, V value, int bucketIndex) {
1.783 - Entry<K,V> e = table[bucketIndex];
1.784 - table[bucketIndex] = new Entry<>(hash, key, value, e);
1.785 - size++;
1.786 - }
1.787 -
1.788 - private abstract class HashIterator<E> implements Iterator<E> {
1.789 - Entry<K,V> next; // next entry to return
1.790 - int expectedModCount; // For fast-fail
1.791 - int index; // current slot
1.792 - Entry<K,V> current; // current entry
1.793 -
1.794 - HashIterator() {
1.795 - expectedModCount = modCount;
1.796 - if (size > 0) { // advance to first entry
1.797 - Entry[] t = table;
1.798 - while (index < t.length && (next = t[index++]) == null)
1.799 - ;
1.800 - }
1.801 - }
1.802 -
1.803 - public final boolean hasNext() {
1.804 - return next != null;
1.805 - }
1.806 -
1.807 - final Entry<K,V> nextEntry() {
1.808 - if (modCount != expectedModCount)
1.809 - throw new ConcurrentModificationException();
1.810 - Entry<K,V> e = next;
1.811 - if (e == null)
1.812 - throw new NoSuchElementException();
1.813 -
1.814 - if ((next = e.next) == null) {
1.815 - Entry[] t = table;
1.816 - while (index < t.length && (next = t[index++]) == null)
1.817 - ;
1.818 - }
1.819 - current = e;
1.820 - return e;
1.821 - }
1.822 -
1.823 - public void remove() {
1.824 - if (current == null)
1.825 - throw new IllegalStateException();
1.826 - if (modCount != expectedModCount)
1.827 - throw new ConcurrentModificationException();
1.828 - Object k = current.key;
1.829 - current = null;
1.830 - HashMap.this.removeEntryForKey(k);
1.831 - expectedModCount = modCount;
1.832 - }
1.833 -
1.834 - }
1.835 -
1.836 - private final class ValueIterator extends HashIterator<V> {
1.837 - public V next() {
1.838 - return nextEntry().value;
1.839 - }
1.840 - }
1.841 -
1.842 - private final class KeyIterator extends HashIterator<K> {
1.843 - public K next() {
1.844 - return nextEntry().getKey();
1.845 - }
1.846 - }
1.847 -
1.848 - private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
1.849 - public Map.Entry<K,V> next() {
1.850 - return nextEntry();
1.851 - }
1.852 - }
1.853 -
1.854 - // Subclass overrides these to alter behavior of views' iterator() method
1.855 - Iterator<K> newKeyIterator() {
1.856 - return new KeyIterator();
1.857 - }
1.858 - Iterator<V> newValueIterator() {
1.859 - return new ValueIterator();
1.860 - }
1.861 - Iterator<Map.Entry<K,V>> newEntryIterator() {
1.862 - return new EntryIterator();
1.863 - }
1.864 -
1.865 -
1.866 - // Views
1.867 -
1.868 - private transient Set<Map.Entry<K,V>> entrySet = null;
1.869 -
1.870 - /**
1.871 - * Returns a {@link Set} view of the keys contained in this map.
1.872 - * The set is backed by the map, so changes to the map are
1.873 - * reflected in the set, and vice-versa. If the map is modified
1.874 - * while an iteration over the set is in progress (except through
1.875 - * the iterator's own <tt>remove</tt> operation), the results of
1.876 - * the iteration are undefined. The set supports element removal,
1.877 - * which removes the corresponding mapping from the map, via the
1.878 - * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1.879 - * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1.880 - * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
1.881 - * operations.
1.882 - */
1.883 - public Set<K> keySet() {
1.884 - Set<K> ks = keySet;
1.885 - return (ks != null ? ks : (keySet = new KeySet()));
1.886 - }
1.887 -
1.888 - private final class KeySet extends AbstractSet<K> {
1.889 - public Iterator<K> iterator() {
1.890 - return newKeyIterator();
1.891 - }
1.892 - public int size() {
1.893 - return size;
1.894 - }
1.895 - public boolean contains(Object o) {
1.896 - return containsKey(o);
1.897 - }
1.898 - public boolean remove(Object o) {
1.899 - return HashMap.this.removeEntryForKey(o) != null;
1.900 - }
1.901 - public void clear() {
1.902 - HashMap.this.clear();
1.903 - }
1.904 - }
1.905 -
1.906 - /**
1.907 - * Returns a {@link Collection} view of the values contained in this map.
1.908 - * The collection is backed by the map, so changes to the map are
1.909 - * reflected in the collection, and vice-versa. If the map is
1.910 - * modified while an iteration over the collection is in progress
1.911 - * (except through the iterator's own <tt>remove</tt> operation),
1.912 - * the results of the iteration are undefined. The collection
1.913 - * supports element removal, which removes the corresponding
1.914 - * mapping from the map, via the <tt>Iterator.remove</tt>,
1.915 - * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1.916 - * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
1.917 - * support the <tt>add</tt> or <tt>addAll</tt> operations.
1.918 - */
1.919 - public Collection<V> values() {
1.920 - Collection<V> vs = values;
1.921 - return (vs != null ? vs : (values = new Values()));
1.922 - }
1.923 -
1.924 - private final class Values extends AbstractCollection<V> {
1.925 - public Iterator<V> iterator() {
1.926 - return newValueIterator();
1.927 - }
1.928 - public int size() {
1.929 - return size;
1.930 - }
1.931 - public boolean contains(Object o) {
1.932 - return containsValue(o);
1.933 - }
1.934 - public void clear() {
1.935 - HashMap.this.clear();
1.936 - }
1.937 - }
1.938 -
1.939 - /**
1.940 - * Returns a {@link Set} view of the mappings contained in this map.
1.941 - * The set is backed by the map, so changes to the map are
1.942 - * reflected in the set, and vice-versa. If the map is modified
1.943 - * while an iteration over the set is in progress (except through
1.944 - * the iterator's own <tt>remove</tt> operation, or through the
1.945 - * <tt>setValue</tt> operation on a map entry returned by the
1.946 - * iterator) the results of the iteration are undefined. The set
1.947 - * supports element removal, which removes the corresponding
1.948 - * mapping from the map, via the <tt>Iterator.remove</tt>,
1.949 - * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
1.950 - * <tt>clear</tt> operations. It does not support the
1.951 - * <tt>add</tt> or <tt>addAll</tt> operations.
1.952 - *
1.953 - * @return a set view of the mappings contained in this map
1.954 - */
1.955 - public Set<Map.Entry<K,V>> entrySet() {
1.956 - return entrySet0();
1.957 - }
1.958 -
1.959 - private Set<Map.Entry<K,V>> entrySet0() {
1.960 - Set<Map.Entry<K,V>> es = entrySet;
1.961 - return es != null ? es : (entrySet = new EntrySet());
1.962 - }
1.963 -
1.964 - private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1.965 - public Iterator<Map.Entry<K,V>> iterator() {
1.966 - return newEntryIterator();
1.967 - }
1.968 - public boolean contains(Object o) {
1.969 - if (!(o instanceof Map.Entry))
1.970 - return false;
1.971 - Map.Entry<K,V> e = (Map.Entry<K,V>) o;
1.972 - Entry<K,V> candidate = getEntry(e.getKey());
1.973 - return candidate != null && candidate.equals(e);
1.974 - }
1.975 - public boolean remove(Object o) {
1.976 - return removeMapping(o) != null;
1.977 - }
1.978 - public int size() {
1.979 - return size;
1.980 - }
1.981 - public void clear() {
1.982 - HashMap.this.clear();
1.983 - }
1.984 - }
1.985 -
1.986 -
1.987 - private static final long serialVersionUID = 362498820763181265L;
1.988 -
1.989 -
1.990 - // These methods are used when serializing HashSets
1.991 - int capacity() { return table.length; }
1.992 - float loadFactor() { return loadFactor; }
1.993 -}