05月25, 2020

【java基础系列】-Map集合之HashMap(java8)

提起Map想必大家都不陌生,用的最多的比如:HashMap、TreeMap、ConconrentHashMap等等,本文主要介绍HashMap底层的一点东西,说的不全,后续会继续补充。。。

你懂得越多,你不懂的越多

简介

HashMap在java.util包下,是AbstractMap的字类,属于非线程安全集合,HashMap的源码相信很多人都看过,我再稍微总结下,做个笔记,以便后续复习, 先介绍下HashMap类的几个变量:

  • DEFAULT_LOAD_FACTOR = 0.75f :默认装载因子(0.75)

  • EFAULT_INITIAL_CAPACITY = 1 << 4:默认初始容量(16)

  • MAXIMUM_CAPACITY = 1 << 30:最大容量(2^30)

接下来通过一个例子一步步介绍它底层的一些逻辑,首先是构造方法,HashMap提供了4中构造方法:

//四种构造方法
public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity)
public HashMap() 
public HashMap(Map<? extends K, ? extends V> m)

具体的实现这里不多说了,重点是前三种构造方法,虽然有初始容量和负载因子,但是方法内部都没有去初始化一个table。具体什么时候回初始化,下边会介绍到。

扰动函数

介绍扰动函数之前,我们先看下HashMap的put()方法,可以看到在put方法里边还有一个putVal()方法

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

然后在这个方法里有个hash(key),这个函数即被称为扰动函数(到底是什么的扰动,下边再说),源码如下:

static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

方法的实现非常简单,首先获取key的hashCode(就是最底层的hashCode()),然后将hashCode右移16位,之后两者异或。先说下这样做的好处是可以让hashCode的高低位都参与到index(数据在map中的位置)的计算中,具体原因下边再说。

 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)   //1
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)   //2
            tab[i] = newNode(hash, key, value, null);
        else {
        ......

进到putVal()方法的内部,我们只看前半部分,后边的扩容逻辑暂时不看,注意注释位置

  • 1、首先判断table是不是空,如果是空则resize()初始化,上边说的构造函数未初始化的table,就是在这初始化的,这块有点像懒加载,用到的时候才创建

  • 2、计算一个位置(index),看这个位置是否为空,如果为空则新建一个节点,可以看到计算方式为(n - 1) & hash,这里的n指的是table的长度,hash其实就是上边扰动函数算出的hash值(高低16位异或那个),这个地方还牵扯到另一个点就是为什么table的容量必须是2的n次幂,即便初始化的时候构造参数不是2的n次幂,hashmap内部也会转成2的n次幂大小(就是下边这个方法)。

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

这里就是通过一系列的右移+位或操作,因为操作只要有一个1结果就是1,这样就可以将位都变成1,比如10二进制为1010,右移1位为0101,位或结果为1111,之后再右移、或操作结果都是1111,对应十进制为15,最后得到n+1=16。为什么一定要转为2的n次幂,往下看。

2的n次幂

这里之所以把2的n次幂作为一个模块,是因为之前一直没搞懂这块(异或、与操作啥的,乱七八糟),所以打算着重记录下,这里主要介绍两个方面:一是为什么集合容量一定是2的n次幂;其次是这块和扰动函数之间的关系。

我们知道,hash函数主要关注的无非两点(分布均匀和较低的碰撞率),其实只需要关注碰撞率就好。碰撞率低数据分布自然均匀,这里的2的n次幂扰动函数就是实现低碰撞率的,具体怎么实现呢,往下看:

我们假设容量n=2^4=16,那么n-1=15用二进制标识就是01111,下面列举4个随机数与01111与操作。

alt

可以发现结果都不同,很好的避免了hash碰撞。

如果容量不是2的n次幂,假如容量n=10,那么n-1=9,用二进制表示为01001,同样对4个数进行与操作,很明显有3个结果是重复的,说明碰撞率很高。

alt

到这里我们知道了为什么容量一定是2的n次幂,那扰动函数起什么作用呢?上边说到扰动函数是将hashCode 的高低16位进行异或操作,为的是让高低位都可以参与到index的计算中,我们还是举个例子说明:

假设容量n=16n-1=15二进制是01111,hash=....1010 0000 0110 0110,我们知道0与任何数都是0,那么hash&(n-1)=(....1010 0000 0110 0110) & (01111)=.......0110,这里的结果省略了前边的一堆0,可以看到结果就是hash的后四位(0110)。

那么如果不使用扰动函数,直接hashCode & (n-1),这样的话如果两个数的hashCode的后四位一样,比如.....0101 0110......0110 0110,计算出的结果都是0110,碰撞率很高,所以相比于直接使用hashCode,扰动函数计算出的hash值,hash结果就没那么碰巧。

讲到这里,我们应该知道为什么容量取2的n次幂引入扰动函数,其实两者是结合使用的,都是为了减小碰撞率

至此,我们大致了解了HashMap的为避免hash碰撞的做法和逻辑,下边我们分析下发生hash碰撞后HashMap做了什么?

putVal()后半段(hash碰撞解决过程)

我们接着看putVal()方法,看下半部分的逻辑

 else {      //发生了碰撞
     Node<K,V> e; K k;
         if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))             //1、相同key,直接覆盖
             e = p;
         else if (p instanceof TreeNode)                                  //2、是否是红黑树的节点
             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
          else {                   
            for (int binCount = 0; ; ++binCount) {        //3、尾插法插入元素
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)         //3-1 、判断链表长度是否大于默认值8
                        treeifyBin(tab, hash);
                        break;
                 }
                 if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))    //3-2、链表中是否有相同的key
                        break;
                    p = e;
              }
         }
         if (e != null) {                 
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
         }
  }
        ++modCount;
        if (++size > threshold) 
            resize();
        afterNodeInsertion(evict);
        return null;

这段主要是发生hash碰撞后的处理流程,根据注释位置,大致介绍下:

  • 1、这里的p指的是上边根据(n-1) & hash算出的位置所对应的值,如果key和hash值相同,说明是同一个key,直接覆盖

  • 2、判断是否是红黑树的节点,如果是则直接put,红黑树相关操作后续再说。

  • 3、不是相同的key,且不是红黑树节点,走正常的添加逻辑,也就是尾插法将元素放到最后一个位置,在这中间有两个判断,

    • 3-1、判断链表的长度是否大于临界值8,如果大于则进入一个叫treeifyBin(tab, hash)的方法,这个方法在这就不细说了,主要做了两件事:如果整个table的长度小于64只进行resize()扩容,否则如果长度大于64则将当前链表结构转为红黑树
    • 3-2、 在尾插法遍历过程中,如果发现有相同的Key,直接break跳出循环。

至此,我们已经了解了HashMap的put大致流程,接下来看下HashMap的扩容机制。

扩容机制 resize()

我们知道,当table的长度大于64并且某一链表的长度大于8的时候,会触发扩容,也就是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) {              //1、如果原始table的长度大于最大值(2^30),将临界值设为int的最大值
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
        //2、如果老数组长度的2倍<最大容量 && 老数组的长度>默认容量,将新的临界值设为原始临界值的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);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;                           //3、到此为止,计算出了新的capcity(容量)和threshold(临界值)
        @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) {             //4、遍历老数组,复制元素到新数组
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)         //5、如果链表只有一个节点,直接放到 hash & (newCap - 1) 位置
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)               //6、如果是红黑树节点,走红黑树扩容逻辑
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {                                                            //7、链表扩容逻辑(重点,下边细说)
                        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) {       //7-1、判断元素在新数组中的位置是否需要改变
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {                                   // 8、需要改变位置的链表尾插逻辑
                                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;        //9、需要改变位置的链表放到table中的新位置
                        }
                    }
                }
            }
        }
        return newTab;
    }

以上就是rezise()扩容机制的详细流程,下边重点说下普通链表的扩容逻辑(注释7),首先判断的是元素在新数组的位置是否需要改变,判断公式为e.hash & oldCap,注意不是hash & (oldCap-1),下边举几个个例子说明下,假设初始容量是oldCap=16(0001 0000),扩容后容量为newCap=32(0010 0000)

1、 假设e.hash=10(0000 1010),那么e.hash & oldCap = 10(0000 1010) & 32(0010 0000)=0(0000 0000),结论是扩容后不需要变更位置,,我们验证下:

  • 扩容之前的index=e.hash & (oldCap-1)=10(0000 1010) & 15(0000 1111) = 10(0000 1010)

  • 扩容后index=e.hash & (newCap)=10(0000 1010) & 31(0001 1111) = 10(0000 1010),扩容后位置不变

2、假设e.hash=17(0001 0001),则e.hash & oldCap = 17(0001 0001) & 16(0001 0000)=16(0001 0000),结论是扩容后需要变动位置,解释如下:

  • 扩容之前的index=e.hash & (oldCap-1)=17(0001 0001) & 15(0000 1111) = 1(0000 0001)

  • 扩容后index=e.hash & (newCap)=17(0001 0001) & 31(0001 1111) = 17(0001 0001),扩容后的位置变了

注释8意思是:如果改变链表头结点在table中的位置,则新建一个链表,再把新链表的头结点放到table中的新位置,对应注释9位置代码。可以发现新链表的头结点在table中的位置是newTab[j+oldCap],其实就是原始位置索引加上原始长度,这也对应了上边说的hash=17在原始table中的位置是1,rehash后在新table中的位置是17(1+16)。

拓展

说到扩容就不得不提一下jdk1.7中在多线程下扩容形成死链的问题,在jdk1.7中扩容使用的是头插法,核心代码如下:

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            //这个while循环是我们问题的关键
            while(null != e) {
                Entry<K,V> next = e.next;    //t1、线程1执行到此处
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);          //重新计算位置
                e.next = newTable[i];             //头插法插入当前元素
                newTable[i] = e;
                e = next;
            }
        }
    }

首先我们了解下头插法: 假设有3个元素,

1、插入元素a,此时e指向a,next指向b

2、插入b,此时e指向b,next指向c:

3、插入c:

alt alt alt

死链的产生:当两个线程都执行扩容方法时,假设线程1执行到代码注释t1处(此时e指向的是a),此时线程2来了,重新执行了扩容并将table更新为newTab,这时线程1来了,对于线程1来说,由于e指向的是a,然后执行代码e.next = newTable[i],e.next指向了链表的头结点(也就是c),然后又执行newTable[i] = e后将头结点赋为a,此时的结构就像下图这样

alt

在jdk1.8中采用尾插法避免了死链的问题,但是这并不意味着在jdk1.8中可以在并发场景下使用HashMap,因为它内部并没有集成锁机制,多线程下仍然存在数据不一致的情况。至此,我们大致了解了HashMap的扩容机制以及jdk1.7中的死链相关问题。

小结

此篇文章大概介绍了HashMap中的几个关注点:扰动函数table长度为什么是2的n次幂hash碰撞解决扩容机制(resize)以及jdk1.7死链问题。至于扩容引入的关于红黑树相关知识,后期打算单独拉一个模块来详细介绍下,这里就不多说了。

注:此文章仅为自己的相关理解,如有理解不正之处,望请指正!!!

本文链接:http://blog.keepting.cn/blog//post/java_map_hashmap.html

-- EOF --

Comments