• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

Map(一)之HashMap(java8)

java 来源:左撇子小哥哥 1次浏览

概述【本文基于jdk1.8.0_60】

  在我们日常开发中,HashMap被使用到的概率非常高。它是一种非常典型的数据结构。我们应该都知道Map是存储key-value键值对的集合类,也就是说元素是成对出现的。并且key可以为null但必须是唯一的。
  

定义

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

  HashMap实现了Map接口,继承了AbstractMap。

基本属性

    /** * 默认初始容量(桶的数量),16 */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    /** * 最大容量1*2^30 */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /** * 默认装载因子,此值表示当前容量的HashMap装entry满的程度,当entry数量大于当前容量与装载因子的 * 乘积时,HashMap就会进行rehash操作。也就是HashMap会扩充容量,扩充容量之后整个HashMap就会 * 重建 */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /** *当“桶”中的元素大于此阀值时使用树代替单向链表,这里的树实际上是红黑树 */
    static final int TREEIFY_THRESHOLD = 8;

    /** * 当“桶”中的元素小于此阀值时,树转成单向链表 */
    static final int UNTREEIFY_THRESHOLD = 6;

    /** *HashMap中所有元素总数小于此值时,即使“桶”中元素超过TREEIFY_THRESHOLD也不转成树 */
    static final int MIN_TREEIFY_CAPACITY = 64;

构造

    //默认构造方法,装载因子设置为默认值0.75
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    //指定初始容量和加载因子
    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);
    }
    //使用一个Map来初始化一个HashMap
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

底层存储

    /** *HashMap底层实际上是一个Node<K,V>类型的数组 */
    transient Node<K,V>[] table;

简单画一下HashMap底层存储结构图:

上图描述的是一个容量为16(即16个桶)的的HashMap结构图。可以理解为是一个长度为16的Node类型的数组,每个数组元素都是一个链表的head结点。于是乎就构成了上面的结构。我们用默认构造方法创建的HashMap在没有resize之前容量就是16。

resize与树化

  随着结点的增多,单个桶中的元素越来越大,即链表的长度越来越长。这样会导致get,remove(大家可以想一下链表的相关操作)等的性能越来越差,怎么办呢?HashMap中有对应的解决方案。

resize

  HashMap中有一个叫做threshold的参数:

    /** * The next size value at which to resize (capacity * load factor). */
    int threshold;

这个参数表示当HashMap的size达到此值时就要进行resize操作。它是怎么计算来的呢?计算公式如下:

threshold = capacity * load factor

拿上图举个例子,假如上图的HashMap是通过默认构造方法创建的。其中HashMap的容量为16,load_factor为默认值0.75 。所以threshold = 16 * 0.75 = 12 。也就是说当元素个数达到12时,就会发生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语句块
        if (oldCap > 0) {
            //容量不能超过MAXIMUM_CAPACITY上限
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            //新容量为旧容量的2倍,新阀值为旧阀值的两倍。(<<1表示2进制左移一位,也就是乘以2)
            } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        //这个分支是应对使用不能构造方法创建HashMap的情况
        } 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;
        //创建一个更大容量的Node数组
        Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
        //把新创建的数组赋值给table属性
        table = newTab;
        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;
                            /** *下面的是把旧HashMap中的元素放到新HashMap。映射算法后面再详细讲解 */
                            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;
    }

树化

  我们观察会发现HashMap有两个属性:

    static final int TREEIFY_THRESHOLD = 8;
    static final int MIN_TREEIFY_CAPACITY = 64;

当HashMap的容量大于MIN_TREEIFY_CAPACITY 并且桶中元素数量大于等于TREEIFY_THRESHOLD 时,该桶中的元素结构就会由链表结构转成结构以提高性能。看下源码:

   final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //这里是保证桶中元素和HashMap容量同时满足条件才对相应桶进行树化。否则只进行resize操作
        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;
            /** *这里可以理解为把链表中每个结点都替换成树结点,世界上是创建一个新链表,结点类型 *由Node变为TreeNode */
            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);
        }
    }

看一下树化之后的HashMap结构长什么样:

上图编号为1023的桶由于数量超过了阀值,所以有链表转成了形结构。关于链表转成树的具体算法这里就不详细讲解了。
有树化过程当然就有“非树化”过程,我这里树的非树化就是树转链表。当然如果我们频繁做remove操作,链表里面的元素越来越少就会进行逆向操作。相应的“非树化”阀值参数定义如下:

    /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */
    static final int UNTREEIFY_THRESHOLD = 6;

意思是当桶中元素个数小于UNTREEIFY_THRESHOLD 时,就会由转成链表,当然,前提是你之前已经进行了树化操作。

其他创建流程

  HashMap提供了4个构造方法,这使我们可以在创建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);
    }

假如我们想创建一个初始容量为30的HashMap,也许你会这样写:

Map<String, Object> map = new HashMap<>(30);

我们这样写实际上调用的是 public HashMap(int initialCapacity, float loadFactor) ,这里loadFactor是默认值,我们不管它,看最后一句。

this.threshold = tableSizeFor(initialCapacity);

啊?initialCapacitythreshold什么关系?是不是感觉有点混乱?我们刚刚不是想创建容量为30HashMap吗?为何这里把initialCapacity通过计算赋值给了threshold?别急!我们一步步来,先来看下这个tableSizeFor方法时干嘛的,上源码:

    /** * Returns a power of two size for the given target capacity. */
    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;
    }

它的作用是根据传入的容量,返回2幂次方大小的容量。你刚刚传的是30,这里会返回2^5=32。但是这个值也没有赋值给initialCapacity参数呀?继续看:
  我们知道我们虽然new HashMap(30),但此时HashMap里面的真正用来存储数组的Node数组table还是null呢:
  

   transient Node<K,V>[] table;

  此时当我们往HashMapput元素时,如果table==null,就需要进行第一次resize操作:
  
  
我们继续看resize方法:
  
这里会把threshold 的值赋给newCap,然后根据这个newCap创建一个Node数组赋给table。然后根据newCap计算一个threshold赋值给threshold。此时的newCap的值为32,threshold的值为24 。所以我们刚开始使用Map<String, Object> map = new HashMap<>(30); 创建的map的容量不是30,而是32

HashMap中映射算法介绍

  • 1 key映射到桶

      我们拿get(object key)方法来分析,key是如何映射到桶的,也就是HashMap如何知道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;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            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;
    }

仔细观察有这么一行代码:tab[(n - 1) & hash] 其中hash的值就是key的哈希值,从中我们可以大致知道hash值是怎么映射到桶的。接下来我们通过例子来更深层次的探讨下:
  假如我们通过构造方法创建了一个HashMap,那么它的初始容量是16。现在我们往HashMap中添加4个元素。假如这4个元素key的hash值分别是6、22、38、54(具体key的值是多少我们这里就不列出了)。现在我们看下这4个元素会映射到哪个桶?由于容量是16,所以n=16,那么n - 1) & hash 代入n就变成了15 & hash。我们把6、22、38、54 分别于 15 进行按位与操作,换算成二进制:
  
计算之后的结果全是6,于是这四个元素全部放到了table[6]中,即第6个桶。另外由于15二进制001111,除了低四位为1,其他高位全是0 。所以与15进行按位与结果永远不会大于15,所以不会超出table大小范围。这四个元素放到HashMap中的结构如图:

  • 2 resize时key的重新映射
      接着上面的例子讲,随着HashMap中元素的增多,我们建立的HashMap容量是16,加载因子loader_factor0.75 。所以threshold = 16*0.75 = 12 所以当元素数量超过12时,HashMap就会resize。假如现在上例中元素刚好达到12,第6个桶中的元素还是上述那四个元素。我们看下这四个元素分别会重新映射到新table中的哪个桶。在开始讨论之前,先看下重新映射的代码:
      
      
    我们知道原来HashMap的容量是16,resize之后容量是32 。旧数组中的元素映射到新数组中的算法就如上图所示。是不是有点晕?为什么要这样算呢?我们先看一下resize之前和之后往HashMap中添加元素是如何映射的,以key的hash值是6、22为例,映射算法分别是6 & 156 & 3122 & 1522 & 31,换算成二进制计算如下图:

  如上图所示,我们只观察从右往左第5位(前面4位都是一样的),6的第5位为0,所以不论是与15还是31进行按位与操作结果都是一样的。然而22的第5位为1,所以与1531的按位与结果不同。与31的按位与结果比15大了010000,也就是16(未resize前的容量大小)。可以理解为resize之后,元素在新HashMap中桶的位置是否改变,取决于原第5(在这个例子中是第五位)位是0还是1。那么代码中的算法就是按照第5位是0,还是1进行了分组。代码中的hash&oldCap,刚好可以区分第5位是0还是1 。看例子:
  

结果为0的第5位是0,否则第5位不为0 。
说明一下:上述算法只有当resize之后是之前的2倍的基础上才成立。换算成2进制就是左移了一位:newCap = oldCap <<1 ,这个是必要条件。否则上述算法就不对了。不知道我有没有讲清楚。
下面看下resize前后结构图:

HashMap的bug

  我们知道,旧版本jdkHashMap在多线程条件下rehash操作有可能会产生无限循环的问题。不了解此问题的麻烦搜索下相关问题,这里不做描述。在jdk1.8中(我研究的这个版本),此问题已经得到解决。(我看其他人写的博客中还提到说java8中hashMap死循环的问题,他们应该是搞错了)。产生无限循环的本质就是链表中产生了,而java8中不具有产生环的条件,所以不会产生无限循环。但是产生了其他bug。

1. 为何不会产生环

  java8中resize时对每个桶进行的操作都是先将链表拆分成两个链表,然后分别将两个链表放到新table中对应的桶当中去。这个过程在多线程条件下不会产生环。

2. 其他bug(多线程条件下)
  • 1 HashMap中有值,但是get出来为null。
      来看下resize时有这么一行代码:
      
      如上图所示,在进行真正的元素移动前,先将newTab赋值给了table,这时table是空的,什么都没有,假如这个时候进行get操作,什么都取不到。
  • 2 resize时元素丢失问题。
      假设同时又两个线程thread1、thread2同时进行resize操作,初始状态图如下:
      
      
      图中红色代表thread1,银灰色代表thread2,此时thread2被挂起,thread1执行到如下图:
      
      
      
      此时仔细观察会发现thread2指向的链表少了一个节点c。倘若此时thread1被挂起,thread2执行,直到遍历完整个链表:

 

此时thread1执行到遍历完整个链表,结果如下图:

此时thread2中少了一个元素,现在如果thread1先将结果赋值给新table,thread2再进行赋值操作,那么thread2就会覆盖thread1的结果。这样就导致resize之后少了一个元素。

如有发现文章中有任何错误,麻烦留言指出。谢谢~


版权声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。
喜欢 (0)