@[toc]

概述

本文介绍JDK11中HashMap的源码实现。

hashmap数据结构

map中存储的是key,value键值对。众所周知，hashmap是采用的 ==数组 + 链表 + 红黑树== 的数据结构存储数据的：

上图中，左侧方形表示的是数组，初始化状态长度是16。数组中每个元素我们这里称之为桶，桶存储的是key的hash值，每个桶后面挂载着链表，链表中存储的是具体的数据value。

基本参数

/**
 * 默认的初始容量。
 * 必须是2的整数次方
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * map的最大容量
 * 也要是2的整数次方
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认负载因子
 * 
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 链表长度大于8时，转换为红黑树结构
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 扩容时，如果发现树中节点数量小于6，则将树还原为链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * map容器中某个箱子（bin）再有链表转为树之前还要满足键值对数量大于 64 才会发生转换。
 * 目的是为了避免 resizing（扩容） 和 treeification（链表转树结构）之间的冲突
 */
static final int MIN_TREEIFY_CAPACITY = 64;

MAXIMUM_CAPACITY为什么设置成1 << 30

MAXIMUM_CAPACITY含义是map的最大容量。它是int类型，使用<<移位运算符的结果不能超过int可以表示的最大值。固最大只能左移30，再大就溢出了。

java中的int占4个字节，每个字节8位，所以总共是占用32位。int是有符号的，其中第一位是符号位。所以还剩下31位。那么最多就是左移30了。
1 << 2 = 4(十进制) = 100(二进制)

为什么map的容量要限制为2的整数次方

上面已经提到map的数据结构是数组加链表的结构。
那么如何才能快速定位某个键值对的位置呢？
老版本的源码中有这么一个方法，获取元素的位置：

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

上述代码在jdk11中已经删除。但是在其他代码段中依然是采用类似的方式寻找的：

tab是数组，n是数组长度，hash是要查找的key的hash值。
tab[(n-1) & hash] 含义就是根据hash值快速定位到数组的位置。
由于数组长度是2的整数次方，n-1转为二进制就都是1111（初始化情况下）。这样进行 & 计算的结果就与hash一样，也就定位到了数组中的位置。
那么为什么是2的整数次方呢。假如不是2的整数次方，length为15，则length-1为14，对应的二进制为1110，在于h与操作，最后一位都为0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，==空间浪费相当大==，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着==进一步增加了碰撞的几率==，减慢了查询的效率！这样就会造成空间的浪费。也就是说设置2的N次方，可以使得==数据分布更加分散，减少碰撞==

DEFAULT_LOAD_FACTOR负载因子为什么是0.75

泊松分布（Poisson分布）

hashmap中的泊松分布

在hashmap的注释中也给出了泊松分布的公式及各参数作用的注释：

大体意思也就是说，treenode占用的空间是常规节点的两倍，所以只有当bin（指数组中的一个桶，这里也可以翻译为箱子）中元素数量超过TREEIFY_THRESHOLD时才会使用treenode。
在hash分布比较均匀的情况下，很少使用treenode。
在随机hashCodes情况下，bin中节点出现的频率遵循Poisson分布。此时load factor（即DEFAULT_LOAD_FACTOR）=0.75f，λ=0.5。
调整load factor，λ会出现比较大的偏差。

假如在长度为length=16的数组中放入0.75*length=12个数据时，数组中某一个下标放入k个数据（即数组后面的链表的数据量）的概率：

hashmap扩容到32或者64时，一个bin中存储8个数据量的概率都是0.00000006。
所以，当某一个bin（链表）的节点数大于等于8个的时候，就可以从链表node转换为treenode，其性价比是值得的。

重要属性

/**
 * 存储hash的数组，首次使用时初始化
 * 长度总是2的真实次方
 */
transient Node<K,V>[] table;

/**
 * 存放实际的键值对
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * mao中元素总数量
 */
transient int size;

/**
 * 每次扩容和更改map结构的计数器
 */
transient int modCount;

/**
 * threshold =  (capacity * load factor)
 * 该字段用于判断核实扩容
 */
int threshold;

/**
 * 负载因子
 */
final float loadFactor;

重要方法分析

构造函数

这里分析一下HashMap<String, String> map = new 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
   }

构造方法都是设置几个参数值，并没有实际初始化数组与链表。这样可以节省一点空间。
在首次put时会调用resize()方法来初始化数组tab。

这里注意tableSizeFor()这个方法,该方法==返回最近的不小于输入参数的2的整数次幂==。比如10，则返回16：

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

先说Integer.numberOfLeadingZeros这个方法，他的作用是==返回无符号整型i的最高非零位前面的0的个数，包括符号位在内==。具体代码分析请参见 jdk11源码--Integer.numberOfLeadingZeros。

假如cap=10 ，10的二进制表示是00000000 00000000 00000000 00001010。人工计算一下，大于10的最小2的n次方大于10且距离10最近的应该是16，二进制表示是00000000 00000000 00000000 00010000，也就是从右往左找到最后一个1，这个1右边的值全部改为1，然后再加1就是我们想要的结果了。
上述代码可以快速计算出结果。详细计算步骤如下：

• Integer.numberOfLeadingZeros(cap - 1) = 28，二进制表示是00000000 00000000 00000000 00011100

• n=-1>>>28=15

  • -1二进制原码是10000000 00000000 00000000 00000001
  • -1反码是11111111 11111111 11111111 11111110
  • -1补码是11111111 11111111 11111111 11111111 (知识点：负数的补码 = {原码符号位不变} + {数值位按位取反后+1})
  • 所以-1带符号右移28位是00000000 00000000 00000000 00001111=15(十进制)
• 最终结果是15+1=16.

put() 及 hash 算法

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

//计算hash值。这里在获取了hash值以后，又进行了一次异或计算。目的是为了尽可能减少hash碰撞。
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}


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)//初始化时肯定为null
        n = (tab = resize()).length;//初始化时在这里调用resize()进行数组的初始化
    if ((p = tab[i = (n - 1) & hash]) == null)//数组中某个tab位是空的，也就是后面没有挂载链表 ，没有数据
        tab[i] = newNode(hash, key, value, null);//则直接创建node对象，挂载数据即可
    else {//数组中某个tab已经有数据存在了，则这里进行链表构建
        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);
        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);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // key相同时更新value
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();//如果超过阈值，则扩充map大小
    afterNodeInsertion(evict);
    return null;
}

我们首先来看一下上面的hash函数，jdk中没有直接使用hashcode()作为hash值，而是现==将hashcode()值无符号右移16位得到新值，然后hashcode()与这个新值进行异或计算得到最终的hash值==。

这样做的墓地是避免hash碰撞。比如，在n - 1为15(0x1111)时，散列值真正生效的只是低4位。当新增的键的hashcode()是2，18，34这样恰好以16的倍数为差的等差数列，就产生了大量碰撞。
因此，设计者综合考虑了速度、作用、质量，把高16bit和低16bit进行了异或。因为现在大多数的hashCode的分布已经很不错了，就算是发生了较多碰撞也用O(logn)的红黑树去优化了。仅仅异或一下，既减少了系统的开销，也不会造成因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。

resize()

接下来看resize()方法。

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)
                 //将当前数组长度扩大一倍
            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);
    }
    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) {
    //循环遍历老map中的所有数据，迁移到新数组中对应位置，进行扩容操作
        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;
                        //这里通过当前hash与数组长度进行逻辑与操作，判断是否为0，来区分该元素是不变位置还是需要重新更换位置
                        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;//现有index+现有数组的长度就是新数组中的索引位置
                    }
                }
            }
        }
    }
    return newTab;
}

代码分析

• 当初始化hashmap时，按照threashold进行初始分配内存
• 扩容时，数组会扩容两倍，采用右移一位算法
• 扩容时，现有数据位置要么不动，要么是（当前索引+现有数组长度）
• 扩容时不会重新计算hash值，key的hash值会保存在node元素中。
• 上述代码中有个(e.hash & oldCap) == 0的计算，这一步的意思是判断这个元素是应该不动，还是应该迁移到新的位置。下面举例说明：

我们以map.put("a1", "aa1")为例，a1计算后的hash值是3056，初始化情况下，存储在数组中的位置是0：

00000000 00001111 【初始化数组长度是16，(16-1)对应二进制】
00001011 11110000 【3056的二进制】
&
00000000 00000000 【逻辑与计算结果是0】

扩容时，数组长度增加一倍，变为32。计算a1是否应该迁移，迁移到什么位置。首先，将a1与16进行逻辑与计算，结果是1，所以要进行迁移：

00000000 00010000 【初始化数组长度是16，对应二进制】
00001011 11110000 【3056的二进制】
&
00000000 00010000 【逻辑与计算结果是1】

那么扩容后迁移的新位置的索引是：

00000000 00011111 【扩容后数组长度是32，（32-1）对应二进制】
00001011 11110000 【3056的二进制】
&
00000000 00010000 【逻辑与计算结果是16（正好是0+16）】

==如果将aX与16进行逻辑与计算，结果是0，那么上述数组长度32的逻辑与计算的结果肯定与长度16的计算结果一致，因为高位结果是0.==

treeifyBin() 链表转为红黑树

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)
        resize();//为空或者容量小于MIN_TREEIFY_CAPACITY（默认64）则不进行转换，而是进行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);//根据链表的node创建treenode
            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);
    }
}

• (n = tab.length) < MIN_TREEIFY_CAPACITY表示不仅仅是单个链表长度超过8，还要数组长度大于64才进行红黑树的转换，否则进行扩容。红黑树占用空间大，hashmap的设计是尽可能不用。

更多红黑树的内容参见：红黑树详解

get()

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {//map不是空的
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;//根据hash定位到数组中位置后，读取的第一个元素就是要找的元素
        if ((e = first.next) != null) {
            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;
}

• 红黑树查询时间复杂度 O(logn)
• 链表查询时间复杂度 O(n)