阅读 109

容器类源码解析系列(三)—— HashMap 源码分析(最新版)

容器类源码解析系列(三)—— HashMap 源码分析(最新版)

前言

本篇文章是《Java容器类源码解析》系列的第三篇文章,主要是对HashMap的源码实现进行分析。强烈建议阅读本文之前,先看看该系列的前两篇文章:

  1. 容器类源码解析系列(一)ArrayList 源码分析——基于最新Android9.0源码
  2. 容器类源码解析系列(二)—— LinkedList 集合源码分析(最新版)

要点

  • HashMap 内部是基于数组加链表结构来实现数据存储,这句话在jdk1.8版本之后,就不准确了。因为在JDK1.8版本之后,HashMap内部加入了红黑树的数据结构来提高数据查找效率。所以现在应该改为数组加链表(红黑树)。
  • HashMap支持NULL 键(key)、NULL 值(value),HashTable不支持。
  • HasMap 是非线程安全的,所以在多线程并发场景下,需要加锁来保证同步操作;HashTable是线程安全的。
  • HashMap具有fai-fast机制的,关于fail-fast机制,我在该系列第一篇文章有讲解。容器类源码解析系列(一)ArrayList 源码分析——基于最新Android9.0源码
  • HashMap的树化条件是链表深度达到阀值8,同时数组长度(capacity)要达到64.

准备

先了解一下分析HashMap源码,需要知道的一些内容。

DEFAULT_INITIAL_CAPACITY = 1 << 4 默认的capacity(容量)大小

MAXIMUM_CAPACITY = 1 << 30 最大的capacity

DEFAULT_LOAD_FACTOR = 0.75f 默认的加载因子

TREEIFY_THRESHOLD = 8 链表树化阀值(链表长度)

UNTREEIFY_THRESHOLD = 6 反树化,TreeNode->Node

MIN_TREEIFY_CAPACITY = 64 链表树化阀值(capacity)

Node<K,V>[] table 存储数据的容器

Node<K,V> 类,当数据量不大,没有达到树化条件时,HashMap的存储节点结构。

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

        ...
        ...
    }
复制代码

TreeNode<K,V> 存储数量较大,满足树化条件时,HashMap的存储节点结构。

static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<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);
        }
        ...
        ...
        
}
复制代码

树化前:

树化前

树化后:

红黑树直接拿的wiki上面的图,省事!😀

树化后

图可能画的不准确,大概就是这个意思,帮助理解的,don’t care little things!

构造

HashMap提供四种构造方法,可以分为两类,一类是单纯设置capacity和loadFactor这两个成员变量的,创建一个空的hashmap;一类是传递一个Map集合参数,来赋值的。 我们先看第一类构造方法。

/**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    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);
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
复制代码

我们主要看第一个构造方法,第二个第三个比较简单,还有注释就不提了。在第一个构造方法中,可以看到先是对传进来的initialCapacity、loadFactor参数进行一个有效性判断,然后在赋值initialCapacity的时候对其值进行了一个处理,然后赋值给threshold变量,这个threshold是HashMap扩容时的阀值。在table数组没有初始化的时候这个threshold表示初始数组的capacity。 刚说了,对initialCapacity值做了一个处理,我们看看是什么处理;

	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;
    }
复制代码

上面的处理是对传进来的参数进行位操作处理,来实现return出去的数据是2的n次方。举个例子: 传进的值是11,减一后变成10;10的二进制表示是1010,进过位操作后,变成1111;1111+1 变成10000 转成10进制是16;是2的4次方。 一般来说通过这个方法实际赋的值都是大于等于传进来,期望的值的。 接着看第二类构造方法:

	public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
复制代码

它传进来一个Map容器,capacity和loadFactor都是用的默认值,分别是16和0.75f。这里提一嘴,默认的loadFactor值0.75f是经过测试比较合适的一个平衡点,如果传入的loadFactor值比较大,虽然可以减少内存空间的消耗但是会增加数据查找的复杂度。因为扩容操作是很耗性能的,所以在构造HashMap时,应该根据自己需要存储的数据量大小来设置合适的capacity,避免出现扩容操作。

	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);
            }
        }
    }
复制代码

如果table数组没有初始化就先计算容量,然后在调用putVal方法,在执行putVal会有扩容判断处理,来对table进行初始化操作。这个在讲解put操作的时候在详解putVal方法的是实现逻辑。


扩容机制

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;//得到table数组的长度
        int oldThr = threshold;//如果table数组还没有初始化,threshold代表initial capacity,否则代表扩容阈值。
        int newCap, newThr = 0;
        if (oldCap > 0) {//table数组长度大于0
            if (oldCap >= MAXIMUM_CAPACITY) {//table数组长度达到最大值,不做扩容处理,一般不会达到这个条件
                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) // 这是通过构造方法设置了capacity,还没有初始化table数组时
            newCap = oldThr;//注释一
        else {               // 用了无参的构造方法,还没初始化table数组呢
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {//通过上面的分析,可以看出来,只有在“注释一”的case下,没有给newThr赋值了
            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) {//表示非初始化情况下,所以需要进行数据拷贝
            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;//直接把节点赋值到新的数组索引下,新数组的新索引通过“e.hash & (newCap - 1)”这种“与操作”来确定。
                    else if (e instanceof TreeNode)//如果节点是树节点,走红黑树的扩容逻辑
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 
                    else { // 注释二
                        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) {//等于0,扩容后索引的计算依然与扩容前一致
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else { //不为0,扩容后的索引值是旧的索引值加旧的数组大小
                                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;
    }
复制代码

通过上面的代码,我们知道正常情况下,扩容后的Capacity是之前容量的两倍。

上面的扩容逻辑,在每行代码后面已经给了注释讲解,比较简单,接着我们看*"注释二”*,可能看到这里会比较疑惑,为什么会有个等于零的判断,而且出现这么多Node变量作用感觉很相似,重复。之所以出现等于0 的判断是因为HashMap在扩容的时候,有一个特点是,如果节点的hash值&扩容前数组大小的值等于0表示该节点在扩容后新数组下的index索引跟之前的数组索引一致;不等于则新的数组索引为旧的数组索引+oldCapacity。

为什么又会这个结论?这根HashMap的索引计算有关,HashMap 中,索引的计算方法为 (n - 1) & hash,n表示数组长度。假如有一个Node节点的hash值为111001,OldCapacity是16(默认值)。那么:

扩容前:

111001 & (16-1)—> 111001&1111 = 001001(9)

扩容后:(Capacity变成了之前的两倍为32)

111001&(32-1)—> 111001&11111 = 011001(25)

扩容后节点的索引变了。这里我们注意下16的二进制表示:10000

假如hash值是101001,再看下结果:

扩容前:

101001 & (16-1)—> 101001&1111 = 001001(9)

扩容后:(Capacity变成了之前的两倍为32)

101001&(32-1)—> 101001&11111 = 001001(9)

这次扩容后节点的索引还是之前的索引,原因体现在我上面加粗字体,我们记住数组长度的二进制表示中1的位置,如果hash值对应的位置是0的话表示扩容后索引不变,是1的话扩容后索引是原来的索引加上原数组长度。


常规操作

put操作

官方介绍HashMap的"put","get"操作,说是时间复杂度是O(1),其实这是不准确的,他是假设hash散列操作能完全均匀分散到容器中去,现实中很难达到。

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

当调用put方法时,会进而调用内部的putVal方法,putVal接收四个参数。

Parameter1 是传进来的key的hash值;

Parameter4 fasle表示相同key的情况下替换value值,true的话就不改变原来的value

Parameter5 只有在初始化table数组的时候才是false,其他操作都是true。

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)//如果table数组还没有创建,那就先通过resize创建,并记录数组长度与引用
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)//传进来的key对应的数组索引下没有数据
            tab[i] = newNode(hash, key, value, null);//那就新创建节点数据存进去
        else { //对应索引下存在节点数据
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;//如果key的hash值相同,key也相同,那么替换原来value即可。
            else if (p instanceof TreeNode)//是树节点的话,说明已经树化了,要走红黑树的对应put逻辑。
                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) // 达到树化条件,链的长度为8
                            treeifyBin(tab, hash);//进入这个方法后,还有一个树化条件判断,数组长度有没有到达阈值。
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)//替换旧值
                    e.value = value;
                afterNodeAccess(e);//LinkedHashMap重写了这个方法,感兴趣可以去看看
                return oldValue;//返回旧值
            }
        }
        ++modCount;
        if (++size > threshold)//判断是否需要扩容
            resize();
        afterNodeInsertion(evict);//LinkedHashMap重写了这个方法,感兴趣可以去看看
        return null;
    }

复制代码

HashMap的默认put操作在遇到相同key,hash的时候,是会替换原来的value的,原因在onlyIfAbsent为false;

如果节点是普通节点则会把数据插入链尾,如果是树化节点TreeNode则会有树的相应插入逻辑。在作为普通节点插入数据至链尾的过程中会检测是否达到(可能)树化条件,达到的话会走树化逻辑。把普通Node节点变成TreeNode。

get操作

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

复制代码

代码比较少,首先先进行table数组有效性判断,获取目标索引下的头结点。如果头结点就满足key相等的要求,那自然是皆大欢喜,省事了。直接返回头结点即可。

不是头结点的话,它会接着判断是不是TreeNode,是TreeNode的话则走树对应的get操作;否则走普通节点的查找操作,即遍历寻找,找到后就返回对应的值没找到就返回null。

remove操作

public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
复制代码

remove方法会返回删除节点的value。我们看removeNode的逻辑。

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {//table数组有效性判断,获取对应索引的头结点
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))//巧了,头结点就是要找到节点O(∩_∩)O哈哈~
                node = p;
            else if ((e = p.next) != null) {//头节点不是要找到,那就接着看它的next节点
                if (p instanceof TreeNode)//头结点是TreeNode,那就走树的查找目标节点逻辑
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {//普通节点就遍历查找
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
              //如果找到了,再根据节点的类型,执行对应的逻辑
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)//如果头结点就是要找到节点,直接把头节点的next节点指向index索引即可
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
复制代码

结语

在分析源码逻辑的时候,可以发现主要分为两部分,一种是如果节点是TreeNode要走红黑树的查找,添加等逻辑;另外一种是走普通的链表逻辑。

为什么要在新的JDK中添加红黑树的数据结构,是为了提交效率,当链表过长,会拖慢效率,而红黑树的性能很好,对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。时间复杂度是O(log n)。而链表是最坏情况下的时间复杂度是O(n)。

本文主要是对HashMap的源码进行整体的分析,对于红黑树的算法逻辑细节没有提及。如果对红黑树这种结构有兴趣研究的话可以自行研究。

红黑树-wiki

宇宝守护神的个人站


扫码加入我的个人微信公众号:Android开发圈 ,一起学习Android知识!!

在这里插入图片描述

关注下面的标签,发现更多相似文章
评论