JDK1.8中的HashMap源码分析

一、关于HashMap

HashMap是最经典的Map实现，HashMap是一个具有映射关系（key-value）的集合，它基于hash算法，通过put和get方式存储和获取对象。

二、HashMap实现原理

1、数据结构

HashMap的底层维护一个Node数组Node<K,V>[] table，哈希bucket就是HashMap数组里面的一个位置中所占所有数据，每个bucket里面通过Node<K,V>来储存元素，Node实现了Entry，Node还可以扩展成链表，当链表长度大于等于8时，会转化为红黑树TreeNode<K,V>。

2、原理

存储对象时，我们将K/V传给put方法时，它调用K的hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。

如果发生碰撞的时候，HashMap通过链表将产生碰撞冲突的元素组织起来。在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

JDK1.7中的HashMap，是基于数组+链表来实现的，它的底层维护一个Entry数组。它会根据计算的hashCode将对应的KV键值对存储到该数组中，一旦发生hashCode冲突，那么就会将该KV键值对放到对应的已有元素的后面，此时便形成了一个链表式的存储结构。

JDK1.7中HashMap的实现方案有一个明显的缺点，即当Hash冲突严重时，在桶上形成的链表会变得越来越长，这样在查询时的效率就会越来越低，其时间复杂度为O(N)。

JDK1.8中的HashMap，是基于数组+链表+红黑树来实现的，它的底层维护一个Node数组。当链表的存储的数据个数大于等于8的时候，且数组空间大于等于64，不再采用链表存储，而采用了红黑树存储结构。这么做主要是在查询的时间复杂度上进行优化，链表为O(N)，而红黑树一直是O(logN)，可以大大的提高查找性能。

三、源码解析

1、成员变量

groovyScript("if(\"${_1}\".length() == 2) {return '';} else {def result=''; def params=\"${_1}\".replaceAll('[\\\\[|\\\\]|\\\\s]', '').split(',').toList();for(i = 0; i < params.size(); i++) {if(params[i]=='null'){return;}else{result+='\\n' + ' * @param ' + params[i] + ' '}}; return result;}", methodParameters());



/**
 * The default initial capacity - MUST be a power of two.
 * 数组初始容量，1向左移位4位，也就是16，使用移位是因为移位是计算机基础运算，效率快
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * MUST be a power of two <= 1<<30.
 * 最大容量<=2^30
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.
 * 加载因子，当数组容量使用超过75%就扩容
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 当某个bucket节点数量大于8时，链表会转换为红黑树
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 当某个bucket节点数量小于6时，如果是红黑树就会转换为链表
 */
static final int UNTREEIFY_THRESHOLD = 6;


/**
 * 当整个hashMap数组长度小于64时，链表无法转换为红黑树
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * 存储元素的数组，transient关键字表示该属性不能被序列化
 */
transient Node<K,V>[] table;

/**
 * 将数据转换成set的另一种存储形式，这个变量主要用于迭代功能
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * 元素数量
 */
transient int size;

/**
 * 统计该map修改的次数
 */
transient int modCount;

/**
 * The next size value at which to resize (capacity * load factor).
 * 阈值，也就是元素数量达到阈值时，会进行扩容，阈值 = capacity * load factor
 */
int threshold;

关于transient关键字

Java中使用transient关键字修饰的成员变量不参与序列化过程。可以保证信息安全。

序列化 (Serialization)：将对象的状态信息转换为可以存储或传输的形式的过程。在序列化期间，对象将其当前状态写入到临时或持久性存储区。以后，可以通过从存储区中读取或反序列化对象的状态，重新创建该对象。

2、静态内部类

源码

/**
 * Node结点，用来储存K-V，实现了Map.Entry接口，可以扩展成链表
 */
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;
    }
}

/**
 * 红黑树结构，TreeNode继承LinkedHashMap.Entry，而LinkedHashMap.Entry是继承HashMap.Node
 */
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;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    
    }

关于HashMap中的循环链表

https://blog.csdn.net/u014401141/article/details/122686601
在jdk1.7中，因为HashMap采用头插法。
在多线程的情况下，当重新调整HashMap大小的时候，就会存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历。如果条件竞争发生了，那么就会产生死循环了。

3、构造方法

/**
 * 设置初始容量和加载因子
 */
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);
}

/**
 * 无参构造，使用默认的加载因子0.75
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
 * 传入一个Map，然后把该Map转为HashMap
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
/**
 * Implements Map.putAll and Map constructor.
 *
 * @param m the map
 * @param evict false when initially constructing this map, else
 * true (relayed to method afterNodeInsertion).
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        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);
        }
    }
}

4、为什么加载因子为0.75

加载因子是表示Hash表中元素的填满的程度。
加载因子越大,填满的元素越多,空间利用率越高，但发生冲突的机会加大了。
加载因子越小,填满的元素越少,冲突的机会减小,但空间浪费多了。
冲突的机会越大,则查找的成本越高。反之,查找的成本越小。

因此,必须在 “发生冲突的机会”与”空间利用率”之间寻找一种平衡与折衷。

至于到底为什么是0.75？

下面是我唯一能在网上找到的相关信息了，我也不太确定真实性。

Stack overFlow上这篇回答很有意思：

https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap

根据这个回答，一个bucket空和非空的概率为0.5，通过牛顿二项式等数学计算，他计算了完美的加载因子应该约为$ln2$ 约为0.693

至于为什么是0.75，我认为可能是0.75*初始长度16，刚好能得到一个整数的threshold为12，那为什么不取更加接近的0.6875，我个人认为，可能是想尽量加点空间利用率吧，毕竟jdk1.8都引入了红黑树来解决严重的hash冲突情况，即使实际上转化为红黑树的概率都相当低。

5、链表转换为红黑树

源码分析

/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果数组的长度小于64
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        //扩容
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        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);
    }
}

从以上代码可以看出，当put元素时，链表长度大于等于8触发链表转化为红黑树，但是会先判断该HashMap数组长度，如果长度小于64则不会出发树化，而是先出发扩容机制，反之才会树化。

为什么当链表长度达到8位时转化为红黑树？

柏松分布：https://en.wikipedia.org/wiki/Poisson_distribution

参考源码中的注释

/*
 * Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.  In
 * usages with well-distributed user hashCodes, tree bins are
 * rarely used.  Ideally, under random hashCodes, the frequency of
 * nodes in bins follows a Poisson distribution
 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 * parameter of about 0.5 on average for the default resizing
 * threshold of 0.75, although with a large variance because of
 * resizing granularity. Ignoring variance, the expected
 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 * factorial(k)). The first values are:
 *
 * 0:    0.60653066
 * 1:    0.30326533
 * 2:    0.07581633
 * 3:    0.01263606
 * 4:    0.00157952
 * 5:    0.00015795
 * 6:    0.00001316
 * 7:    0.00000094
 * 8:    0.00000006
 * more: less than 1 in ten million
 *
 */

翻译：

因为 TreeNode 的大小大约是常规nodes的两倍，所以我们仅在 bin 包含足够的nodes以保证使用时才使用它们（请参阅 TREEIFY_THRESHOLD）。当它们变得太小（由于移除或调整大小）时，它们会被转换回普通bins。在具有良好分布的hashCodes的使用中，很少使用tree bins。理想情况下，在随机 hashCodes 下，bin 中nodes的频率遵循泊松分布，默认扩容阈值为 0.75，参数平均约为 0.5，尽管由于扩容粒度而存在很大差异。忽略方差，list size k 的预期出现是 (exp(-0.5) * pow(0.5, k) / factorial(k))。

官方根据泊松分布实验发现，假设hashmap长度length为16，假设放入12（0.75*16）个数据到hashmap中，链表中存放8个节点的概率仅为0.00000006，链表中存放1~8节点的概率为：

0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006

从以上可知，实际上一个链表被放满8个节点的概率非常小，实际上链表转红黑树是非常耗性能的，而链表在8个节点以内的平均查询时间复杂度与黑红树相差无几，超过8个节点，黑红树的查询复杂度会好一些。所以，当链表的节点大于等于8个的时候，转为红黑树的性价比比较合适。

为什么用红黑树而不用B树

B/B+树多用于外存上时，B/B+也被成为一个磁盘友好的数据结构。

HashMap本来是数组+链表的形式，链表由于其查找慢的特点，所以需要被查找效率更高的树结构来替换。如果用B/B+树的话，在数据量不是很多的情况下，数据都会“挤在”一个结点里面，这个时候遍历效率就退化成了链表。

四、HashMap中的hash()方法

static final int hash(Object key) {
    int h;
    //先获取到key的hashCode，然后进行移位再进行异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在HashMap中采用了上面的方式进行HashCode的运算，这样可以将hashCode的前后16位都充分利用。并且使用了异或运（其他的离散值为3/4，而异或为1/2）算来加大离散度（在哈希计算中，所有的操作都是为了加大离散度）。

1、为什么要右移16位?

0000 0100 1011 0011  1101 1111 1110 0001
 
>>> 16 
 
0000 0000 0000 0000  0000 0100 1011 0011

保证高16位也参与计算， int占4字节 32位，16是中位数
因为大部分情况下，都是低16位参与运算，高16位可以减少hash冲突

2、为什么要进行异或运算？

因为&和|都会使得结果偏向0或者1 ,并不是均匀的概念,所以用^

^：异或运算，相同置0，不同置1

& ：与运算，两个同时为1，结果才为1

| ：或运算，只要有1 结果就为1

五、HashMap的put过程

1、源码解读

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //tab：哈希数组，p：该哈希bucket的首节点，n hashMap的长度，i 计算出的数组下标
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    //数组为空进行首次扩容，使用的是懒加载，table一开始是没有加载的，等put后才开始加载
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
   
    //如果该bucket的位置没有值，则把新插入的key-value放到此处
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    //发生hash冲突的情况
    else {
        //临时结点
        Node<K,V> e; K k;
        //1、插入的key-value的hash值，key都与当前节点的相等，e = p，则表示为首节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //2、hash值不等于首节点，判断该p是否属于红黑树的节点
        else if (p instanceof TreeNode)
            //p为红黑树的节点，则在红黑树中进行添加，如果该节点已经存在，则返回该节点（不为null），该值很重要，用来判断put操作是否成功，如果添加成功返回null
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //3、p不为红黑树的节点，则为链表的节点
        else {
            //遍历该链表
            for (int binCount = 0; ; ++binCount) {
                //如果找到尾部，则表明添加的key-value没有重复，在尾部进行添加
                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，e则为当前重复的节点，结束循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        //有重复的key，则用待插入值进行覆盖，返回旧值。
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //到了此步骤，则表明待插入的key-value是没有key的重复，因为插入成功e节点的值为null
    //修改次数+1
    ++modCount;
    
    //实际长度+1，判断是否大于临界值，大于则扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    //添加成功
    return null;
}

2、计算索引为什么使用(n - 1) & hash

主要是为了使用位运算代替取模运算，更加高效

1
2
3

//如果该bucket的位置没有值，则把新插入的key-value放到此处
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

int index=hash&(n - 1);
    //假设n为16
    1001 1011 //155
   &     1111 //16-1
   ——————————
         1011   //直接舍弃前面N位，取后4位，特别高效

将hash值与阈值进行位运算获得数组中的索引，当一个int值a是二的次幂的时候，h跟a-1进行与运算的时候，刚好结果是h % a，这是也是为什么HashMap的数组大小需要为2的整次幂的原因之一，也是导致hash冲突的原因（可能2个索引在一个位置）。

六、HashMap的扩容：resize()

1、源码解读

/**
 * 初始化或两倍扩容
 */
final Node<K,V>[] resize() {
    //把没插入之前的哈希数组作为oldTal
    Node<K,V>[] oldTab = table;
    //old的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //old的临界值
    int oldThr = threshold;
    //初始化new的长度和临界值
    int newCap, newThr = 0;
    //oldCap > 0也就是说不是首次初始化，因为hashMap用的是懒加载
    if (oldCap > 0) {
        //大于最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            //临界值为整数的最大值
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //标记##，扩容两倍，并且扩容后的长度要小于最大值，old长度也要大于16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //临界值也扩容为old的临界值2倍
            newThr = oldThr << 1; // double threshold
    }
    /**
     * 如果oldCap<0，但是已经初始化了，像把元素删除完之后的情况，那么它的临界值肯定还存在，        
     * 如果是首次初始化，它的临界值则为0
     **/
    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);
    }
  
    //此处的if为上面标记##的补充，也就是初始化时容量小于默认值16的，此时newThr没有赋值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        //判断是否new容量是否大于最大值，临界值是否大于最大值
        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
    table = newTab;
    //此处是把old中的元素，遍历到new中
    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 { // preserve order
                    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;
                        }
                        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;
                    }
                }
            }
        }
    }
    return newTab;
}

2、为什么数组长度按照两倍扩容

可以参考上面计算索引为什么使用(n - 1) & hash,因为HashMap底层计算索引使用了位运算来代替取模运算，因此，只有当数组长度为2的整次幂时，n-1是一个全为1的二进制数，当为1的二进制数与key的hash值进行&运算的时候效果等同与hash值对数组长度的取模运算，这也是导致hash冲突的原因。