HashMap源码分析(JDK1.8)

HashMap简介：

HashMap在底层数据结构上采用了数组＋链表＋红黑树，通过散列映射来存储键值对数据因为在查询上使用散列码（通过键生成一个数字作为数组下标，
这个数字就是hashcode）所以在查询上的访问速度比较快，HashMap最多允许一对键值对的Key为Null，允许多对键值对的value为Null。
它是非线程安全的。在排序上面是无序的。

HashMap的主要成员变量：

transient Node<K,V>[] table：这是一个Node类型的数组（也有称作Hash桶），可以从下面源码中看到静态内部类Node在这边可以看做就是一个节点，多个Node节点构成链表，当链表长度大于8的时候转换为红黑树。

transient int size：表示当前HashMap包含的键值对数量

transient int modCount：表示当前HashMap修改次数

int threshold：表示当前HashMap能够承受的最多的键值对数量，一旦超过这个数量HashMap就会进行扩容

final float loadFactor：负载因子，用于扩容

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4：默认的table初始容量

static final float DEFAULT_LOAD_FACTOR = 0.75f：默认的负载因子

介绍完了重要的几个参数后我们来看看HashMap的构造参数。

HashMap的构造方法有四种：

详细代码：

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;
    this.threshold = tableSizeFor(initialCapacity);
}
 
 
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
 
 
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
 
 
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

前面三个构造器的区别都是在于指定初始容量以及负载因子，如果你选择默认的构造器那么在创建的时候不会指定threshold的值，而第二个以及第三个构造器在一开始的时候就会根据下面的这个方法来确认threshold值，可以看到下面用到了移位算法，最后一个构造器很显然就是把另一个Map的值映射到当前新的Map中。

这边先提下负载因子（loadFactor），源码中有个公式为threshold = loadFactor * 容量。HashMap和HashSet都允许你指定负载因子的构造器，表示当负载情况达到负载因子水平的时候，容器会自动扩容，HashMap默认使用的负载因子值为0.75f（当容量达到四分之三进行再散列（扩容））。当负载因子越大的时候能够容纳的键值对就越多但是查找的代价也会越高。所以如果你知道将要在HashMap中存储多少数据，那么你可以创建一个具有恰当大小的初始容量这可以减少扩容时候的开销。但是大多数情况下0.75在时间跟空间代价上达到了平衡所以不建议修改。

下面将根据默认的构造为出发点，从初始化一个HashMap到使用Get，Put方法进行一些源码解析。

put(K key, V value)：

在使用默认构造器初始化一个HashMap对象的时候，首次Put键值对的时候会先计算对应
Key的hash值通过hash值来确定存放的地址。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

紧接着调用了putVal方法，在刚刚初始化之后的table值为null因此程序会进入到resize()方法中。而resize方法就是用来进行扩容的（稍后提到）。扩容后得到了一个table的节点（Node）数组，接着根据传入的hash值去获得一个对应节点p并去判断是否为空，是的话就存入一个新的节点（Node）。反之如果当前存放的位置已经有值了就会进入到else中去。接着根据前面得到的节点p的hash值以及key跟传入的hash值以及参数进行比较，如果一样则替覆盖。如果存在Hash碰撞就会以链表的形式保存，把当前传进来的参数生成一个新的节点保存在链表的尾部（JDK1.7保存在首部）。而如果链表的长度大于8那么就会以红黑树的形式进行保存。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0) //首次初始化的时候table为null
        n = (tab = resize()).length; //对HashMap进行扩容
    if ((p = tab[i = (n - 1) & hash]) == null) //根据hash值来确认存放的位置。如果当前位置是空直接添加到table中
        tab[i] = newNode(hash, key, value, null);
    else {
        //如果存放的位置已经有值
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; //确认当前table中存放键值对的Key是否跟要传入的键值对key一致
        else if (p instanceof TreeNode) //确认是否为红黑树
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {//如果hashCode一样的两个不同Key就会以链表的形式保存
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 判断链表长度是否大于8
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
            
            if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value; //替换新的value并返回旧的value
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();//如果当前HashMap的容量超过threshold则进行扩容
    afterNodeInsertion(evict);
    return null;
}

扩容机制核心方法Node<K,V>[] resize()：

HashMap扩容可以分为三种情况：

第一种：使用默认构造方法初始化HashMap。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table，并且thershold为0。因此第一次扩容的容量为默认值DEFAULT_INITIAL_CAPACITY也就是16。同时threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。

第二种：指定初始容量的构造方法初始化HashMap。那么从下面源码可以看到初始容量会等于threshold，接着threshold = 当前的容量（threshold） * DEFAULT_LOAD_FACTOR。

第三种：HashMap不是第一次扩容。如果HashMap已经扩容过的话，那么每次table的容量以及threshold量为原有的两倍。

这边也可以引申到一个问题就是HashMap是先插入数据再进行扩容的，但是如果是刚刚初始化容器的时候是先扩容再插入数据。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;//首次初始化后table为Null
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;//默认构造器的情况下为0
    int newCap, newThr = 0;
    if (oldCap > 0) {//table扩容过
         //当前table容量大于最大值得时候返回当前table
         if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
        //table的容量乘以2，threshold的值也乘以2           
        newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
    //使用带有初始容量的构造器时，table容量为初始化得到的threshold
    newCap = oldThr;
    else {  //默认构造器下进行扩容  
         // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
    //使用带有初始容量的构造器在此处进行扩容
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
  if (oldTab != null) {
    //对新扩容后的table进行赋值，条件中的代码删减
    }
    return newTab;
}

get(Object key)：

先前HashMap通过hashcode来存放数据，那么get方法一样要通过hashcode来获取数据。可以看到如果当前table没有数据的话直接返回null反之通过传进来的hash值找到对应节点（Node）first，如果first的hash值以及Key跟传入的参数匹配就返回对应的value反之判断是否是红黑树，如果是红黑树则从根节点开始进行匹配如果有对应的数据则结果否则返回Null，如果是链表的话就会循环查询链表，如果当前的节点不匹配的话就会从当前节点获取下一个节点来进行循环匹配，如果有对应的数据则返回结果否则返回Null。

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //如果当前table没有数据的话返回Null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //根据当前传入的hash值以及参数key获取一个节点即为first,如果匹配的话返回对应的value值
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //如果参数与first的值不匹配的话
        if ((e = first.next) != null) {
            //判断是否是红黑树，如果是红黑树的话先判断first是否还有父节点，然后从根节点循环查询是否有对应的值
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
            //如果是链表的话循环拿出数据
            if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

JDK1.8对HashMap进行了优化， 真正理解它了吗？

考虑如下问题： 

1、哈希基本原理？（答：散列表、hash碰撞、链表、红黑树）

2、hashmap查询的时间复杂度， 影响因素和原理？ （答：最好O（1），最差O（n）， 如果是红黑O（logn））

3、resize如何实现的， 记住已经没有rehash了！！！（答：拉链entry根据高位bit散列到当前位置i和size+i位置）

4、为什么获取下标时用按位与&，而不是取模%？ （答：不只是&速度更快哦，  我觉得你能答上来便真正理解hashmap了）

5、什么时机执行resize？

答：hashmap实例里的元素个数大于threshold时执行resize(即桶数量扩容为2倍并散列原来的Entry)。 PS：threshold=桶数量*负载因子

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;   //初始化桶，默认16个元素
    if ((p = tab[i = (n - 1) & hash]) == null)   //如果第i个桶为空，创建Node实例
        tab[i] = newNode(hash, key, value, null);
    else { //哈希碰撞的情况， 即(n-1)&hash相等
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;   //key相同，后面会覆盖value
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  //红黑树添加当前node
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);  //链表添加当前元素
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);  //当链表个数大于等于7时，将链表改造为红黑树
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;            //覆盖key相同的value并return， 即不会执行++size
        }
    }
    ++modCount;
    if (++size > threshold)    //key不相同时，每次插入一条数据自增1. 当size大于threshold时resize
        resize();
    afterNodeInsertion(evict);
    return null;
}

6、为什么负载因子默认为0.75f ？ 能不能变为0.1、0.9、2、3等等呢？

答：0.75是平衡了时间和空间等因素； 负载因子越小桶的数量越多，读写的时间复杂度越低（极限情况O(1), 哈希碰撞的可能性越小）； 负载因子越大桶的数量越少，读写的时间复杂度越高(极限情况O(n), 哈希碰撞可能性越高)。 0.1，0.9，2，3等都是合法值。

7、影响HashMap性能的因素？

1、 负载因子；

2、哈希值；理想情况是均匀的散列到各个桶。 一般HashMap使用String类型作为key，而String类重写了hashCode函数。

   static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

8、HashMap的key需要满足什么条件？ 

答：必须重写hashCode和equals方法， 常用的String类实现了这两个方法。

示例代码：

    private static class KeyClass {
        int age;
        String name;
 
        public boolean equals(Object anyObject) {
            if (anyObject == this) {
                return true;
            }
 
            if (anyObject instanceof KeyClass) {
                KeyClass obj = (KeyClass) anyObject;
                if (obj.age == this.age
                        && obj.name == this.name) {
                    return true;
                }
            }
            return false;
        }
 
        public int hashCode() {
            return name==null? age : age|name.hashCode();
        }
    }
 
    public static void main(String[] args) {
        HashMap<KeyClass, String> map = new HashMap<>();
        KeyClass obj1 = new KeyClass();
        KeyClass obj2 = new KeyClass();
        obj1.age = 1;
        obj1.name = "Tom";
        obj2.age = 2;
        obj2.name ="Jack";
        map.put(obj1, "aaa");
        map.put(obj2, "bbb");
        map.put(obj1, "ccc");
        map.put(obj2, "ddd");
 
        map.forEach((key, value) -> {
            System.out.println(key.name + "---" + value);
        });
    }

输出：

Tom---ccc
Jack---ddd

9、HashMap允许key/value为null， 但最多只有一个。 为什么？  

答： 如果key为null会放在第一个桶（即下标0）位置， 而且是在链表最前面（即第一个位置）。 

JDK1.8的HashMap源码： http://www.grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/HashMap.java#HashMap

        我的习惯是先看注释再看源码并调试， 先翻译一下源码注释吧， 不准之处请指正哈。

Hash table based implementation of the Map interface. This implementation provides all of the optional map

   HashTable实现了Map接口类， 这些接口实现了所有可选的map功能， 包括允许空值和空key。

operations, and permits null values and thenull key. (TheHashMap class is roughly equivalent toHashtable, 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.

       HashMap和HashTable基本一致，  区别是HashMap是线程不同步的且允许空key。 HashMap不保证map的顺序， 而且顺序是可变的。

This implementation provides constant-time performance for the basic operations (get andput), assuming the hash function disperses the elements properly among the buckets.

    如果将数据适当的分散到桶里， HashMap的添加、查询函数的执行周期是常量值。

Iteration over collection views requires time proportional to the "capacity" of theHashMap 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.

    使用迭代器遍历所有数据的性能跟HashMap的桶（bucket）数量有直接关系，   为了提高遍历的性能， 不能设置比较大的桶数量或者负载因子过低。

An instance of HashMap has two parameters that affect its performance:initial capacity andload factor. Thecapacity 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.

      HashMap实例有2个重要参数影响它的性能： 初始容量和负载因子。 初始容量是指在哈希表里的桶总数， 一般在创建HashMap实例时设置初始容量。

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 isrehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

       当哈希表的数据个数超过负载因子和当前容量的乘积时， 哈希表要再做一次哈希（重建内部数据结构）， 哈希表每次扩容为原来的2倍。

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 theHashMap class, including get and put).

        负载因子的默认值是0.75， 它平衡了时间和空间复杂度。 负载因子越大会降低空间使用率，但提高了查询性能（表现在哈希表的大多数操作是读取和查询）

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.

       考虑哈希表的性能问题， 要设置合适的初始容量，   从而减少rehash的次数。 当哈希表中entry的总数少于负载因子和初始容量乘积时， 就不会发生rehash动作。

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 using many keys with the same hashCode() is a sure way to slow down performance of any hash table. To ameliorate impact, when keys arejava.lang.Comparable, this class may use comparison order among keys to help break ties.

      如果有很多值要存储到HashMap实例中， 在创建HashMap实例时要设置足够大的初始容量， 避免自动扩容时rehash。 如果很多关键字的哈希值相同， 会降低哈希表的性能。 为了降低这个影响， 当关键字支持java.lang.Comparable时， 可以对关键字做次排序以降低影响。

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, itmust be synchronized externally. (A structural modification

   哈希表是非线程安全的， 如果多线程同时访问哈希表， 且至少一个线程修改了哈希表的结构， 那么必须在访问hashmap前设置同步锁。（修改结构是指添加或者删除一个或多个entry， 修改键值不算是修改结构。）

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.

     一般在多线程操作哈希表时，  要使用同步对象封装map。

If no such object exists, the map should be "wrapped" using theCollections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

      如果不封装Hashmap， 可以使用Collections.synchronizedMap  方法调用HashMap实例。  在创建HashMap实例时避免其他线程操作该实例， 即保证了线程安全。

   Map m = Collections.synchronizedMap(new HashMap(...));

       JDK1.8对哈希碰撞后的拉链算法进行了优化， 当拉链上entry数量太多（超过8个）时，将链表重构为红黑树。  下面是源码相关的注释：

   * This map usually acts as a binned (bucketed) hash table, but
      * when bins get too large, they are transformed into bins of
      * TreeNodes, each structured similarly to those in
      * java.util.TreeMap. Most methods try to use normal bins, but
      * relay to TreeNode methods when applicable (simply by checking
      * instanceof a node).  Bins of TreeNodes may be traversed and
      * used like any others, but additionally support faster lookup
      * when overpopulated. However, since the vast majority of bins in
      * normal use are not overpopulated, checking for existence of
      * tree bins may be delayed in the course of table methods.

看看HashMap的几个重要成员变量：

 //The default initial capacity - MUST be a power of two.

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //为毛不写成16？？？ 大师是想用这种写法告诉你只能是2的幂

 HashMap的初始容量是16个， 而且容量只能是2的幂。  每次扩容时都是变成原来的2倍。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认的负载因子是0.75f， 16*0.75=12。即默认的HashMap实例在插入第13个数据时，会扩容为32。

The bin count threshold for using a tree rather than list for a bin. Bins are converted to trees when adding an element to a bin with at least this many nodes. The value must be greater than 2 and should be at least 8 to mesh with assumptions in tree removal about conversion back to plain bins upon shrinkage.
static final int TREEIFY_THRESHOLD = 8;

注意：这是JDK1.8对HashMap的优化， 哈希碰撞后的链表上达到8个节点时要将链表重构为红黑树，  查询的时间复杂度变为O(logN)。

The table, initialized on first use, and resized as necessary. When allocated, length is always a power of two. (We also tolerate length zero in some operations to allow bootstrapping mechanics that are currently not needed.)
transient Node<K,V>[] table;  //HashMap的桶， 如果没有哈希碰撞， HashMap就是个数组，我说的是如果。  数组的查询时间复杂度是O(1)，所以HashMap理想时间复杂度是O(1)；如果所有数据都在同一个下标位置， 即N个数据组成链表，时间复杂度为O(n)， 所以HashMap的最差时间复杂度为O(n)。如果链表达到8个元素时重构为红黑树，而红黑树的查询时间复杂度为O(logN), 所以这时HashMap的时间复杂度为O(logN)。

Holds cached entrySet(). Note that AbstractMap fields are used for keySet() and values().
transient Set<Map.Entry<K,V>> entrySet; //HashMap所有的值，因为用了Set， 所以HashMap不会有key、value都相同的数据。

                               

                                                       哈希表的结构

1、 哈希碰撞的原因和解决方法：

     哈希碰撞是不同的key值找到相同的下标，  对应HashMap里hashcode和容量的模相同。

源码629行    if ((p = tab[i = (n - 1) & hash]) == null) ， 其中n是容量值，    即用哈希值和容量相与得到要保存的位置。 如果不同Key的(n - 1) & hash相同， 那么要存储到同一个数组下标位置， 这个现象就叫哈希碰撞。

        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {

          ....

         if ((p = tab[i = (n - 1) & hash]) == null)     //如果该下标没值，则存储到该下标位置
             tab[i] = newNode(hash, key, value, null);     
         else {
             Node<K,V> e; K k;
             if (p.hash == hash &&
                 ((k = p.key) == key || (key != null && key.equals(k))))
                 e = p;      //如果哈希值相同而且key相同， 则更新键值
             else if (p instanceof TreeNode)
                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  //如果下标数据是TreeNode类型，则将新数据添加到红黑树中。
             else {
                 for (int binCount = 0; ; ++binCount) {
                     if ((e = p.next) == null) {
                         p.next = newNode(hash, key, value, null);   //将新Node添加到链表末尾
                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                             treeifyBin(tab, hash);    //如果链表个数达到8个时，将链表修改为红黑树结构
                         break;
                     }    

            .....

           }

2、JDK1.8对HashMap最大的优化是resize函数，  在扩容时不再需要rehash了， 下面就看看大师是怎么实现的。

Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.

初始化数组或者扩容为2倍，   初值为空时，则根据初始容量开辟空间来创建数组。否则， 因为我们使用2的幂定义数组大小，数据要么待在原来的下标， 或者移动到新数组的高位下标。 （举例： 初始数组是16个，假如有2个数据存储在下标为1的位置， 扩容后这2个数据可以存在下标为1或者16+1的位置）

Returns:
    the table
final Node<K,V>[] resize() {

         ....

         newThr = oldThr << 1; // double threshold,   大小扩大为2倍，出于性能考虑和者告诉使用者它是2的幂， 这里用的是位移， 而不是*2，

   if (e.next == null)
      newTab[e.hash & (newCap - 1)] = e;  //如果该下标只有一个数据，则散列到当前位置或者高位对应位置（以第一次resize为例，原来在第4个位置，resize后会存储到第4个或者第4+16个位置）
  else if (e instanceof TreeNode)
     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  //红黑树重构

   else {

     do {
        next = e.next;
        if ((e.hash & oldCap) == 0) {   
            if (loTail == null)
               loHead = e;
            else
            loTail.next = e;
            loTail = e;
        } else {
            if (hiTail == null)
               hiHead = e;
            else
               hiTail.next = e;
               hiTail = e;
         }
      } while ((e = next) != null);
      if (loTail != null) {
          loTail.next = null;
          newTab[j] = loHead;   //下标不变
      }
      if (hiTail != null) {
          hiTail.next = null;
          newTab[j + oldCap] = hiHead; //下标位置移动原来容量大小
      }

   (e.hash & oldCap) == 0写的很赞！！！ 它将原来的链表数据散列到2个下标位置，  概率是当前位置50%，高位位置50%。     你可能有点懵比， 下面举例说明。  上边图中第0个下标有496和896，  假设它俩的hashcode(int型，占4个字节)是

resize前：

496的hashcode: 00000000  00000000  00000000  00000000

896的hashcode: 01010000  01100000  10000000  00100000

oldCap是16:       00000000  00000000  00000000  00010000

    496和896对应的e.hash & oldCap的值为0， 即下标都是第0个。

resize后：

496的hashcode: 00000000  00000000  00000000  00000000

896的hashcode: 01010000  01100000  10000000  00100000

oldCap是32:       00000000  00000000  00000000  00100000

   496和896对应的e.hash & oldCap的值为0和1， 即下标都是第0个和第16个。

   看明白了吗？   因为hashcode的第n位是0/1的概率相同， 理论上链表的数据会均匀分布到当前下标或高位数组对应下标。

       回顾JDK1.7的HashMap，在扩容时会rehash即每个entry的位置都要再计算一遍，  性能不好呀， 所以JDK1.8做了这个优化。

      再回到文章最开始的问题， HashMap为什么用&得到下标，而不是%？   如果使用了取模%， 那么在容量变为2倍时， 需要rehash确定每个链表元素的位置。

     很佩服HashMap的作者呀，  大师在运算符的使用上都是这么考究！！！

PS: 顺便说一下ArrayList， 初始容量是10个， 每次扩容是原来的1.5倍。

********

• 本文作者： 生活,生活?
• 本文链接： ayjcsgm.github.io/2019/10/03/HashMap源码分析-JDK1-8/
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！