2.1、JDK 源码分析 - HashMap1.8

原创
2022/07/17 16:36
阅读数 183

摘要

上一篇博文,分享了HashMap1.7版本的底层实现;本篇文章将继续带着小伙伴们探索HashMap1.8的底层原理;JDK1.8中对HashMap的底层数据结构进行了优化,它不再是之前的"数组+链表"的方式,而是"数组+链表+红黑树"的方式来实现;由于,此序列博文主要主要内容是关于源码分析,所以文章中关于数据结构方面的知识会比较简略提到。更详细的数据结构方面的知识,博主将会在后期的专题栏目中进行分享。

数据结构-树简介

树:定义树的一种自然方式是递归方式。一棵树是一些节点的集合。这个集合可以空集;若不是空集,则树由称作根的节点r以及0个或多个非空的子树T1、T2、T3...,Tn组成,这些子树中每一棵的根都被来自根r的一条有向边所连接。

树按照分叉来分,有两种:

二叉树:是一棵树,其中每个节点都不能有多于两个的儿子。二叉树的一个性质是一棵平均二叉树的深度要比节点个数N小得多,这个性质很重要。分析表明 ,其平均深度为O(根号N),而对于特殊类型的二叉树,即二叉查找树,其深度的平均值时O(logN)。不幸的是,这个深度是可以大道N-1的(此时,树已经退化为链表结构)。

多叉树:是一棵树,其中每个节点可以有多个儿子。

二叉查找树:使二叉树成为二叉查找树的性质是,对于树中的每个节点X,它的左子树中的所有项的值小于X中的项,它的右子树中的所有项的值大于X中的项。另外,二叉查找树要求所有的项都能够排序。需要说明的是,二叉查找树在经过长时间的添加、删除等操作后,可能变得不平衡,或者说它的某些分支相对于其它一些分支会变得非常的深(此处,与它的删除算法有关,一般删除一个节点的时候,如果它有右子树,则使用右子树中最小的节点来替代该节点)。当然,除了上面这种由实现引起的情况;还有就是当我们项二叉树添加一连串的排好序的数据,也会造成树的深度问题。

平衡二叉树(AVL): AVL 树是带有平衡条件的二叉树。一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树(空树的高度定义为-1)。

伸展树:它保证从空树开始连续M次对树的操作最多花费O(MlogN)时间。虽然这种保证并不排除任意单次操作花费O(N)时间的可能,而且这样的界也不如每次操作最坏情形的界为O(logN)那么强,但是时间效果却是医院的:不存在坏的输入序列。

红黑树:一种比较流行的AVL树的变种树。对红黑树的操作在最坏的情形下花费O(logN)时间,而且我们将看到,(对于插入操作的)一种审慎的非递归实现可以相对容易的完成(与AVL树相比)

红黑树是具有下列着色性质的二叉查找树:

1、每一个节点或者着成红色,或者着成黑色。

2、根式黑色的。

3、如果一个节点是红色的,那么它的子节点必须是黑色的。

4、从一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点。

着色法则的一个结论是,红黑树的高度最多是2log(N+1)。红黑树的优点是执行插入所需要的开销相对较低,另外就是实践中发生的旋转相对较少。

B(B-)树:是一种多路搜索树。1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树(或B-树、B_树)。

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的树:

一、根结点至少有两个子女;

二、每一个非根节点所包含的关键字个数 j 满足:m/2 - 1 <= j <= m - 1;(向上取整)

三、除根结点之外的全部结点(不包括叶子结点)的个数正好是关键字总数加1,故内部子树个数 k 满足:m/2<= k <= m ;

四、全部的叶子结点都位于同一层。

B+树: B+树是应文件系统所需而出的一种B-树的变型树,这种树主要用在数据库索引中。一棵m阶的B+树和m阶的B-树的差别在于:

  • 有n棵子树的结点中含有n个关键字,每一个关键字不保存数据,只用来索引,全部数据都保存在叶子节点。
  • 全部的叶子结点中包含了所有关键字的信息,及指向含这些关键字记录的指针,且叶子结点自己依关键字的大小自小而大顺序连接。
  • 全部的非终端结点能够当作是索引部分,结点中仅含其子树(根结点)中的最大(或最小)关键字。一般在B+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点。

B*树:是B+树的变体,在B+树的非根和非叶子结点再增长指向兄弟的指针;B树定义了非叶子结点关键字个数至少为(2/3)M,即块的最低使用率为2/3.

跳跃表(Skip List):增加了向前指针的链表叫做指针。跳表全称叫做跳跃表,简称跳表。跳表是一个随机化的数据结构,实质是一种可以进行二分查找的有序链表。跳表在原有的有序链表上增加了多级索引,通过索引来实现快速查询。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。

应用场景:节点增加和更新比较少,查询频次较多的情况。

使用跳跃表的产品:

1、Lucene, elasticSearch

2、Redis:

Redis sorted set的内部使用HashMap和跳跃表(SkipList)来保证数据的存储和有序,HashMap里放的是成员到score的映射,而跳跃表里存放的 是所有的成员,排序依据是HashMap里存的score,使用跳跃表的结构可以获得比较高的查找效率,并且在实现上比较简单。

源码解析

这个map通常充当一个binned (bucketed)哈希表,但是当容器变得太大时,它们将被转换为TreeNodes的容器,每个容器的结构与java.util.TreeMap中的容器类似。 大多数方法尝试使用普通bins,但在适用的情况下传递到TreeNode方法(简单地通过检查节点的实例)。 TreeNodes的Bins可以像其他Bins一样遍历和使用,但在填充过多时还支持更快的查找。 然而,由于在正常使用中绝大多数的容器都没有被过度填充,所以在表方法过程中检查树容器是否存在可能会被延迟。

树容器(即,其元素都是TreeNodes的容器)主要由hashCode排序,但在纽带的情况下,如果两个元素是相同的“class C implements Comparable<C>”,类型则使用它们的compareTo方法进行排序。 (我们通过反射保守地检查泛型类型来验证这一点——参见方法comparableClassFor)。 当键具有不同的哈希值或可排序时,树容器增加的复杂性对于提供最坏情况下的O(log n)操作是值得的。因此,在偶然或恶意的用法下,性能会优雅地下降,其中hashCode()方法返回的值分布很差,以及许多键共享一个hashCode,只要它们也是Comparable。 (如果两者都不适用,与不采取预防措施相比,我们可能会浪费大约两倍的时间和空间。 但是,唯一已知的案例来自于糟糕的用户编程实践,它们已经如此缓慢,以至于没有什么区别。)

因为TreeNodes的大小大约是常规节点的两倍,所以我们只在容器包含足够的节点时才使用它们(参见TREEIFY_THRESHOLD)。 当它们变得太小时(由于移除或调整大小),它们会被转换回普通bins。 在使用良好分布的用户hashCodes时,很少使用树容器。

树的根通常是它的第一个节点。 然而,有时(目前仅在Iterator.remove上),根可能在其他地方,但可以在父链接之后恢复(方法TreeNode.root())。

当bin列表被树形化、拆分或未拆分时,我们将它们保持在相同的相对访问/遍历顺序(即字段Node.next),以更好地保留局部性,并略微简化调用iterator.remove的拆分和遍历的处理。 当在插入中使用比较器时,为了在重新平衡中保持总排序(或尽可能接近),我们比较类和identityHashCodes作为tie-breakers。

由于子类LinkedHashMap的存在,普通模式和树模式之间的使用和转换变得复杂。 请参阅下面定义的在插入、删除和访问时调用的钩子方法,这些方法允许LinkedHashMap内部保持独立于这些机制。 (这还需要将一个map实例传递给可能创建新节点的一些实用程序方法。)

(1)、类定义

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

与JDK1.7定义一样,HashMap 继承了 AbstractMap,实现 Map、Cloneable、Serializable 接口。

(2)、HashMap 变量

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

    /**
     * 最大容量,如果一个较大的值由带参数的构造函数中的任何一个隐式指定,则使用该值。 必须是2的幂<= 1<<30。
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 在构造函数中没有指定时使用的负载因子。
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 使用树而不是列表的桶计数阈值。 当将元素添加到至少有这么多节点的bin中时,bin将被转换为树。 该值必须大于2且至少为8,
     * 以便与树移除中关于收缩时转换回普通bins的假设相匹配
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 在调整大小操作期间取消(拆分)bin树化的bin计数阈值。 应该小于TREEIFY_THRESHOLD,并且在去除收缩检测时最多6个网格。
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 可将容器树形化的最小表容量。 (否则,如果一个bin中有太多的节点,表将被调整大小。) 应至少为4 * TREEIFY_THRESHOLD,
     * 以避免调整大小和树化阈值之间的冲突。
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * 表,在第一次使用时初始化,并根据需要调整大小。 在分配时,长度总是2的幂。 (我们也允许在某些操作中长度为零,以允许当前不需要的引导机制。)
     */
    transient Node<K,V>[] table;

    /**
     * 保存缓存entrySet()。 注意,AbstractMap字段用于keySet()和values()。
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * 此映射中包含的键值映射的数量。
     */
    transient int size;

    /**
     * 结构化修改指的是改变HashMap中映射的数量或修改其内部结构(如rehash)。 该字段用于使HashMap的集合视图上的迭代器快速失败。
     * (见ConcurrentModificationException)。
     */
    transient int modCount;

    /**
     * 要调整大小的下一个大小值(容量*负载因子)。
     */
    int threshold;

    /**
     * 哈希表的负载因子。
     */
    final float loadFactor;

(3)、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);
    }

    /**
     * 构造一个空的HashMap,使用指定的初始容量和默认的负载因子(0.75)。
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 构造一个空的HashMap,使用默认的初始容量(16)和默认的负载因子(0.75)。
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    /**
     * 构造一个新的HashMap,具有与指定的Map相同的映射。
     * 创建HashMap时使用默认负载因子(0.75)和足够容纳指定Map中的映射的初始容量。
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    /**
     * 实现 Map.putAll and Map constructor
     *
     * @param m the map
     * @param evict 在最初构造此映射时为false,否则为true(转发给afternodeinsert方法)。
     */
    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);
            }
        }
    }

(4)、静态内部类 Node

    /**
     * 基本哈希bin节点,用于大多数条目。 (参见下面的TreeNode子类,以及它的Entry子类的LinkedHashMap。)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//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;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

(5)、静态内部类 TreeNode

红黑树

    /**
     * 树容器的条目。 LinkedHashMap延伸。 条目(它扩展了Node),因此可以用作常规或链接节点的扩展。
     */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<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);
        }
        .....
     }

    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

(6)、 put(K key, V value)

    /**
     * 将指定值与此映射中的指定键关联。 如果映射之前包含键的映射,则替换旧值。
     * @return 前一个与键关联的值,或null(如果键没有映射的话)。 (一个null返回也可以表示先前关联null与键的映射。)
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    /**
     * 实现 Map.put 和相关 方法
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //tab赋值,如果当前tab为null,则resize()初始化tab; n赋值为tab.length
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //如果根据hash定位到的hash表槽位为空,则直接新建一个节点并赋值给此槽位
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //当前槽位非空,并且key匹配的话,则表示当前已存在该key的映射
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //当前槽位的节点类型为TreeNode,则将键值对存入红黑树
            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);
                        //如果达到链表转换红黑树的长度阈值8,则根据情况进行表扩容或者将当前链表转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果链表中已存在该key的映射,跳出循环进行下面的value替换逻辑
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //已存在该key的映射,则直接替换value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
       //如果size达到达到扩容阈值,则进行扩容操作
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    /**
     * 替换桶中所有的链接节点在给定的哈希索引,除非表太小,在这种情况下,调整大小代替。
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //hash表长度小于64的时候,直接使用扩容
        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;
            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);
        }
    }

由上面的源码,可以得到如下put逻辑:

  • 1、首先,根据hash定位哈希表的槽位(桶);
  • 2、如果当前桶为空,则直接新建节点插入,最后判断是否哈希表是达阈值需要进行扩容
  • 3、当前槽位非空,并且槽位第一个Node节点key匹配上的话,则表示当前已存在该key的映射,进行value替换即可
  • 4、当前槽位的第一个节点类型为TreeNode,则将键值对存入红黑树
  • 5、否则,遍历该槽位的链表,如果存在该key,则替换value
  • 6、继续第五步,如果链表不存在该key,则插入链表末端,最后判断如果链表长度达到链表转换阈值; 如果hash表长度小于64,则扩容;否则,将链表转为红黑树;最后判断是否哈希表是达阈值需要进行扩容

JDK1.8,HashMap扩容条件:

  • 当hash表长度小于64时,如果键值对size达到阈值,则扩容;如果链表达到转树阈值8,则扩容
  • 当hash表长度大于64是,如果键值对size达到阈值,则扩容;

(7)、get(Object key)

    /**
     * 返回指定键映射到的值,如果这个映射不包含该键的映射,则返回{@code null}。
     */
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    /**
     * 实现 Map.get and 相关方法
     */
    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) {
            // always check first node
            if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                //第一个节点为TreeNode,则使用树查找并返回结果
                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;
    }

(9)、remove(Object key)

    /**
     * 如果存在,则从该映射中移除指定键的映射。
     */
    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

    /**
     * 实现 Map.remove 和相关方法
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to match if matchValue, else ignored
     * @param matchValue if true only remove if value is equal
     * @param movable if false do not move other nodes while removing
     * @return the node, or null if none
     */
    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) {
            Node<K,V> node = null, e; K k; V v;
            //判断第一个节点是否为要删除的节点
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                //如果为TreeNode类型,则从树中查找节点
                if (p instanceof 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)))) {
                //如果为TreeNode类型,则调用树删除节点
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //删除链表节点
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

上面代码中,通过removeTreeNode方法删除节点时,会判断如果树的size大小<=阈值6,则红黑树重新转为链表

最后总结:HashMap1.8的整个主要方法逻辑还是比较清晰的,JDK1.7相比,它的底层数据结构,增加了红黑树相关的逻辑;由于红黑树的查找性能O(logN),比链表快很多;所以,当hash冲突较多的情况下,1.8的性能会有显著提高。另外,由于红黑树相关添加,以及删除等逻辑比较复杂,其中涉及到各种旋转以及着色的改变等操作,所以本篇博文未对这块进行深入分析;在后续的数据结构专题中,博主将继续将红黑树具体的实现内容为大家详细分析!

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部