本文共 41233 字，大约阅读时间需要 137 分钟。

1.    HashMap概述：

   HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

 

2.    HashMap的数据结构：

   在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

   从上图中可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。

   源码如下：

   可以看出，Entry就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用，这就构成了链表。

 

3.    HashMap的存取实现：

   1) 存储：

   从上面的源代码中可以看出：当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

   addEntry(hash, key, value, i)方法根据计算出的hash值，将key-value对放在数组table的i索引处。addEntry 是HashMap 提供的一个包访问权限的方法，代码如下：

   当系统决定存储HashMap中的key-value对时，完全没有考虑Entry中的value，仅仅只是根据key来计算并决定每个Entry的存储位置。我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可。

   hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的hash冲突。

 

   我们可以看到在HashMap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的 元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。

   对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(int h) 方法所计算得到的 hash 码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，在HashMap中是这样做的：调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下：

 

   这个方法非常巧妙，它通过 h & (table.length -1) 来得到该对象的保存位，而HashMap底层数组的长度总是 2 的n 次方，这是HashMap在速度上的优化。在 HashMap 构造器中有如下代码：

   这段代码保证初始化时HashMap的容量总是2的n次方，即底层数组的长度总是为2的n次方。

当length总是 2 的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

   这看上去很简单，其实比较有玄机的，我们举个例子来说明：

   假设数组长度分别为15和16，优化后的hash码分别为8和9，那么&运算后的结果如下：

       h & (table.length-1)                     hash                             table.length-1

       8 & (15-1)：                                 0100                   &              1110                   =                0100

       9 & (15-1)：                                 0101                   &              1110                   =                0100

       -----------------------------------------------------------------------------------------------------------------------

       8 & (16-1)：                                 0100                   &              1111                   =                0100

       9 & (16-1)：                                 0101                   &              1111                   =                0101

  

   从上面的例子中可以看出：当它们和15-1（1110）“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到数组中的同一个位置上形成链表，那么查询的时候就需要遍历这个链 表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hash值会与15-1（1110）进行“与”，那么 最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！而当数组长度为16时，即为2的n次方时，2ⁿ-1得到的二进制数的每个位上的值都为1，这使得在低位上&时，得到的和原hash的低位相同，加之hash(int h)方法对key的hashCode的进一步优化，加入了高位计算，就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。

   

   所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

   根据上面 put 方法的源代码可以看出，当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有Entry 的 value，但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。

   2) 读取：

 

   有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

  

   3) 归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

 

4.    HashMap的resize（rehash）：

   当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

   那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

 

5.    HashMap的性能参数：

   HashMap 包含如下几个构造器：

   HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。

   HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。

   HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。

   HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。

   initialCapacity：HashMap的最大容量，即为底层数组的长度。

   loadFactor：负载因子loadFactor定义为：散列表的实际元素数目(n)/ 散列表的容量(m)。

   负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。

   HashMap的实现中，通过threshold字段来判断HashMap的最大容量：

   结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是容量的两倍：

 

 

6.    Fail-Fast机制：

   我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

   这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

 

   在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：

   注意到modCount声明为volatile，保证线程之间修改的可见性。

 

   在HashMap的API中指出：

   由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。

   注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

以上内容转自：http://zhangshixi.iteye.com/blog/672697

根据上述内容，阅读了HashMap的源码；

/* * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. * * * * * * * * * * * * * * * * * * * * */package java.util;import java.io.*;/** * Hash table based implementation of the Map interface.  This * implementation provides all of the optional map operations, and permits * null values and the null key.  (The HashMap * class is roughly equivalent to Hashtable, except that it is * unsynchronized and permits nulls.)  This class makes no guarantees as to * the order of the map; in particular, it does not guarantee that the order * will remain constant over time. * * 
This implementation provides constant-time performance for the basic * operations (get and put), assuming the hash function * disperses the elements properly among the buckets.  Iteration over * collection views requires time proportional to the "capacity" of the * HashMap instance (the number of buckets) plus its size (the number * of key-value mappings).  Thus, it's very important not to set the initial * capacity too high (or the load factor too low) if iteration performance is * important. * * 
An instance of HashMap has two parameters that affect its * performance: initial capacity and load factor.  The * capacity is the number of buckets in the hash table, and the initial * capacity is simply the capacity at the time the hash table is created.  The * load factor is a measure of how full the hash table is allowed to * get before its capacity is automatically increased.  When the number of * entries in the hash table exceeds the product of the load factor and the * current capacity, the hash table is rehashed (that is, internal data * structures are rebuilt) so that the hash table has approximately twice the * number of buckets. * * 
As a general rule, the default load factor (.75) offers a good tradeoff * between time and space costs.  Higher values decrease the space overhead * but increase the lookup cost (reflected in most of the operations of the * HashMap class, including get and put).  The * expected number of entries in the map and its load factor should be taken * into account when setting its initial capacity, so as to minimize the * number of rehash operations.  If the initial capacity is greater * than the maximum number of entries divided by the load factor, no * rehash operations will ever occur. * * 
If many mappings are to be stored in a HashMap instance, * creating it with a sufficiently large capacity will allow the mappings to * be stored more efficiently than letting it perform automatic rehashing as * needed to grow the table. * * 
Note that this implementation is not synchronized. * If multiple threads access a hash map concurrently, and at least one of * the threads modifies the map structurally, it must be * synchronized externally.  (A structural modification is any operation * that adds or deletes one or more mappings; merely changing the value * associated with a key that an instance already contains is not a * structural modification.)  This is typically accomplished by * synchronizing on some object that naturally encapsulates the map. * * If no such object exists, the map should be "wrapped" using the * {@link Collections#synchronizedMap Collections.synchronizedMap} * method.  This is best done at creation time, to prevent accidental * unsynchronized access to the map:
 *   Map m = Collections.synchronizedMap(new HashMap(...));
 * * 
The iterators returned by all of this class's "collection view methods" * are fail-fast: if the map is structurally modified at any time after * the iterator is created, in any way except through the iterator's own * remove method, the iterator will throw a * {@link ConcurrentModificationException}.  Thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than risking * arbitrary, non-deterministic behavior at an undetermined time in the * future. * * 
Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification.  Fail-fast iterators * throw ConcurrentModificationException on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: the fail-fast behavior of iterators * should be used only to detect bugs. * * 
This class is a member of the *  * Java Collections Framework. * * @param 
    
      the type of keys maintained by this map * @param 
     
       the type of mapped values * * @author  Doug Lea * @author  Josh Bloch * @author  Arthur van Hoff * @author  Neal Gafter * @see     Object#hashCode() * @see     Collection * @see     Map * @see     TreeMap * @see     Hashtable * @since   1.2 */public class HashMap
      
           extends AbstractMap
       
        	//继承AbstractMap 一个抽象类    implements Map
        
         , Cloneable, Serializable //实现Map接口，Cloneable接口，Serializable接口{ /** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * An empty table instance to share when the table is not inflated. */ static final Entry
         [] EMPTY_TABLE = {}; /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry
         
          [] table = (Entry
          
           []) EMPTY_TABLE; /** * The number of key-value mappings contained in this map. */ transient int size; /** * The next size value at which to resize (capacity * load factor). * @serial */ // If table == EMPTY_TABLE then this is the initial capacity at which the // table will be created when inflated. int threshold; //容量乘以加载因子 /** * The load factor for the hash table. * * @serial */ final float loadFactor; /** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */ transient int modCount; /** * The default threshold of map capacity above which alternative hashing is * used for String keys. Alternative hashing reduces the incidence of * collisions due to weak hash code calculation for String keys. * 
          
         
        
       
      
     
    
     * This value may be overridden by defining the system property     * {@code jdk.map.althashing.threshold}. A property value of {@code 1}     * forces alternative hashing to be used at all times whereas     * {@code -1} value ensures that alternative hashing is never used.     */    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;    /**     * holds values which can't be initialized until after VM is booted.     */    private static class Holder {        /**         * Table capacity above which to switch to use alternative hashing.         */        static final int ALTERNATIVE_HASHING_THRESHOLD;        static {            String altThreshold = java.security.AccessController.doPrivileged(                new sun.security.action.GetPropertyAction(                    "jdk.map.althashing.threshold"));            int threshold;            try {                threshold = (null != altThreshold)                        ? Integer.parseInt(altThreshold)                        : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;                // disable alternative hashing if -1                if (threshold == -1) {                    threshold = Integer.MAX_VALUE;                }                if (threshold < 0) {                    throw new IllegalArgumentException("value must be positive integer.");                }            } catch(IllegalArgumentException failed) {                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);            }            ALTERNATIVE_HASHING_THRESHOLD = threshold;	//在static同步块中对static final变量赋值        }    }    /**     * A randomizing value associated with this instance that is applied to     * hash code of keys to make hash collisions harder to find. If 0 then     * alternative hashing is disabled.     */    transient int hashSeed = 0;	//transient关键字？？？    /**     * Constructs an empty HashMap with the specified initial     * capacity and load factor.     *     * @param  initialCapacity the initial capacity     * @param  loadFactor      the load factor     * @throws IllegalArgumentException if the initial capacity is negative     *         or the load factor is nonpositive     */    public HashMap(int initialCapacity, float loadFactor) {        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +                                               initialCapacity);        if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +                                               loadFactor);        this.loadFactor = loadFactor;        threshold = initialCapacity;        init();    }    /**     * Constructs an empty HashMap with the specified initial     * capacity and the default load factor (0.75).     *     * @param  initialCapacity the initial capacity.     * @throws IllegalArgumentException if the initial capacity is negative.     */    public HashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_LOAD_FACTOR);    }    /**     * Constructs an empty HashMap with the default initial capacity     * (16) and the default load factor (0.75).     */    public HashMap() {        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);    }    /**     * Constructs a new HashMap with the same mappings as the     * specified Map.  The HashMap is created with     * default load factor (0.75) and an initial capacity sufficient to     * hold the mappings in the specified Map.     *     * @param   m the map whose mappings are to be placed in this map     * @throws  NullPointerException if the specified map is null     */    public HashMap(Map
    m) {        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);        inflateTable(threshold);        putAllForCreate(m);    }    private static int roundUpToPowerOf2(int number) {        // assert number >= 0 : "number must be non-negative";        int rounded = number >= MAXIMUM_CAPACITY                ? MAXIMUM_CAPACITY                : (rounded = Integer.highestOneBit(number)) != 0                    ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded                    : 1;        return rounded;    }    /**     * Inflates the table.     */    private void inflateTable(int toSize) {        // Find a power of 2 >= toSize        int capacity = roundUpToPowerOf2(toSize);        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);        table = new Entry[capacity];        initHashSeedAsNeeded(capacity);    }    // internal utilities    /**     * Initialization hook for subclasses. This method is called     * in all constructors and pseudo-constructors (clone, readObject)     * after HashMap has been initialized but before any entries have     * been inserted.  (In the absence of this method, readObject would     * require explicit knowledge of subclasses.)     */    void init() {    }    /**     * Initialize the hashing mask value. We defer initialization until we     * really need it.     */    final boolean initHashSeedAsNeeded(int capacity) {        boolean currentAltHashing = hashSeed != 0;        boolean useAltHashing = sun.misc.VM.isBooted() &&                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);        boolean switching = currentAltHashing ^ useAltHashing;        if (switching) {            hashSeed = useAltHashing                ? sun.misc.Hashing.randomHashSeed(this)                : 0;        }        return switching;    }    /**     * Retrieve object hash code and applies a supplemental hash function to the     * result hash, which defends against poor quality hash functions.  This is     * critical because HashMap uses power-of-two length hash tables, that     * otherwise encounter collisions for hashCodes that do not differ     * in lower bits. Note: Null keys always map to hash 0, thus index 0.     */    final int hash(Object k) {        int h = hashSeed;        if (0 != h && k instanceof String) {            return sun.misc.Hashing.stringHash32((String) k);        }        h ^= k.hashCode();        // This function ensures that hashCodes that differ only by        // constant multiples at each bit position have a bounded        // number of collisions (approximately 8 at default load factor).        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    /**     * Returns index for hash code h.     */    static int indexFor(int h, int length) {        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";        return h & (length-1);    }    /**     * Returns the number of key-value mappings in this map.     *     * @return the number of key-value mappings in this map     */    public int size() {        return size;    }    /**     * Returns true if this map contains no key-value mappings.     *     * @return true if this map contains no key-value mappings     */    public boolean isEmpty() {        return size == 0;    }    /**     * Returns the value to which the specified key is mapped,     * or {@code null} if this map contains no mapping for the key.     *     * 
More formally, if this map contains a mapping from a key     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :     * key.equals(k))}, then this method returns {@code v}; otherwise     * it returns {@code null}.  (There can be at most one such mapping.)     *     * 
A return value of {@code null} does not necessarily     * indicate that the map contains no mapping for the key; it's also     * possible that the map explicitly maps the key to {@code null}.     * The {@link #containsKey containsKey} operation may be used to     * distinguish these two cases.     *     * @see #put(Object, Object)     */    public V get(Object key) {        if (key == null)            return getForNullKey();        Entry
    
      entry = getEntry(key);        return null == entry ? null : entry.getValue();    }    /**     * Offloaded version of get() to look up null keys.  Null keys map     * to index 0.  This null case is split out into separate methods     * for the sake of performance in the two most commonly used     * operations (get and put), but incorporated with conditionals in     * others.     */    private V getForNullKey() {        if (size == 0) {            return null;        }        for (Entry
     
       e = table[0]; e != null; e = e.next) {            if (e.key == null)                return e.value;        }        return null;    }    /**     * Returns 
      true if this map contains a mapping for the     * specified key.     *     * @param   key   The key whose presence in this map is to be tested     * @return 
      true if this map contains a mapping for the specified     * key.     */    public boolean containsKey(Object key) {        return getEntry(key) != null;    }    /**     * Returns the entry associated with the specified key in the     * HashMap.  Returns null if the HashMap contains no mapping     * for the key.     */    final Entry
      
        getEntry(Object key) {        if (size == 0) {            return null;        }        int hash = (key == null) ? 0 : hash(key);        for (Entry
       
         e = table[indexFor(hash, table.length)];             e != null;             e = e.next) {            Object k;            if (e.hash == hash &&                ((k = e.key) == key || (key != null && key.equals(k))))                return e;        }        return null;    }    /**     * Associates the specified value with the specified key in this map.     * If the map previously contained a mapping for the key, the old     * value is replaced.     *     * @param key key with which the specified value is to be associated     * @param value value to be associated with the specified key     * @return the previous value associated with 
        key, or     *         
        null if there was no mapping for 
        key.     *         (A 
        null return can also indicate that the map     *         previously associated 
        null with 
        key.)     */    public V put(K key, V value) {        if (table == EMPTY_TABLE) {            inflateTable(threshold);        }        if (key == null)            return putForNullKey(value);        int hash = hash(key);        int i = indexFor(hash, table.length);        for (Entry
        
          e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; } /** * Offloaded version of put for null keys */ private V putForNullKey(V value) { for (Entry
         
           e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; } /** * This method is used instead of put by constructors and * pseudoconstructors (clone, readObject). It does not resize the table, * check for comodification, etc. It calls createEntry rather than * addEntry. */ private void putForCreate(K key, V value) { int hash = null == key ? 0 : hash(key); int i = indexFor(hash, table.length); /** * Look for preexisting entry for key. This will never happen for * clone or deserialize. It will only happen for construction if the * input Map is a sorted map whose ordering is inconsistent w/ equals. */ for (Entry
          
            e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { e.value = value; return; } } createEntry(hash, key, value, i); } private void putAllForCreate(Map
            m) { for (Map.Entry
            e : m.entrySet()) putForCreate(e.getKey(), e.getValue()); } /** * Rehashes the contents of this map into a new array with a * larger capacity. This method is called automatically when the * number of keys in this map reaches its threshold. * * If current capacity is MAXIMUM_CAPACITY, this method does not * resize the map, but sets threshold to Integer.MAX_VALUE. * This has the effect of preventing future calls. * * @param newCapacity the new capacity, MUST be a power of two; * must be greater than current capacity unless current * capacity is MAXIMUM_CAPACITY (in which case value * is irrelevant). */ void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } /** * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry
           
             e : table) { while(null != e) { Entry
            
              next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } } /** * Copies all of the mappings from the specified map to this map. * These mappings will replace any mappings that this map had for * any of the keys currently in the specified map. * * @param m mappings to be stored in this map * @throws NullPointerException if the specified map is null */ public void putAll(Map
              m) { int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0) return; if (table == EMPTY_TABLE) { inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold)); } /* * Expand the map if the map if the number of mappings to be added * is greater than or equal to threshold. This is conservative; the * obvious condition is (m.size() + size) >= threshold, but this * condition could result in a map with twice the appropriate capacity, * if the keys to be added overlap with the keys already in this map. * By using the conservative calculation, we subject ourself * to at most one extra resize. */ if (numKeysToBeAdded > threshold) { int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); if (targetCapacity > MAXIMUM_CAPACITY) targetCapacity = MAXIMUM_CAPACITY; int newCapacity = table.length; while (newCapacity < targetCapacity) newCapacity <<= 1; if (newCapacity > table.length) resize(newCapacity); } for (Map.Entry
              e : m.entrySet()) put(e.getKey(), e.getValue()); } /** * Removes the mapping for the specified key from this map if present. * * @param key key whose mapping is to be removed from the map * @return the previous value associated with 
             key, or * 
             null if there was no mapping for 
             key. * (A 
             null return can also indicate that the map * previously associated 
             null with 
             key.) */ public V remove(Object key) { Entry
             
               e = removeEntryForKey(key); return (e == null ? null : e.value); } /** * Removes and returns the entry associated with the specified key * in the HashMap. Returns null if the HashMap contains no mapping * for this key. */ final Entry
              
                removeEntryForKey(Object key) { if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); Entry
               
                 prev = table[i]; Entry
                
                  e = prev; while (e != null) { Entry
                 
                   next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; } /** * Special version of remove for EntrySet using {@code Map.Entry.equals()} * for matching. */ final Entry
                  
                    removeMapping(Object o) { if (size == 0 || !(o instanceof Map.Entry)) return null; Map.Entry
                   
                     entry = (Map.Entry
                    
                     ) o; Object key = entry.getKey(); int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); Entry
                     
                       prev = table[i]; Entry
                      
                        e = prev; while (e != null) { Entry
                       
                         next = e.next; if (e.hash == hash && e.equals(entry)) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; } /** * Removes all of the mappings from this map. * The map will be empty after this call returns. */ public void clear() { modCount++; Arrays.fill(table, null); size = 0; } /** * Returns 
                        true if this map maps one or more keys to the * specified value. * * @param value value whose presence in this map is to be tested * @return 
                        true if this map maps one or more keys to the * specified value */ public boolean containsValue(Object value) { if (value == null) return containsNullValue(); Entry[] tab = table; for (int i = 0; i < tab.length ; i++) for (Entry e = tab[i] ; e != null ; e = e.next) if (value.equals(e.value)) return true; return false; } /** * Special-case code for containsValue with null argument */ private boolean containsNullValue() { Entry[] tab = table; for (int i = 0; i < tab.length ; i++) for (Entry e = tab[i] ; e != null ; e = e.next) if (e.value == null) return true; return false; } /** * Returns a shallow copy of this 
                        HashMap instance: the keys and * values themselves are not cloned. * * @return a shallow copy of this map */ public Object clone() { HashMap
                        
                          result = null; try { result = (HashMap
                         
                          )super.clone(); } catch (CloneNotSupportedException e) { // assert false; } if (result.table != EMPTY_TABLE) { result.inflateTable(Math.min( (int) Math.min( size * Math.min(1 / loadFactor, 4.0f), // we have limits... HashMap.MAXIMUM_CAPACITY), table.length)); } result.entrySet = null; result.modCount = 0; result.size = 0; result.init(); result.putAllForCreate(this); return result; } static class Entry
                          
                            implements Map.Entry
                           
                             { final K key; V value; Entry
                            
                              next; int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry
                             
                               n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); } public final String toString() { return getKey() + "=" + getValue(); } /** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that's already * in the HashMap. */ void recordAccess(HashMap
                              
                                m) { } /** * This method is invoked whenever the entry is * removed from the table. */ void recordRemoval(HashMap
                               
                                 m) { } } /** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */ void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } /** * Like addEntry except that this version is used when creating entries * as part of Map construction or "pseudo-construction" (cloning, * deserialization). This version needn't worry about resizing the table. * * Subclass overrides this to alter the behavior of HashMap(Map), * clone, and readObject. */ void createEntry(int hash, K key, V value, int bucketIndex) { Entry
                                
                                  e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; } private abstract class HashIterator
                                 
                                   implements Iterator
                                  
                                    { Entry
                                   
                                     next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry
                                    
                                      current; // current entry HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } public final boolean hasNext() { return next != null; } final Entry
                                     
                                       nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry
                                      
                                        e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } public void remove() { if (current == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); Object k = current.key; current = null; HashMap.this.removeEntryForKey(k); expectedModCount = modCount; } } private final class ValueIterator extends HashIterator
                                       
                                         { public V next() { return nextEntry().value; } } private final class KeyIterator extends HashIterator
                                        
                                          { public K next() { return nextEntry().getKey(); } } private final class EntryIterator extends HashIterator
                                         
                                          
                                           > { public Map.Entry
                                           
                                             next() { return nextEntry(); } } // Subclass overrides these to alter behavior of views' iterator() method Iterator
                                            
                                              newKeyIterator() { return new KeyIterator(); } Iterator
                                             
                                               newValueIterator() { return new ValueIterator(); } Iterator
                                              
                                               
                                                > newEntryIterator() { return new EntryIterator(); } // Views private transient Set
                                                
                                                 
                                                  > entrySet = null; /** * Returns a {@link Set} view of the keys contained in this map. * The set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. If the map is modified * while an iteration over the set is in progress (except through * the iterator's own 
                                                  remove operation), the results of * the iteration are undefined. The set supports element removal, * which removes the corresponding mapping from the map, via the * 
                                                  Iterator.remove, 
                                                  Set.remove, * 
                                                  removeAll, 
                                                  retainAll, and 
                                                  clear * operations. It does not support the 
                                                  add or 
                                                  addAll * operations. */ public Set
                                                  
                                                    keySet() { Set
                                                   
                                                     ks = keySet; return (ks != null ? ks : (keySet = new KeySet())); } private final class KeySet extends AbstractSet
                                                    
                                                      { public Iterator
                                                     
                                                       iterator() { return newKeyIterator(); } public int size() { return size; } public boolean contains(Object o) { return containsKey(o); } public boolean remove(Object o) { return HashMap.this.removeEntryForKey(o) != null; } public void clear() { HashMap.this.clear(); } } /** * Returns a {@link Collection} view of the values contained in this map. * The collection is backed by the map, so changes to the map are * reflected in the collection, and vice-versa. If the map is * modified while an iteration over the collection is in progress * (except through the iterator's own 
                                                      remove operation), * the results of the iteration are undefined. The collection * supports element removal, which removes the corresponding * mapping from the map, via the 
                                                      Iterator.remove, * 
                                                      Collection.remove, 
                                                      removeAll, * 
                                                      retainAll and 
                                                      clear operations. It does not * support the 
                                                      add or 
                                                      addAll operations. */ public Collection
                                                      
                                                        values() { Collection
                                                       
                                                         vs = values; return (vs != null ? vs : (values = new Values())); } private final class Values extends AbstractCollection
                                                        
                                                          { public Iterator
                                                         
                                                           iterator() { return newValueIterator(); } public int size() { return size; } public boolean contains(Object o) { return containsValue(o); } public void clear() { HashMap.this.clear(); } } /** * Returns a {@link Set} view of the mappings contained in this map. * The set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. If the map is modified * while an iteration over the set is in progress (except through * the iterator's own 
                                                          remove operation, or through the * 
                                                          setValue operation on a map entry returned by the * iterator) the results of the iteration are undefined. The set * supports element removal, which removes the corresponding * mapping from the map, via the 
                                                          Iterator.remove, * 
                                                          Set.remove, 
                                                          removeAll, 
                                                          retainAll and * 
                                                          clear operations. It does not support the * 
                                                          add or 
                                                          addAll operations. * * @return a set view of the mappings contained in this map */ public Set
                                                          
                                                           
                                                            > entrySet() { return entrySet0(); } private Set
                                                            
                                                             
                                                              > entrySet0() { Set
                                                              
                                                               
                                                                > es = entrySet; return es != null ? es : (entrySet = new EntrySet()); } private final class EntrySet extends AbstractSet
                                                                
                                                                 
                                                                  > { public Iterator
                                                                  
                                                                   
                                                                    > iterator() { return newEntryIterator(); } public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry
                                                                    
                                                                      e = (Map.Entry
                                                                     
                                                                      ) o; Entry
                                                                      
                                                                        candidate = getEntry(e.getKey()); return candidate != null && candidate.equals(e); } public boolean remove(Object o) { return removeMapping(o) != null; } public int size() { return size; } public void clear() { HashMap.this.clear(); } } /** * Save the state of the 
                                                                       HashMap instance to a stream (i.e., * serialize it). * * @serialData The 
                                                                       capacity of the HashMap (the length of the * bucket array) is emitted (int), followed by the * 
                                                                       size (an int, the number of key-value * mappings), followed by the key (Object) and value (Object) * for each key-value mapping. The key-value mappings are * emitted in no particular order. */ private void writeObject(java.io.ObjectOutputStream s) throws IOException { // Write out the threshold, loadfactor, and any hidden stuff s.defaultWriteObject(); // Write out number of buckets if (table==EMPTY_TABLE) { s.writeInt(roundUpToPowerOf2(threshold)); } else { s.writeInt(table.length); } // Write out size (number of Mappings) s.writeInt(size); // Write out keys and values (alternating) if (size > 0) { for(Map.Entry
                                                                       
                                                                         e : entrySet0()) { s.writeObject(e.getKey()); s.writeObject(e.getValue()); } } } private static final long serialVersionUID = 362498820763181265L; /** * Reconstitute the {@code HashMap} instance from a stream (i.e., * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { // Read in the threshold (ignored), loadfactor, and any hidden stuff s.defaultReadObject(); if (loadFactor <= 0 || Float.isNaN(loadFactor)) { throw new InvalidObjectException("Illegal load factor: " + loadFactor); } // set other fields that need values table = (Entry
                                                                        
                                                                         []) EMPTY_TABLE; // Read in number of buckets s.readInt(); // ignored. // Read number of mappings int mappings = s.readInt(); if (mappings < 0) throw new InvalidObjectException("Illegal mappings count: " + mappings); // capacity chosen by number of mappings and desired load (if >= 0.25) int capacity = (int) Math.min( mappings * Math.min(1 / loadFactor, 4.0f), // we have limits... HashMap.MAXIMUM_CAPACITY); // allocate the bucket array; if (mappings > 0) { inflateTable(capacity); } else { threshold = capacity; } init(); // Give subclass a chance to do its thing. // Read the keys and values, and put the mappings in the HashMap for (int i = 0; i < mappings; i++) { K key = (K) s.readObject(); V value = (V) s.readObject(); putForCreate(key, value); } } // These methods are used when serializing HashSets int capacity() { return table.length; } float loadFactor() { return loadFactor; }}
                                                                        
                                                                       
                                                                      
                                                                     
                                                                    
                                                                   
                                                                  
                                                                 
                                                                
                                                               
                                                              
                                                             
                                                            
                                                           
                                                          
                                                         
                                                        
                                                       
                                                      
                                                     
                                                    
                                                   
                                                  
                                                 
                                                
                                               
                                              
                                             
                                            
                                           
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

转载地址：http://lpuni.baihongyu.com/