1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/emul/compact/src/main/java/java/util/HashMap.java Wed Jan 23 22:32:27 2013 +0100
1.3 @@ -0,0 +1,1051 @@
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 + * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
1.988 + * serialize it).
1.989 + *
1.990 + * @serialData The <i>capacity</i> of the HashMap (the length of the
1.991 + * bucket array) is emitted (int), followed by the
1.992 + * <i>size</i> (an int, the number of key-value
1.993 + * mappings), followed by the key (Object) and value (Object)
1.994 + * for each key-value mapping. The key-value mappings are
1.995 + * emitted in no particular order.
1.996 + */
1.997 + private void writeObject(java.io.ObjectOutputStream s)
1.998 + throws IOException
1.999 + {
1.1000 + Iterator<Map.Entry<K,V>> i =
1.1001 + (size > 0) ? entrySet0().iterator() : null;
1.1002 +
1.1003 + // Write out the threshold, loadfactor, and any hidden stuff
1.1004 + s.defaultWriteObject();
1.1005 +
1.1006 + // Write out number of buckets
1.1007 + s.writeInt(table.length);
1.1008 +
1.1009 + // Write out size (number of Mappings)
1.1010 + s.writeInt(size);
1.1011 +
1.1012 + // Write out keys and values (alternating)
1.1013 + if (i != null) {
1.1014 + while (i.hasNext()) {
1.1015 + Map.Entry<K,V> e = i.next();
1.1016 + s.writeObject(e.getKey());
1.1017 + s.writeObject(e.getValue());
1.1018 + }
1.1019 + }
1.1020 + }
1.1021 +
1.1022 + private static final long serialVersionUID = 362498820763181265L;
1.1023 +
1.1024 + /**
1.1025 + * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
1.1026 + * deserialize it).
1.1027 + */
1.1028 + private void readObject(java.io.ObjectInputStream s)
1.1029 + throws IOException, ClassNotFoundException
1.1030 + {
1.1031 + // Read in the threshold, loadfactor, and any hidden stuff
1.1032 + s.defaultReadObject();
1.1033 +
1.1034 + // Read in number of buckets and allocate the bucket array;
1.1035 + int numBuckets = s.readInt();
1.1036 + table = new Entry[numBuckets];
1.1037 +
1.1038 + init(); // Give subclass a chance to do its thing.
1.1039 +
1.1040 + // Read in size (number of Mappings)
1.1041 + int size = s.readInt();
1.1042 +
1.1043 + // Read the keys and values, and put the mappings in the HashMap
1.1044 + for (int i=0; i<size; i++) {
1.1045 + K key = (K) s.readObject();
1.1046 + V value = (V) s.readObject();
1.1047 + putForCreate(key, value);
1.1048 + }
1.1049 + }
1.1050 +
1.1051 + // These methods are used when serializing HashSets
1.1052 + int capacity() { return table.length; }
1.1053 + float loadFactor() { return loadFactor; }
1.1054 +}