1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Licensed to the Apache Software Foundation (ASF) under one or more 319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * contributor license agreements. See the NOTICE file distributed with 4adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * this work for additional information regarding copyright ownership. 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The ASF licenses this file to You under the Apache License, Version 2.0 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * (the "License"); you may not use this file except in compliance with 719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * the License. You may obtain a copy of the License at 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 9adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 10adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 11adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Unless required by applicable law or agreed to in writing, software 12adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 13adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * See the License for the specific language governing permissions and 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * limitations under the License. 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util; 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 20adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.IOException; 2119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Blochimport java.io.InvalidObjectException; 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectInputStream; 23adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectOutputStream; 2419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Blochimport java.io.ObjectStreamField; 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.Serializable; 266186821cb13f4ac7ff50950c813394367e021eaeJesse Wilsonimport libcore.util.Objects; 27adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 28adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 29438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * HashMap is an implementation of {@link Map}. All optional operations are supported. 30f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 31438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * <p>All elements are permitted as keys or values, including null. 32f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 33438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * <p>Note that the iteration order for HashMap is non-deterministic. If you want 34438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * deterministic iteration, use {@link LinkedHashMap}. 35f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 36438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * <p>Note: the implementation of {@code HashMap} is not synchronized. 37438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * If one thread of several threads accessing an instance modifies the map 38438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * structurally, access to the map needs to be synchronized. A structural 39438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * modification is an operation that adds or removes an entry. Changes in 40438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * the value of an entry are not structural changes. 41f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 42438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * <p>The {@code Iterator} created by calling the {@code iterator} method 43438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * may throw a {@code ConcurrentModificationException} if the map is structurally 44438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * changed while an iterator is used to iterate over the elements. Only the 45438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * {@code remove} method that is provided by the iterator allows for removal of 46438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * elements during iteration. It is not possible to guarantee that this 47438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * mechanism works in all cases of unsynchronized concurrent modification. It 48438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * should only be used for debugging purposes. 49f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 5019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @param <K> the type of keys maintained by this map 5119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @param <V> the type of mapped values 52adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 53438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughespublic class HashMap<K, V> extends AbstractMap<K, V> implements Cloneable, Serializable { 5419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 5519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Min capacity (other than zero) for a HashMap. Must be a power of two 5619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * greater than 1 (and less than 1 << 30). 57f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson */ 5819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private static final int MINIMUM_CAPACITY = 4; 59adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 6019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 6119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Max capacity for a HashMap. Must be a power of two >= MINIMUM_CAPACITY. 62f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson */ 6319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private static final int MAXIMUM_CAPACITY = 1 << 30; 64adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 6519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 6619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * An empty table shared by all zero-capacity maps (typically from default 6719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * constructor). It is never written to, and replaced on first put. Its size 6819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * is set to half the minimum, so that the first resize will create a 6919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * minimum-sized table. 70f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson */ 7119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private static final Entry[] EMPTY_TABLE 7219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch = new HashMapEntry[MINIMUM_CAPACITY >>> 1]; 73adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 7419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 7519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * The default load factor. Note that this implementation ignores the 7619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * load factor, but cannot do away with it entirely because it's 77438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * mentioned in the API. 7819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * 7919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * <p>Note that this constant has no impact on the behavior of the program, 8019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * but it is emitted as part of the serialized form. The load factor of 8119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * .75 is hardwired into the program, which uses cheap shifts in place of 8219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * expensive division. 83f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson */ 8419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch static final float DEFAULT_LOAD_FACTOR = .75F; 85adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 8619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 8719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * The hash table. If this hash map contains a mapping for null, it is 8819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * not represented this hash table. 89f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson */ 9019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch transient HashMapEntry<K, V>[] table; 91f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 9219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 9319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * The entry representing the null key, or null if there's no such mapping. 94f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson */ 9519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch transient HashMapEntry<K, V> entryForNullKey; 96f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 9719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 9819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * The number of mappings in this hash map. 9919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 10019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch transient int size; 101f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 10219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 10319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Incremented by "structural modifications" to allow (best effort) 10419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * detection of concurrent modification. 10519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 10619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch transient int modCount; 107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 108f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson /** 10919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * The table is rehashed when its size exceeds this threshold. 11019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * The value of this field is generally .75 * capacity, except when 11119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * the capacity is zero, as described in the EMPTY_TABLE declaration 11219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * above. 113f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson */ 11419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private transient int threshold; 11519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 11619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch // Views - lazily initialized 11719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private transient Set<K> keySet; 11819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private transient Set<Entry<K, V>> entrySet; 11919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private transient Collection<V> values; 120adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 121adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 122adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new empty {@code HashMap} instance. 123adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 12419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @SuppressWarnings("unchecked") 125adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public HashMap() { 12619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch table = (HashMapEntry<K, V>[]) EMPTY_TABLE; 12719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch threshold = -1; // Forces first put invocation to replace EMPTY_TABLE 128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 130adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code HashMap} instance with the specified capacity. 132f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial capacity of this hash map. 135adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalArgumentException 136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * when the capacity is less than zero. 137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public HashMap(int capacity) { 13919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (capacity < 0) { 14019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch throw new IllegalArgumentException("Capacity: " + capacity); 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 142f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 14319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (capacity == 0) { 14419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @SuppressWarnings("unchecked") 14519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE; 14619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch table = tab; 14719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch threshold = -1; // Forces first put() to replace EMPTY_TABLE 14819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return; 149f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 15019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 15119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (capacity < MINIMUM_CAPACITY) { 15219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch capacity = MINIMUM_CAPACITY; 15319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } else if (capacity > MAXIMUM_CAPACITY) { 15419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch capacity = MAXIMUM_CAPACITY; 15519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } else { 1561424a2a1a9fc53dc8b859a77c02c924d3dc2334dIan Rogers capacity = Collections.roundUpToPowerOfTwo(capacity); 157f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 15819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch makeTable(capacity); 159adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code HashMap} instance with the specified capacity and 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * load factor. 164f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity 166adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial capacity of this hash map. 167adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param loadFactor 168adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial load factor. 169adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalArgumentException 170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * when the capacity is less than zero or the load factor is 17119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * less or equal to zero or NaN. 172adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public HashMap(int capacity, float loadFactor) { 17419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch this(capacity); 17519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 17619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (loadFactor <= 0 || Float.isNaN(loadFactor)) { 17719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch throw new IllegalArgumentException("Load factor: " + loadFactor); 178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 17919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 18019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /* 18119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Note that this implementation ignores loadFactor; it always uses 182438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * a load factor of 3/4. This simplifies the code and generally 18319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * improves performance. 18419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 185adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 187adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 188adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code HashMap} instance containing the mappings from 189adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the specified map. 190f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 191adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param map 192adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the mappings to add. 193adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 194adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public HashMap(Map<? extends K, ? extends V> map) { 19519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch this(capacityForInitSize(map.size())); 19619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch constructorPutAll(map); 197adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 198adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 20019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Inserts all of the elements of map into this HashMap in a manner 201438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * suitable for use by constructors and pseudo-constructors (i.e., clone, 20219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * readObject). Also used by LinkedHashMap. 203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 20419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch final void constructorPutAll(Map<? extends K, ? extends V> map) { 2059084e968a10ed230e76940eef60b8f6229cc7b8bElliott Hughes if (table == EMPTY_TABLE) { 2069084e968a10ed230e76940eef60b8f6229cc7b8bElliott Hughes doubleCapacity(); // Don't do unchecked puts to a shared table. 2079084e968a10ed230e76940eef60b8f6229cc7b8bElliott Hughes } 20819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (Entry<? extends K, ? extends V> e : map.entrySet()) { 20919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch constructorPut(e.getKey(), e.getValue()); 21019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 211adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 212adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 21319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 21419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Returns an appropriate capacity for the specified initial size. Does 21519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * not round the result up to a power of two; the caller must do this! 21619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * The returned value will be between 0 and MAXIMUM_CAPACITY (inclusive). 21719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 21819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch static int capacityForInitSize(int size) { 21919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth 22019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 22119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch // boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY 22219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY; 223adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 224adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 225adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 226adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a shallow copy of this map. 227f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 228adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return a shallow copy of this map. 229adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 230adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @SuppressWarnings("unchecked") 23119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public Object clone() { 23219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /* 23319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * This could be made more efficient. It unnecessarily hashes all of 23419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * the elements in the map. 23519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 23619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMap<K, V> result; 237adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 23819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch result = (HashMap<K, V>) super.clone(); 239adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } catch (CloneNotSupportedException e) { 24019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch throw new AssertionError(e); 241adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 242adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 24319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch // Restore clone to empty state, retaining our capacity and threshold 24419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch result.makeTable(table.length); 24519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch result.entryForNullKey = null; 24619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch result.size = 0; 24719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch result.keySet = null; 24819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch result.entrySet = null; 24919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch result.values = null; 25019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 25119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch result.init(); // Give subclass a chance to initialize itself 25219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch result.constructorPutAll(this); // Calls method overridden in subclass!! 25319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return result; 254adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 255adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 256adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 25719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * This method is called from the pseudo-constructors (clone and readObject) 25819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * prior to invoking constructorPut/constructorPutAll, which invoke the 259438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * overridden constructorNewEntry method. Normally it is a VERY bad idea to 26019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * invoke an overridden method from a pseudo-constructor (Effective Java 2614adff24306c86433ce4f771da8489a574e63318eElliott Hughes * Item 17). In this case it is unavoidable, and the init method provides a 26219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * workaround. 263adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 26419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch void init() { } 265adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 266adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 26719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Returns whether this map is empty. 268f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 26919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @return {@code true} if this map has no elements, {@code false} 27019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * otherwise. 27119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @see #size() 272adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 27319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public boolean isEmpty() { 27419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return size == 0; 275adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 276adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 277adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 27819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Returns the number of elements in this map. 279f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 28019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @return the number of elements in this map. 281adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 28219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public int size() { 28319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return size; 284adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 285adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 286adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 287adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the value of the mapping with the specified key. 288f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 289adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param key 290adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the key. 291adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the value of the mapping with the specified key, or {@code null} 292adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if no mapping for the specified key is found. 293adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 294adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public V get(Object key) { 295adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (key == null) { 29619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> e = entryForNullKey; 29719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return e == null ? null : e.value; 298adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 299f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 30044bc12dfe2e22cfb86dd619f35f040f3e0628aabElliott Hughes int hash = Collections.secondaryHash(key); 30119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] tab = table; 30219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; 30319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch e != null; e = e.next) { 30419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch K eKey = e.key; 30519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (eKey == key || (e.hash == hash && key.equals(eKey))) { 30619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return e.value; 307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 308adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 30919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return null; 310adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 312adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 31319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Returns whether this map contains the specified key. 314f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 31519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @param key 31619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * the key to search for. 31719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @return {@code true} if this map contains the specified key, 31819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * {@code false} otherwise. 319adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 32019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public boolean containsKey(Object key) { 32119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (key == null) { 32219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return entryForNullKey != null; 32319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 32419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 32544bc12dfe2e22cfb86dd619f35f040f3e0628aabElliott Hughes int hash = Collections.secondaryHash(key); 32619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] tab = table; 32719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; 32819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch e != null; e = e.next) { 32919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch K eKey = e.key; 33019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (eKey == key || (e.hash == hash && key.equals(eKey))) { 33119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return true; 33219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 33319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 33419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return false; 335adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 336adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 337adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 33819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Returns whether this map contains the specified value. 339f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 34019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @param value 34119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * the value to search for. 34219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @return {@code true} if this map contains the specified value, 34319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * {@code false} otherwise. 344adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 34519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public boolean containsValue(Object value) { 34619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry[] tab = table; 34719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int len = tab.length; 34819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (value == null) { 34919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (int i = 0; i < len; i++) { 35019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (HashMapEntry e = tab[i]; e != null; e = e.next) { 35119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (e.value == null) { 35219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return true; 35319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 354adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 35519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 35619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return entryForNullKey != null && entryForNullKey.value == null; 35719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 358adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 35919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch // value is non-null 36019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (int i = 0; i < len; i++) { 36119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (HashMapEntry e = tab[i]; e != null; e = e.next) { 36219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (value.equals(e.value)) { 36319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return true; 364adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 36519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 366adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 36719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return entryForNullKey != null && value.equals(entryForNullKey.value); 368adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 369adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 370adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 371adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Maps the specified key to the specified value. 372f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 373adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param key 374adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the key. 375adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param value 376adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the value. 377adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the value of any previous mapping with the specified key or 378adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code null} if there was no such mapping. 379adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 38019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public V put(K key, V value) { 38119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (key == null) { 38219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return putValueForNullKey(value); 38319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 384adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 38544bc12dfe2e22cfb86dd619f35f040f3e0628aabElliott Hughes int hash = Collections.secondaryHash(key); 38619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] tab = table; 38719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int index = hash & (tab.length - 1); 3889483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) { 38919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (e.hash == hash && key.equals(e.key)) { 39019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch preModify(e); 39119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch V oldValue = e.value; 39219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch e.value = value; 39319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return oldValue; 394adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 39519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 39619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 39719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch // No entry for (non-null) key is present; create one 39819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch modCount++; 39919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (size++ > threshold) { 40019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch tab = doubleCapacity(); 40119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch index = hash & (tab.length - 1); 40219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 4039483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch addNewEntry(key, value, hash, index); 40419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return null; 40519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 40619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 40719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private V putValueForNullKey(V value) { 40819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> entry = entryForNullKey; 40919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (entry == null) { 4109483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch addNewEntryForNullKey(value); 41119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch size++; 41219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch modCount++; 41319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return null; 414adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 41519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch preModify(entry); 41619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch V oldValue = entry.value; 41719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch entry.value = value; 41819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return oldValue; 41919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 42019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 42119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 42219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 423438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * Give LinkedHashMap a chance to take action when we modify an existing 42419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * entry. 42519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * 42619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @param e the entry we're about to modify. 42719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 42819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch void preModify(HashMapEntry<K, V> e) { } 42919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 43019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 43119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * This method is just like put, except that it doesn't do things that 43219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * are inappropriate or unnecessary for constructors and pseudo-constructors 43319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * (i.e., clone, readObject). In particular, this method does not check to 43419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * ensure that capacity is sufficient, and does not increment modCount. 43519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 43619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private void constructorPut(K key, V value) { 43719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (key == null) { 43819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> entry = entryForNullKey; 439adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (entry == null) { 44019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch entryForNullKey = constructorNewEntry(null, value, 0, null); 44119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch size++; 44219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } else { 44319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch entry.value = value; 444adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 44519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return; 446adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 447adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 44844bc12dfe2e22cfb86dd619f35f040f3e0628aabElliott Hughes int hash = Collections.secondaryHash(key); 44919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] tab = table; 45019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int index = hash & (tab.length - 1); 45119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> first = tab[index]; 45219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (HashMapEntry<K, V> e = first; e != null; e = e.next) { 45319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (e.hash == hash && key.equals(e.key)) { 45419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch e.value = value; 45519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return; 45619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 45719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 45819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 45919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch // No entry for (non-null) key is present; create one 46019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch tab[index] = constructorNewEntry(key, value, hash, first); 46119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch size++; 462adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 463adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 46419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 4659483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch * Creates a new entry for the given key, value, hash, and index and 4669483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch * inserts it into the hash table. This method is called by put 4679483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch * (and indirectly, putAll), and overridden by LinkedHashMap. The hash 4689483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch * must incorporate the secondary hash function. 4699483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch */ 4709483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch void addNewEntry(K key, V value, int hash, int index) { 4719483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]); 4729483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch } 4739483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch 4749483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch /** 4759483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch * Creates a new entry for the null key, and the given value and 4769483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch * inserts it into the hash table. This method is called by put 4779483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch * (and indirectly, putAll), and overridden by LinkedHashMap. 47819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 4799483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch void addNewEntryForNullKey(V value) { 4809483551bcc25e4df0a27d6548b54e1971fac9aeaJoshua Bloch entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null); 481adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 482adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 48319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 48419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Like newEntry, but does not perform any activity that would be 48519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * unnecessary or inappropriate for constructors. In this class, the 48619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * two methods behave identically; in LinkedHashMap, they differ. 48719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 48819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> constructorNewEntry( 48919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch K key, V value, int hash, HashMapEntry<K, V> first) { 49019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return new HashMapEntry<K, V>(key, value, hash, first); 491adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 492adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 493adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 494adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Copies all the mappings in the specified map to this map. These mappings 495adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * will replace all mappings that this map had for any of the keys currently 496adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * in the given map. 497f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 498adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param map 499adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the map to copy mappings from. 500adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 50119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public void putAll(Map<? extends K, ? extends V> map) { 50219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch ensureCapacity(map.size()); 50319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch super.putAll(map); 504adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 505adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 50619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 50719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Ensures that the hash table has sufficient capacity to store the 50819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * specified number of mappings, with room to grow. If not, it increases the 50919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * capacity as appropriate. Like doubleCapacity, this method moves existing 51019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * entries to new buckets as appropriate. Unlike doubleCapacity, this method 51119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * can grow the table by factors of 2^n for n > 1. Hopefully, a single call 51219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * to this method will be faster than multiple calls to doubleCapacity. 51319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * 51419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * <p>This method is called only by putAll. 51519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 51619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private void ensureCapacity(int numMappings) { 5171424a2a1a9fc53dc8b859a77c02c924d3dc2334dIan Rogers int newCapacity = Collections.roundUpToPowerOfTwo(capacityForInitSize(numMappings)); 51819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] oldTable = table; 51919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int oldCapacity = oldTable.length; 52019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (newCapacity <= oldCapacity) { 52119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return; 522adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 523b5bde2fd72189192b52e726a2d606d70c3c8a34bElliott Hughes if (newCapacity == oldCapacity * 2) { 52419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch doubleCapacity(); 52519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return; 526adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 527adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 52819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch // We're growing by at least 4x, rehash in the obvious way 52919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] newTable = makeTable(newCapacity); 53019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (size != 0) { 53119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int newMask = newCapacity - 1; 53219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (int i = 0; i < oldCapacity; i++) { 53319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (HashMapEntry<K, V> e = oldTable[i]; e != null;) { 53419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> oldNext = e.next; 53519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int newIndex = e.hash & newMask; 53619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> newNext = newTable[newIndex]; 53719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch newTable[newIndex] = e; 53819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch e.next = newNext; 53919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch e = oldNext; 54019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 541adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 542adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 543adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 544adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 54519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 54619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Allocate a table of the given capacity and set the threshold accordingly. 54719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @param newCapacity must be a power of two 54819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 54919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private HashMapEntry<K, V>[] makeTable(int newCapacity) { 55019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable 55119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch = (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity]; 55219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch table = newTable; 55319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity 55419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return newTable; 55519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 55619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 55719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 55819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Doubles the capacity of the hash table. Existing entries are placed in 55919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * the correct bucket on the enlarged table. If the current capacity is, 56019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which 56119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * will be new unless we were already at MAXIMUM_CAPACITY. 56219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 56319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private HashMapEntry<K, V>[] doubleCapacity() { 56419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] oldTable = table; 56519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int oldCapacity = oldTable.length; 56619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (oldCapacity == MAXIMUM_CAPACITY) { 56719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return oldTable; 56819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 569b5bde2fd72189192b52e726a2d606d70c3c8a34bElliott Hughes int newCapacity = oldCapacity * 2; 57019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] newTable = makeTable(newCapacity); 57119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (size == 0) { 57219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return newTable; 57319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 57419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 57519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (int j = 0; j < oldCapacity; j++) { 57619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /* 57719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Rehash the bucket using the minimum number of field writes. 57819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * This is the most subtle and delicate code in the class. 57919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 58019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> e = oldTable[j]; 58119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (e == null) { 58219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch continue; 58319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 58419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int highBit = e.hash & oldCapacity; 58519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> broken = null; 58619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch newTable[j | highBit] = e; 58719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) { 58819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int nextHighBit = n.hash & oldCapacity; 58919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (nextHighBit != highBit) { 59019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (broken == null) 59119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch newTable[j | nextHighBit] = n; 59219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch else 59319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch broken.next = n; 59419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch broken = e; 59519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch highBit = nextHighBit; 59619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 59719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 59819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (broken != null) 59919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch broken.next = null; 60019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 60119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return newTable; 602adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 603adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 604adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 605adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Removes the mapping with the specified key from this map. 606f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 607adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param key 608adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the key of the mapping to remove. 609adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the value of the removed mapping or {@code null} if no mapping 610adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * for the specified key was found. 611adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 61219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public V remove(Object key) { 61319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (key == null) { 61419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return removeNullKey(); 61519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 61644bc12dfe2e22cfb86dd619f35f040f3e0628aabElliott Hughes int hash = Collections.secondaryHash(key); 61719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] tab = table; 61819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int index = hash & (tab.length - 1); 61919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (HashMapEntry<K, V> e = tab[index], prev = null; 62019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch e != null; prev = e, e = e.next) { 62119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (e.hash == hash && key.equals(e.key)) { 62219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (prev == null) { 62319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch tab[index] = e.next; 62419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } else { 62519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch prev.next = e.next; 62619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 62719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch modCount++; 62819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch size--; 62919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch postRemove(e); 63019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return e.value; 63119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 632adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 634adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 635adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 63619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private V removeNullKey() { 63719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> e = entryForNullKey; 63819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (e == null) { 639adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return null; 640adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 64119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch entryForNullKey = null; 642adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project modCount++; 64319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch size--; 64419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch postRemove(e); 64519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return e.value; 646adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 647adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 648adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 64919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Subclass overrides this method to unlink entry. 65019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 65119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch void postRemove(HashMapEntry<K, V> e) { } 65219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 65319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 65419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Removes all mappings from this hash map, leaving it empty. 655f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 65619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @see #isEmpty 65719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @see #size 65819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 65919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public void clear() { 66019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (size != 0) { 66119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch Arrays.fill(table, null); 66219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch entryForNullKey = null; 66319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch modCount++; 66419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch size = 0; 66519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 66619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 66719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 66819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 66919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Returns a set of the keys contained in this map. The set is backed by 67019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * this map so changes to one are reflected by the other. The set does not 67119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * support adding. 67219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * 67319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @return a set of the keys. 674adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 67519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public Set<K> keySet() { 67619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch Set<K> ks = keySet; 67719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return (ks != null) ? ks : (keySet = new KeySet()); 678adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 679adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 680adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 681adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a collection of the values contained in this map. The collection 682adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * is backed by this map so changes to one are reflected by the other. The 683adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * collection supports remove, removeAll, retainAll and clear operations, 684adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * and it does not support add or addAll operations. 685adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p> 686adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * This method returns a collection which is the subclass of 687adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * AbstractCollection. The iterator method of this subclass returns a 688adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * "wrapper object" over the iterator of map's entrySet(). The {@code size} 689adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * method wraps the map's size method and the {@code contains} method wraps 690adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the map's containsValue method. 69119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * </p> 692adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p> 693adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The collection is created when this method is called for the first time 694adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * and returned in response to all subsequent calls. This method may return 695adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * different collections when multiple concurrent calls occur, since no 696adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * synchronization is performed. 69719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * </p> 698f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 699adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return a collection of the values contained in this map. 700adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 70119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public Collection<V> values() { 70219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch Collection<V> vs = values; 70319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return (vs != null) ? vs : (values = new Values()); 70419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 705adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 70619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 70719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Returns a set containing all of the mappings in this map. Each mapping is 70819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * an instance of {@link Map.Entry}. As the set is backed by this map, 70919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * changes in one will be reflected in the other. 71019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * 71119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * @return a set of the mappings. 71219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 71319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public Set<Entry<K, V>> entrySet() { 71419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch Set<Entry<K, V>> es = entrySet; 71519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return (es != null) ? es : (entrySet = new EntrySet()); 71619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 717adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 71819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch static class HashMapEntry<K, V> implements Entry<K, V> { 71919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch final K key; 72019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch V value; 72119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch final int hash; 72219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> next; 72319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 72419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) { 72519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch this.key = key; 72619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch this.value = value; 72719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch this.hash = hash; 72819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch this.next = next; 72919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 73019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 73119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public final K getKey() { 73219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return key; 73319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 73419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 73519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public final V getValue() { 73619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return value; 73719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 73819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 73919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public final V setValue(V value) { 74019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch V oldValue = this.value; 74119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch this.value = value; 74219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return oldValue; 74319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 74419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 74519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public final boolean equals(Object o) { 74619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (!(o instanceof Entry)) { 74719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return false; 74819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 74919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch Entry<?, ?> e = (Entry<?, ?>) o; 750e32b21f14d52bac429a9c54fe031f9e92c911d64Jesse Wilson return Objects.equal(e.getKey(), key) 751e32b21f14d52bac429a9c54fe031f9e92c911d64Jesse Wilson && Objects.equal(e.getValue(), value); 75219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 75319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 75419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public final int hashCode() { 75519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return (key == null ? 0 : key.hashCode()) ^ 75619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch (value == null ? 0 : value.hashCode()); 75719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 75819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 75919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @Override public final String toString() { 76019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return key + "=" + value; 76119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 76219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 76319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 76419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private abstract class HashIterator { 765c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int nextIndex; 76619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> nextEntry = entryForNullKey; 767c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashMapEntry<K, V> lastEntryReturned; 76819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int expectedModCount = modCount; 76919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 77019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashIterator() { 77119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (nextEntry == null) { 77219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] tab = table; 77319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> next = null; 77419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch while (next == null && nextIndex < tab.length) { 77519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch next = tab[nextIndex++]; 776adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 77719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch nextEntry = next; 77819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 77919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 78019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 78119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public boolean hasNext() { 78219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return nextEntry != null; 78319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 78419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 78519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> nextEntry() { 78619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (modCount != expectedModCount) 78719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch throw new ConcurrentModificationException(); 78819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (nextEntry == null) 78919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch throw new NoSuchElementException(); 79019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 79119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> entryToReturn = nextEntry; 79219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] tab = table; 79319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> next = entryToReturn.next; 79419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch while (next == null && nextIndex < tab.length) { 79519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch next = tab[nextIndex++]; 79619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 79719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch nextEntry = next; 79819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return lastEntryReturned = entryToReturn; 79919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 80019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 80119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public void remove() { 80219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (lastEntryReturned == null) 80319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch throw new IllegalStateException(); 80419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (modCount != expectedModCount) 80519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch throw new ConcurrentModificationException(); 80619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMap.this.remove(lastEntryReturned.key); 80719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch lastEntryReturned = null; 80819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch expectedModCount = modCount; 80919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 81019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 81119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 81219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private final class KeyIterator extends HashIterator 81319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch implements Iterator<K> { 81419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public K next() { return nextEntry().key; } 81519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 816adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 81719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private final class ValueIterator extends HashIterator 81819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch implements Iterator<V> { 81919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public V next() { return nextEntry().value; } 82019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 82119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 82219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private final class EntryIterator extends HashIterator 82319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch implements Iterator<Entry<K, V>> { 82419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public Entry<K, V> next() { return nextEntry(); } 82519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 82619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 82719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 82819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Returns true if this map contains the specified mapping. 82919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 83019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private boolean containsMapping(Object key, Object value) { 83119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (key == null) { 83219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> e = entryForNullKey; 833e32b21f14d52bac429a9c54fe031f9e92c911d64Jesse Wilson return e != null && Objects.equal(value, e.value); 83419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 83519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 83644bc12dfe2e22cfb86dd619f35f040f3e0628aabElliott Hughes int hash = Collections.secondaryHash(key); 83719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] tab = table; 83819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int index = hash & (tab.length - 1); 83919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) { 84019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (e.hash == hash && key.equals(e.key)) { 841e32b21f14d52bac429a9c54fe031f9e92c911d64Jesse Wilson return Objects.equal(value, e.value); 84219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 84319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 84419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return false; // No entry for key 84519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 84619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 84719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch /** 84819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * Removes the mapping from key to value and returns true if this mapping 84919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch * exists; otherwise, returns does nothing and returns false. 85019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch */ 85119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private boolean removeMapping(Object key, Object value) { 85219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (key == null) { 85319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V> e = entryForNullKey; 854e32b21f14d52bac429a9c54fe031f9e92c911d64Jesse Wilson if (e == null || !Objects.equal(value, e.value)) { 85519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return false; 85619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 85719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch entryForNullKey = null; 85819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch modCount++; 85919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch size--; 86019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch postRemove(e); 86119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return true; 86219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 86319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 86444bc12dfe2e22cfb86dd619f35f040f3e0628aabElliott Hughes int hash = Collections.secondaryHash(key); 86519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMapEntry<K, V>[] tab = table; 86619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int index = hash & (tab.length - 1); 86719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (HashMapEntry<K, V> e = tab[index], prev = null; 86819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch e != null; prev = e, e = e.next) { 86919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (e.hash == hash && key.equals(e.key)) { 870e32b21f14d52bac429a9c54fe031f9e92c911d64Jesse Wilson if (!Objects.equal(value, e.value)) { 87119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return false; // Map has wrong value for key 872adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 87319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (prev == null) { 87419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch tab[index] = e.next; 87519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } else { 87619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch prev.next = e.next; 87719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 87819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch modCount++; 87919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch size--; 88019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch postRemove(e); 88119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return true; 88219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 883adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 88419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return false; // No entry for key 885adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 886adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 887438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes // Subclass (LinkedHashMap) overrides these for correct iteration order 88819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch Iterator<K> newKeyIterator() { return new KeyIterator(); } 88919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch Iterator<V> newValueIterator() { return new ValueIterator(); } 89019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch Iterator<Entry<K, V>> newEntryIterator() { return new EntryIterator(); } 89119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 89219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private final class KeySet extends AbstractSet<K> { 89319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public Iterator<K> iterator() { 89419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return newKeyIterator(); 89519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 89619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public int size() { 89719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return size; 89819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 89919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public boolean isEmpty() { 90019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return size == 0; 90119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 90219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public boolean contains(Object o) { 90319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return containsKey(o); 90419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 90519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public boolean remove(Object o) { 90619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int oldSize = size; 90719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMap.this.remove(o); 90819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return size != oldSize; 90919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 91019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public void clear() { 91119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMap.this.clear(); 912adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 913adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 914adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 91519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private final class Values extends AbstractCollection<V> { 91619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public Iterator<V> iterator() { 91719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return newValueIterator(); 91819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 91919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public int size() { 92019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return size; 92119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 92219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public boolean isEmpty() { 92319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return size == 0; 92419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 92519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public boolean contains(Object o) { 92619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return containsValue(o); 92719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 92819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public void clear() { 92919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMap.this.clear(); 93019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 93119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 93219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 93319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private final class EntrySet extends AbstractSet<Entry<K, V>> { 93419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public Iterator<Entry<K, V>> iterator() { 93519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return newEntryIterator(); 93619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 93719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public boolean contains(Object o) { 93819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (!(o instanceof Entry)) 93919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return false; 94019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch Entry<?, ?> e = (Entry<?, ?>) o; 94119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return containsMapping(e.getKey(), e.getValue()); 94219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 94319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public boolean remove(Object o) { 94419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (!(o instanceof Entry)) 94519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return false; 94619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch Entry<?, ?> e = (Entry<?, ?>)o; 94719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return removeMapping(e.getKey(), e.getValue()); 94819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 94919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public int size() { 95019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return size; 95119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 95219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public boolean isEmpty() { 95319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch return size == 0; 95419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 95519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch public void clear() { 95619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch HashMap.this.clear(); 957adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 958adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 959adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 96019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private static final long serialVersionUID = 362498820763181265L; 96119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 96219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private static final ObjectStreamField[] serialPersistentFields = { 963e26ba79900d471d02d656f686926918ef7dc751fElliott Hughes new ObjectStreamField("loadFactor", float.class) 96419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch }; 96519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 96619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private void writeObject(ObjectOutputStream stream) throws IOException { 96719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch // Emulate loadFactor field for other implementations to read 96819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch ObjectOutputStream.PutField fields = stream.putFields(); 96919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch fields.put("loadFactor", DEFAULT_LOAD_FACTOR); 97019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch stream.writeFields(); 97119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 97219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch stream.writeInt(table.length); // Capacity 97319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch stream.writeInt(size); 97419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (Entry<K, V> e : entrySet()) { 97519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch stream.writeObject(e.getKey()); 97619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch stream.writeObject(e.getValue()); 97719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 978f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 979f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 98019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch private void readObject(ObjectInputStream stream) throws IOException, 98119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch ClassNotFoundException { 98219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch stream.defaultReadObject(); 98319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int capacity = stream.readInt(); 98419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (capacity < 0) { 98519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch throw new InvalidObjectException("Capacity: " + capacity); 98619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 98719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (capacity < MINIMUM_CAPACITY) { 98819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch capacity = MINIMUM_CAPACITY; 98919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } else if (capacity > MAXIMUM_CAPACITY) { 99019ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch capacity = MAXIMUM_CAPACITY; 99119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } else { 9921424a2a1a9fc53dc8b859a77c02c924d3dc2334dIan Rogers capacity = Collections.roundUpToPowerOfTwo(capacity); 99319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 99419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch makeTable(capacity); 99519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch 99619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch int size = stream.readInt(); 99719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch if (size < 0) { 99819ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch throw new InvalidObjectException("Size: " + size); 99919ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 1000f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 100119ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch init(); // Give subclass (LinkedHashMap) a chance to initialize itself 100219ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch for (int i = 0; i < size; i++) { 100319ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @SuppressWarnings("unchecked") K key = (K) stream.readObject(); 100419ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch @SuppressWarnings("unchecked") V val = (V) stream.readObject(); 100519ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch constructorPut(key, val); 100619ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 100719ab821c3b1da5812590140a21ad9d551a3a3ec5Joshua Bloch } 1008adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 1009