HashMap（JDK-1.7及1.8）

简介

HashMap是基于哈希表实现的键值对的集合，继承自AbstractMap并实现了Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键（存放在第一个哈希桶中）。此类不保证映射的顺序，特别是它不保证该顺序恒久不变（扩容）。

HashMap的特殊存储结构使得在获取指定元素前需要经过哈希运算，得到目标元素在哈希表中的位置，然后再进行少量的比较即可得到元素，这使得HashMap的查找效率很高。

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，只需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

特点

• 底层实现是 链表数组，JDK 8 后又加了 红黑树
• 实现了 Map 全部的方法
• key 用 Set 存放，所以 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法
• 允许空键和空值（但空键只有一个，且放在第一位，下面会介绍）
• 元素是无序的，而且顺序会不定时改变
• 插入、获取的时间复杂度基本是 O(1)（前提是有适当的哈希函数，让元素分布在均匀的位置）
• 遍历整个 Map 需要的时间与 桶(数组) 的长度成正比（因此初始化时 HashMap 的容量不宜太大）
• 两个关键因子：初始容量、负载因子

如果内存空间很多而又对时间效率要求很高，可以降低负载因子loadFactor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

JDK1.7（数组+链表）

数据结构

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{
	//默认初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //最大容量： 2^ 30 次方
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //默认加载因子的大小：0.75，可不是随便的，结合时间和空间效率考虑得到的
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final Entry<?,?>[] EMPTY_TABLE = {};
    //哈希表中的链表数组
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    //键值对的数量
    transient int size;
    //阈值，下次需要扩容时的值，等于 容量*加载因子
    int threshold;
    //哈希表的加载因子
    final float loadFactor;
    //当前 HashMap 修改的次数，这个变量用来保证 fail-fast 机制
    transient int modCount;
    //缓存的 键值对集合（另外两个视图：keySet 和 values 是在 AbstractMap 中声明的）
    transient Set<Map.Entry<K,V>> entrySet;
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
    /**********部分代码省略**********/
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash; //对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
        /**********部分代码省略**********/
    }
    /**********部分代码省略**********/
}

HashMap中主要存储着一个Entry的数组table，Entry就是数组中的元素，Entry实现了Map.Entry所以其实Entry就是一个key-value对，并且它持有一个指向下一个元素的引用，这样构成了链表。

构造函数

/**
 * Constructs an empty <tt>HashMap</tt> 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();
}
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                    DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    inflateTable(threshold);

    putAllForCreate(m);
}

主要有两个参数，【initialCapacity】初始容量、【loadFactor】加载因子。这两个属性在类定义时候都赋有默认值分别为16和0.75。table数组默认值为EMPTY_TABLE，在添加元素的时候判断table是否为EMPTY_TABLE来调用inflateTable。在构造HashMap实例的时候默认【threshold】阈值等于初始容量。当构造方法的参数为Map时，调用inflateTable(threshold)方法对table数组容量进行扩充，扩充为原来的2倍：

/**
 * 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);
}
//返回一个比初始容量大的最小的2的幂数,如果number为2的整数幂值那么直接返回，最小为1，最大为2^31。
private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

HashMap的put方法

//HashMap添加元素
public V put(K key, V value) {
    //table没有初始化size=0，先调用inflateTable对table容器进行扩容
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    //在hashMap增加key=null的键值对
    if (key == null)
        return putForNullKey(value);
    //计算key的哈希值
    int hash = hash(key);
    //计算在table数据中的bucketIndex
    int i = indexFor(hash, table.length);
    //遍历table[i]的链表，如果节点不为null，通过循环遍历链表的下一个元素
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //找到对应的key，则将value进行替换
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    //没有找到对应的key的Entry，则需要对数据进行modify,modCount加一
    modCount++;
    //将改key，value添加入table中
    addEntry(hash, key, value, i);
    return null;
}
private V putForNullKey(V value) {
        for (Entry<K,V> 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;
   }
//添加Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
    //当前map中键值对数量大于于阈值，而且当前桶的索引位置不为null。则需要对桶进行扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //对桶进行扩容
        resize(2 * table.length);
        //重新计算hash值
        hash = (null != key) ? hash(key) : 0;
        //重新计算当前需要插入的桶的位置
        bucketIndex = indexFor(hash, table.length);
    }
    //在bucketIndex位置创建Entry
    createEntry(hash, key, value, bucketIndex);
}
//创建Entry
void createEntry(int hash, K key, V value, int bucketIndex) {
    //找到当前桶的当前链表的头节点
    Entry<K,V> e = table[bucketIndex];
    //新创建一个Entry将其插入在桶的bucketIndex位置的链表的头部
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}
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);
}
//找到当前的hash在桶的分布节点位置
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);
}

整体流程：
1、判断table[]哈希表是否为空，若为空，则按当前的阈值threshold对哈希表进行初始化（inflateTable(threshold)），设置为大于当前阈值的最小2次幂数。

2、判断key是否为空，若为空，则调用putForNullKey()在table[0]上设置新的 value，同时返回旧的value。
在putForNullKey()的执行逻辑为先判断table[0]上是否已经存在值，若存在就直接替换，返回旧值。若不存在则表明需要新加一个节点到链表上，此时需要先判断，当前的size是否已超过阈值，超过则先进行扩容，并重新计算key的hash值以及重新定位在哈希表的位置。若没超过，则插入一个新节点到table[0]链表的头部，size++。

3、若插入的key非空，先计算key的hash值，然后定位到具体的哈希表的位置，如table[i]。循环table[i]上的链表，根据key的hash值（不是hashCode）和equals方法比较链表上是否已存在key对应的Entry。若存在则更新对应的Entry上的value，同时返回旧值。若链表上不存在key对应的Entry，则表明需要新加一个节点到链表上，此时需要先判断，当前的size是否已超过阈值，超过则先进行扩容，并重新计算key的hash值以及重新定位在哈希表的位置。若没超过，则插入一个新节点到table[i]链表的头部，size++。

注意：

• 若发生覆盖行为，则返回key对应的旧值。

HashMap的扩容

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

//HashMap扩容
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);
}
//用于初始化hashSeed参数.
//其中hashSeed用于计算key的hash值，它与key的hashCode进行按位异或运算。
//这个hashSeed是一个与实例相关的随机值，主要用于解决hash冲突。
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;
}
//桶中数据的迁移，会将旧桶上链表一部分节点的顺序颠倒过来
void transfer(Entry[] newTable, boolean rehash) {
    //新的痛长
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        //遍历桶的每一个节点的链表
        while(null != e) {
            //提前拿出下一个待迁移的节点
            Entry<K,V> next = e.next;
            //重新计算哈希值
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //找到当前Entry在新桶中的位置
            int i = indexFor(e.hash, newCapacity);
            //将Entry添加在当桶中的bucketIndex处的链表的头部
            e.next = newTable[i];
            //将产生的新链表赋值为桶的bucketIndex处
            newTable[i] = e;
            //遍历当前链表的下一个节点
            e = next;
        }
    }
}

整体过程：
1、判断当前容量是否达到最大值（Integer.MAX_VALUE），若是则直接返回，不进行扩容，否则创建新的桶。
2、transfer()将旧桶上的数据移到新桶上，重新计算阈值。
转移过程：遍历每个桶上的链表，重新定位每个链表上节点在新桶上的位置，利用头插法将节点转移到新的桶上。

所有Entry的hash值是不需要重新计算的。因为hash值与（length - 1）取的总是hash值的二进制右边底位，扩容一次向左多取一位二进制，取值互不影响。
在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

HashMap的get方法

//HashMap的get方法
public V get(Object key) {
    //获取key为null的value
    if (key == null)
        return getForNullKey();
    //获取key对应的Entry实例
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

//获取Entry
final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    //计算key的hash值
    int hash = (key == null) ? 0 : hash(key);
    //根据hash调用indexFor方法找到当前key对应的桶的index，遍历该节点对应的链表
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        //判断当前Entry的hash、key的hash和Entry的key、key是否相等
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

整体过程：
1、若key为空，则直接在哈希表table[0]的链表上遍历，得到key为null的Entry并返回value，若没有得到相应的Entry，直接返回null
2、若key非空，则先计算key对应的哈希值，定位key在哈希桶上的位置，然后遍历该位置上的链表。根据key的hash值和equal找到对应的Entry，返回Entry上的value，否则返回null。

HashMap的keySet

我们遍历hashmap时的方法如下:

Iterator<String> map = map.keySet().iterator();
      while(map.hasNext()){
          System.out.println(map.next());
  }

public Set<K> keySet() {
       Set<K> ks = keySet;
       return (ks != null ? ks : (keySet = new KeySet()));
   }

往后一直追溯到：

private final class KeyIterator extends HashIterator<K> {
       public K next() {
           return nextEntry().getKey();
       }
   }

当我们在增强for循环时会调用该next()方法，它指向的是nextEntry().getKey()，Entry中不仅存放了key，value，也存放了next，指向下一个Entry对象，我们知道，HashMap的数据层实现是数组+链表，nextEntry会先遍历链表，然后再继续遍历下一个数组位置的链表，直至全部遍历完成，其部分源码如下：

if ((next = e.next) == null) {
    Entry[] t = table;
    while (index < t.length && (next = t[index++]) == null)
        ;
}

keySet()方法返回一个内部引用，并指向一个内部类对象，该内部类重写了迭代器方法，当在增强for循环时才调用，并从外部类的table中取值。

JDK1.8 以及所做的改进

数据结构

在java8中Entry改名为Node，因为在Java8中Entry不仅有链表形式还有树型结构，对应的类为TreeNode。同时增加了以下成员变量：

//链表切换为红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
//红黑树切花为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//红黑树上的节点个数满足时对整个桶进行扩容
static final int MIN_TREEIFY_CAPACITY = 64;
//红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    /*************部分代码省略*****************/
}
//获取key的hashCode,并进行二次hash。二次hash只是将hashcode的高16位于第16位进行异或
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//resize时hash冲突使用的是红黑树
final Node<K,V>[] resize() {
    /*************部分代码省略*****************/
}

定位桶位置算法

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。这样可以避免只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，可以避免哈希值分布不均匀。

static final int hash(Object key) {   
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

取key的hashCode值、高位运算、取模运算。JDK1.8没有indexFor()方法，将具体的实现放到了put方法中。

对Null key的处理

在hash方法中做处理，统一返回hash值为0，并参与后面的正常运算过程，也是存储在第一个桶的位置。

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

put

①.判断table是否为null或table.length是否为null，是则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

public V put(K key, V value) {  
    //hash()方法在上面已经出现过了，就不贴了  
    return putVal(hash(key), key, value, false, true);  
}  
  
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
               boolean evict) {  
    Node<K, V>[] tab;  
    Node<K, V> p;  
    int n, i;  
    // 步骤①：tab为空则创建  
    if ((tab = table) == null || (n = tab.length) == 0)  
        n = (tab = resize()).length;  
    // 步骤②：计算index，并对null做处理  
    if ((p = tab[i = (n - 1) & hash]) == null)  
        tab[i] = newNode(hash, key, value, null);  
    else {  
        Node<K, V> e;  
        K k;  
        // 步骤③：节点key存在，直接覆盖value  
        if (p.hash == hash &&  
                ((k = p.key) == key || (key != null && key.equals(k))))  
            e = p;  
            // 步骤④：判断该链为红黑树  
        else if (p instanceof TreeNode)  
            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);  
            // 步骤⑤：该链为链表  
        else {  
            for (int binCount = 0; ; ++binCount) {  
                if ((e = p.next) == null) {  
                    p.next = newNode(hash, key, value, null);  
                    //链表长度大于8转换为红黑树进行处理 TREEIFY_THRESHOLD = 8  
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                        treeifyBin(tab, hash);  

                    break;  
                }  
                // key已经存在直接覆盖value  
                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;  
        }  
    }  
    ++modCount;  
    // 步骤⑥：超过最大容量 就扩容  threshold：单词解释--阈(yu)值,不念阀(fa)值！顺便学下语文咯。  
    if (++size > threshold)  
        resize();  
    afterNodeInsertion(evict);  
    return null;  
}  

注意：
1.7先扩容完，再加上新的节点，而1.8是加上新节点后，再扩容。
1.7使用inflateTable来初始化数组，1.8统一使用resize()，扩容也是它。
1.7链表采用头插法，1.8链表采用尾插法。

扩容

  final Node<K,V>[] resize() {
    //复制一份当前的数据
    Node<K,V>[] oldTab = table;
    //保存旧的元素个数、阈值
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //新的容量为旧的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //如果旧容量小于等于 16，新的阈值就是旧阈值的两倍
            newThr = oldThr << 1; // double threshold
    }
    //如果旧容量为 0 ，并且旧阈值>0，说明之前创建了哈希表但没有添加元素，初始化容量等于阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //旧容量、旧阈值都是0，说明还没创建哈希表，容量为默认容量，阈值为 容量*加载因子
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //如果新的阈值为 0 ，就得用 新容量*加载因子 重计算一次
    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) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                //旧的桶置为空
                oldTab[j] = null;
                //当前 桶只有一个元素，直接赋值给对应位置
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    //如果旧哈希表中这个位置的桶是树形结构，就要把新哈希表里当前桶也变成树形结构
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { //保留旧哈希表桶中链表的顺序
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    //do-while 循环赋值给新哈希表
                    do {
                        next = e.next;
                        // 原索引
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

在JDK1.8中发生hashmap扩容时，遍历hashmap每个bucket里的链表，每个链表可能会被拆分成两个链表，不需要移动的元素置入loHead为首的链表，需要移动的元素置入hiHead为首的链表，然后分别分配给老的buket和新的buket。

扩容过程中几个关键的点：

• 新初始化哈希表时，容量为默认容量，阈值为 容量*加载因子
• 已有哈希表扩容时，容量、阈值均翻倍
• 如果之前这个桶的节点类型是树，需要把新哈希表里当前桶也变成树形结构
• 复制给新哈希表中需要重新索引（rehash），这里采用的计算方法是 e.hash & (newCap - 1)，等价于 e.hash % newCap

1. 在JDK1.7的时候是直接用hash值和需要扩容的二进制数进行&（这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在，因为如果只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少hash碰撞）（hash值 & length-1）

2. 在JDK1.8的时候直接用了JDK1.7的时候计算的规律，也就是扩容前的原始位置+扩容的大小值=JDK1.8的计算方式，而不再是JDK1.7的那种异或的方法。但是这种方式就相当于只需要判断Hash值的新增参与运算的位是0还是1就直接迅速计算出了扩容后的储存方式。

这里用到的是(e.hash & oldCap)，它有两种结果，一个是0，一个是oldCap，

比如oldCap=8,hash是3，11，19，27时，(e.hash & oldCap)的结果是0，8，0，8。这样3，19组成新的链表，index为3；而11，27组成新的链表，新分配的index为3+8；

JDK1.7中重写hash是(e.hash & newCap-1)，也就是3，11，19，27对16取余，也是3，11，3，11，和上面的结果一样，但是index为3的链表是19，3，index为3+8的链表是

27，11，也就是说1.7中经过resize后数据的顺序变成了倒叙，而1.8没有改变顺序。
扩容后，新数组中的链表顺序依然与旧数组中的链表顺序保持一致！

get

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;
    //tab 指向哈希表，n 为哈希表的长度，first 为 (n - 1) & hash 位置处的桶中的头一个节点
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //如果桶里第一个元素就相等，直接返回
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //否则就得慢慢遍历找
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                //如果是树形节点，就调用树形节点的 get 方法
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                //do-while 遍历链表的所有节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

查找 方法比较简单:

先计算哈希值;
然后再用 (n - 1) & hash 计算出桶的位置;
在桶里的链表进行遍历查找。

思考

1.7和1.8hash算法的不同

JDK1.7用了9次扰动处理=4次位运算+5次异或，而JDK1.8只用了2次扰动处理=1次位运算+1次异或。

为什么哈希表的长度是2次幂

首先，capacity 为 2的整数次幂的话，计算桶的位置 h&(capacity-1) 就相当于对 capacity 取模，提升了计算效率；

其次，capacity 为 2 的整数次幂的话，为偶数，这样 capacity-1 为奇数，奇数的最后一位是 1，这样便保证了 h&(capacity-1) 的最后一位可能为 0，也可能为 1（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性；

而如果 capacity 为奇数的话，很明显 capacity-1 为偶数，它的最后一位是 0，这样 h&(capacity-1) 的最后一位肯定为 0，即只能为偶数，这样任何 hash 值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间。

1.7HashMap扩容时出现死循环原因及1.8是怎么改进的

先看下1.7的扩容方法

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
　　　　　//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
　　　　　　　　　 //将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

当thread1执行到Entry next = e.next;这一行时，thread2已完成对HashMap的扩容，结果如下图。

注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。
thread1被调度回来执行，先是执行 newTalbe[i] = e， 然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3)。

e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

根本原因就是扩容重建时链表中形成了环,导致后续get时在环里打转造成死循环。
为什么会形成环?
table这个Entry数组是线程共享的,而next,e是线程私有的。现在假设线程1在运行完后挂起了,然后线程2也去做重建并且完成了。线程1恢复运行时entry状态的变化可能已经被刷新到主存了(线程相关的happends-before规则),这样当前entry的状态就和 next,e 期待的不同,就会导致错误的行为。

JDK1.8声明两对指针，维护两个链表依次在末端添加新的元素。（在多线程操作的情况下，无非是第二个线程重复第一个线程一模一样的操作），解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。

1.8hash的实现吗？为什么要这样实现？

通过hashCode()的高位与底位进行异或，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。

HashMap 中 equals() 和 hashCode() 有什么作用？

HashMap 的添加、获取时需要通过 key 的 hashCode() 进行 hash()，然后计算下标 ( n-1 & hash)，从而获得要找的同的位置。

当发生冲突（碰撞）时，利用 key.equals() 方法去链表或树中去查找对应的节点。

keySet、valueEntry、EntrySet

HashMap 三个视图返回的迭代器都是 fail-fast 的：如果在迭代时使用非迭代器方法修改了 map 的内容、结构，迭代器就会报 ConcurrentModificationException 的错。

参考资料

• 迟到一年HashMap解读
• Java 8系列之重新认识HashMap
• Java 集合深入理解（16）：HashMap 主要特点和关键方法源码解读
• HashMap中keySet()底层调用解析
• Hashmap的结构，1.7和1.8有哪些区别，史上最深入的分析
• JDK1.8 不一样的HashMap