JDK11源码--HashMap源码分析

2019-03-19 10:05:33 114

@[toc]

概述

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

hashmap数据结构

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

上图中,左侧方形表示的是数组,初始化状态长度是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中已经删除。但是在其他代码段中依然是采用类似的方式寻找的:
image

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分布)

image

hashmap中的泊松分布

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

大体意思也就是说,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个数据(即数组后面的链表的数据量)的概率:

存储数据量 概率
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

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值==。

描述
key的hash值 00000101 00101101 10010100 01000010
无符号右移16位 00000000 00000000 00000101 00101101
两者异或结果 00000101 00101101 10010001 01101111

这样做的墓地是避免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)

编程语言 java 源码 node HASH static JDK hashmap 存储 数组

作者

快乐崇拜007
TA的文章

相关文章