Java编程拾遗『容器——HashMap』

之前用了两篇文章讲解了ArrayList和LinkedList的实现和使用，ArrayList和LinkedList都存在一个问题，查找元素效率比较低，都需要一一对比，时间复杂度是O(N)。还是回到那句话，每种数据结构都不是凭空出现的，肯定都有其特定的使用场景，而HashMap其实就是数据结构中的Hash结构的一种实现。本篇文章会介绍一下Java API中HashMap的使用及实现细节，并在后面一篇文章中介绍一下基于HashMap实现的集合类HashSet。

HashMap的继承关系比较简单，实现了Map接口，继承了抽象类AbstractMap类，这部分跟之前讲的ArrayList和LinkedList继承抽象类的原因相同——方便扩展。同时HashMap实现了Cloneable，可克隆。实现了Serializable接口，可以被序列化。

本文源码分析模块，put操作和线程安全，主要参考了美团技术Java 8系列之重新认识HashMap这篇文章，在那篇文章的基础上，结合Java8源码的一些思考，写了本篇文章，这里把原文链接粘一下。

1. 使用规则

1.1 构造方法

1.2 Map接口

HashMap实现了Map接口，继承的抽象类AbstractMap也实现了Map接口，所以HashMap中的常用方法大多数都继承自Map接口，如下：

2. 实现源码分析

在讲方法具体的源码实现之前，先大致讲一下Java中HashMap的基本结构实现，HashMap底层基于Node数组实现，内部类Node实现了Map.Entry接口（Java8的改动，Java8之前不叫Node，内部类名称为Entry）。从结构实现来讲，HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下图所示：

下面看一下内部类Node定义：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)，上图中的每个黑色圆点就是一个Node对象。除了key和value，Node中还有两个成员变量hash和一个自身类型的引用next，分别表示key的哈希值及当前Node节点的相邻节点引用(组织链表)。

HashMap就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。例如程序执行下面代码：

map.put("zhuo", 1);

系统将调用”zhuo”这个key的hashCode()方法得到其hashCode值，然后再通过hashCode值来定位该键值对的存储位置，有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node<k,v>[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。

在理解Hash和扩容流程之前，我们得先了解下HashMap的几个字段。从HashMap的默认构造函数源码可知，HashMap中主要存在以下几个重要的成员变量：

transient Node<K,V>[] table; //Map中用来存储key-value对Node节点的数组
int threshold;             // 所能容纳的key-value对极限 
final float loadFactor;    // 负载因子
int modCount;  //修改次数
int size;     //Map中key-value对数目

首先，Node<k,v>[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

size这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败(ConcurrentModificationException)。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，具体证明可以参考为什么一般hashtable的桶数会取一个素数，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。

这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在Java 8中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8并且数组length大于64）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。

以上相当于是对Java API HashMap实现的一个概述，下面通过具体的方法及源码来介绍HashMap的实现。

2.1 构造函数

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

默认构造函数仅对负载因子进行了赋值，Java8默认构造函数并没有对threashold初始化，这也是跟Java7不同的地方。Java7中，默认构造函数会对loadFactor和threshold赋默认值。在Java8中，对threshold赋值的逻辑是放在put流程中的，在进行第一次进行put操作时，会进行resize，并对threshold赋值。在下面会讲解。上述DEFAULT_LOAD_FACTOR为负载因子的默认值，0.75。

除了上述默认构造函数，下面来看一下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);
}

对HashMap内部loadFactor和threshold赋初值，这里要对tableSizeFor方法特殊讲一下，tableSizeFor返回大于等于initialCapacity最小的2的整数次幂。方法实现使用移位实现，效率较高，也是Java8中引入的新方法。如果通过如下方式调用构造函数：

Map<Stirng, Integer> strMap = new HashMap(13, 0.75);

那么初始化得到的HashMap，loadFactor为0.75，threashold为16。仔细想一下，好像有一点问题，我们都知道，上面调用，我们是希望声明一个容量为13的HashMap，根据HashMap中，哈希桶数组table的长度length大小必须为2的n次方，初始化得到的HashMap哈希桶数组length应该为16，那么HashMap的threshold = length * Load factor = 16 * 0.75 = 12，而不是上面通过tableSizeFor方法得到的16。这是因为调用上述构造函数得到threshold其实存储的是哈希桶数组的长度，在进行第一次进行put操作时，会进行resize，并对threshold重新赋值。

对比一下Java7中上述两个方法的实现：

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
    this.loadFactor = loadFactor;
    threshold = initialCapacity;
}

可以看到Java7中，默认构造函数，直接将threshold、loadFactor赋值为默认值16、0.75。而上述第二个构造函数，直接将构造函数的入参赋值给threshold、loadFactor，比如调用构造函数new HashMap(13, 0.75)，在Java7中，Hash桶数组长度为大于等于17.333(13 / 0.75)的最小2的整数次幂，即32。而在Java8中，同样的调用，Hash桶数组长度为16(tableSizeFor函数计算得到)，threshold大小为16 * 0.75 = 12。接着看一下Java8中余下两个构造函数实现。

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

声明一定容量的HashMap，底层还是调用HashMap(int initialCapacity, float loadFactor)构造函数，loadFactor为默认值0.75。

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

通过一个Map初始化HashMap，将负载因子loadFactor赋为默认值0.75，然后调用putMapEntries方法，将Map中的键值对插入到当前HashMap的Hash桶数组中，putMapEntries方法第二个参数控制插入后是否进行检查，清除最老元素，LinkedHashMap按访问有序的情况下才会是true，关于这个参数，下篇文章讲LinkedHashMap实现的时候再仔细讲解，这里仅来看一下putMapEntries简单实现：

/*
* 将Map中的键值对插入到当前HashMap中
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    //s > 0，说明Map不为空，依次将Map中的键值对插入到当前HashMap中
    if (s > 0) {
        if (table == null) { // pre-size
            //table == null，说明当前HashMap还没进行过插入操作
            //则对根据s的大小，初始化当前HashMap的threshold，使其能够容纳m

            //ft即为能够容纳m的hash桶数组length的最小值(因为数组长度必须为2的整数幂，所以ft不一定为最终值)
            float ft = ((float)s / loadFactor) + 1.0F;

            //检查ft是否超过最大值，如果超过了就赋最大值
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);

            //调用上述构造函数，threshold未进行赋值，所以为0，肯定小于t
            if (t > threshold)
                //threshold为大于t的最小的2的整数次幂，这个threshold不是最终的threshold，
                //在put操作中进行resize时，会赋值为length * loadfactor
                threshold = tableSizeFor(t);
        }
        //如果table不为null，并且s大于当前HashMap的threshold，进行扩容
        else if (s > threshold)
            resize();
        //遍历Map，调用putVal插入Map中的键值对
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

这里分析一下调用上述构造函数，然后调用putMapEntries方法的情况，table ==null肯定是为true的，在该条件下，最终计算得到的threshold为2^n，则满足如下条件：

s/0.75 + 1 < 2^n
所以可以推断出：s < (2^n -1) * 0.75

在putVal插入第一个键值对时，会进行resize，最终得到真正的threshold = length * 0.75，真正的threshold被重新赋值为2^n * 0.75，所以s肯定小于当前HashMap最终的threshold，只需要在插入第一个元素的时候进行一次扩容操作，之后便可以容纳Map中所有的键值对，而不用再进行扩容，设计还是比较巧妙的。

2.2 put方法

Java8中put操作如下所示：

public V put(K key, V value) {
    // 对key的hashCode()做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;
    // 1：tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2：计算index，并对null做处理 
    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3：节点key存在，直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4：判断该链为红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 5：该链为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key,value,null);
                     //链表长度大于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;
    // 6：超过最大容量 就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    	//如果数组长度小于64，进行扩容，并不会转化为红黑树
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
    	//数组长度大于64，将链表转化为红黑树
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

具体流程如下图：

1. 判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容
2. 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，则转向3
3. 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals
4. 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5
5. 遍历table[i]，判断链表长度是否大于8，大于8且数组length大于64的话把链表转换为红黑树，在红黑树中执行插入操作，否则对数组进行扩容，进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可
6. 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容

这里Java8跟之前的版本有一些不同的处理：

• Java8 HashMap是数组+链表+红黑树组织的，之前的版本时通过数组+链表组织的。在Java8中如果链表长度大于8并且数组length大于64，会转化成红黑树
• 对于链表结构，在进行put操作，向某个链表中添加元素时，Java8使用的时尾插法，而Java8之前的版本使用的是头插法
• 计算key的哈希值方法不同，Java8中优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的
• resize实现不同，Java8中resize不会产生环链，从而导致cpu使用率飙升到100%，但仍有数据丢失的可能。另外Java8之前的版本，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，而Java8会保持原来链表的顺序。

2.2.1 确定哈希桶数组索引位置

前面讲过HashMap是通过数组和链表组织的，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。Java中定位一个key的桶数组位置主要是通过如下两个方法实现的：

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

//方法二：
static int indexFor(int h, int length) {  //java7源码，java8中没有这个方法，但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

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

这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在桶数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

下面举例说明下，n为table的长度：

 2.2.2 扩容机制

扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组。

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;
        }
        // 没超过最大值，就扩充为原来的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize上限
    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) {
        // 把每个bucket都移动到新的buckets中
        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 { // 链表优化重hash的代码块
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    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;
}

相关细节注释中都讲解了，这里特别提一下上面讲构造函数时提到的，HashMap构造函数都没对threshold赋值，而是在resize中对其赋值这一动作是怎么实现的，如下图所示：

对比一下Java7 put的实现，如下：

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<K,V> 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;
}  

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);
}

void resize(int newCapacity) {   //传入新的容量
    Entry[] oldTable = table;    //引用扩容前的Entry数组
    int oldCapacity = oldTable.length;         
    if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
        threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
        return;
    }
 
    Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
    transfer(newTable);                         //！！将数据转移到新的Entry数组里
    table = newTable;                           //HashMap的table属性引用新的Entry数组
    threshold = (int)(newCapacity * loadFactor);//修改阈值
}

void transfer(Entry[] newTable) {
    Entry[] src = table;                   //src引用了旧的Entry数组
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
        Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
        if (e != null) {
            src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                e.next = newTable[i]; //标记[1]
                newTable[i] = e;      //将元素放在数组上
                e = next;             //访问下一个Entry链上的元素
            } while (e != null);
        }
    }
}

在Java7 resize中，会遍历哈希桶数组每个元素，然后将每个链表中的元素通过rehash，组织到新的哈希桶数组中。newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置。但是在Java8中，除了引入红黑树处理外(比较复杂，没看懂，这里不讲了)，对于链表的处理跟Java7中也有很大的区别，其实就是不用进行rehash了(indexFor操作)，而是通过平移的方式组织到新的哈希桶数组中，效率较高。

首先来看一下Java7中，resize操作。假设hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。其中的哈希桶数组table的size=2， 所以key = 3、7、5，put顺序依次为 5、7、3(Java7 put操作链表组织也是头插法)。在mod 2以后都冲突在table[1]这里了。假设负载因子loadFactor=1，即当键值对的实际大小size大于table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组resize成4，然后所有的Node重新rehash的过程。如下所示：

 下面讲解下Java8做了哪些优化。经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

 元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，在扩充HashMap的时候，不需要像Java7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

 这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是Java8新增的优化点。有一点注意区别，Java7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，Java8中不会倒置。

2.3 线程安全

HashMap在多线程环境中时不安全的，在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。而我们取查询为什么HashMap在多线程下不安全，得到的答案总是：多线程场景下，HashMap可能造成死循环，导致cpu使用率飙升到100%。这里先将一下结论，其实HashMap在Java8之前的版本，多线程场景下会造成死循环，并且有可能会丢失数据，但是Java8之后，不会再造成死循环，但是无法规避数据丢失的可能。下面首先来看一下Java7 HashMap再多线程场景下为什么会造成死循环。

public class HashMapInfiniteLoop {  

    private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);  
    public static void main(String[] args) {  
        map.put(5， "C");  

        new Thread("Thread1") {  
            public void run() {  
                map.put(7, "B");  
                System.out.println(map);  
            };  
        }.start();  
        new Thread("Thread2") {  
            public void run() {  
                map.put(3, "A);  
                System.out.println(map);  
            };  
        }.start();        
    }  
}

其中，map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize。

通过设置断点让线程1和线程2同时debug到transfer方法的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行；然后放开线程2的的断点，让线程2进行resize。结果如下图。

注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。

线程一被调度回来执行，先是执行 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)， 环形链表就这样出现了。

于是，当我们用线程一调用map.get(11)时，悲剧就出现了——Infinite Loop。并且map中还丢失了元素，(5, “C”)在map中不存在了。

上面讲过，Java8中HashMap在扩容时，不是使用Java7中这种重组链表的形式，而是通过维护两个链表指针loHead、loTail、hiHead、hiTail，只是将元素添加到两个链表的尾部，并不需要头部链接，所以即使存在上面讲的多线程场景，也不会产生上述环链，但是由于线程2已经将链表结构改变了，所以有可能线程1调度回来重组链表的时候，只能遍历到部分元素，所以仍存在数据丢失的可能。

2.4 get(Object key)方法

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;
    //获取key所在hash桶数组索引的第一个元素first
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // 比较第一个元素first与key是否相等
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //第一个元素不相等，遍历first的后继元素
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                //如果位红黑树，则取遍历红黑树，获取与key相等的TreeNode节点
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                //遍历链表，获取与key相等的Node节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

2.5 containsKey(Object key)方法

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

如果能获取到key对应的Node，则说明key存在。上面getNode方法已经详细说明了，不多解释了。

2.6 containsKey(Object key)方法

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        //遍历哈希桶数组每个元素
        for (int i = 0; i < tab.length; ++i) {
            //遍历哈希桶数组各个index位置的元素
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

判断HashMap中是否存在value的算法很粗暴，就是遍历。由于无法使用hash映射，所以效率并不高。

2.7 remove(Object key)方法

从HashMap中删除键为key的键值对，如果删除成功，返回删除键值对的value。如下：

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

主要调用了removeNode方法，removeNode主要作用是删除key对应的节点，并返回该Node，如下：

/**
* @param hash key的哈希值
* @param key key
* @param value 如果matchValue为true，则比较value，否则忽略value
* @param matchValue 如果为true，只有当value也相等时，才删除节点
* @param movable 如果为false，在删除时，不移动其他Node，作用于红黑树节点删除
* @return 返回删除的Node，如果未删除，返回null
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        //与getNode(int hash, Object key)一致，获取key对应的Node
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        //判断是否能删除Node
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                //红黑树节点删除处理
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                //node为链表首节点，将tab[index]指向node的后继节点
                tab[index] = node.next;
            else
                //node非首节点，删除node节点，p为node的前置节点，p的next指针指向node的next后继节点
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

确定Node的思想跟之前讲的getNode方法思想一致，其它细节，见注释。

2.8 remove(Object key, Object value)方法

public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}

理解了上述remove方法，再来看该删除键值对的remove方法就比较简单了，只要在removeNode方法中，讲value赋值，并将matchVlaue置为true。

3. HashMap特点

• 根据键保存和获取值的效率都很高，为O(1)
• HashMap中的键值对没有顺序，因为hash值是随机的

参考链接：

1. Java 8系列之重新认识HashMap
2. HashMap多线程死循环问题
3. JDK8的HashMap源码学习笔记