Java集合类:HashMap (基于JDK1.8)

时间:2022-08-06 17:54:13

转载出处 https://blog.csdn.net/yeyazhishang/article/details/83114658

 

前言

今天我们来学习Java中较为常用的集合类 HashMap。
另外说明一下,本文的 HashMap 源码是基于Jdk1.8版本的,如果没有特别说明的话,之后的集合类源码解析都是1.8的版本。

HashMap的数据结构

打开HashMap源码文件,可以看到它是继承自 AbstractMap,并实现了Java集合的根接口Map,以及Cloneable和Serializable接口,所以HashMap可以被序列化。
Java集合类:HashMap (基于JDK1.8)
HashMap的底层结构是哈希表的具体实现,通过相应的哈希运算就可以很快查询到目标元素在表中的位置,拥有很快的查询速度,因此,HashMap被广泛应用于日常的开发中。理想的情况就是一个元素对应一个Hash值,这样的查询效果是最优的。

但实际这是不可能的,因为哈希表存在“hash (哈希) 冲突“ 的问题。当发生hash冲突时,HashMap采用 “拉链法“ 进行解决,也就是数组加链表的结构。在HashMap的代码注释中,数组中的元素用 “bucket” (中文读作 桶) 来称呼,而哈希函数的作用就是将key寻址到buckets中的一个位置,如果一个 bucket 有多个元素,那么就以链表的形式存储(jdk1.8之前单纯是这样)。

这是HashMap的存储结构图:
Java集合类:HashMap (基于JDK1.8)

关于 “拉链法” 和 “hash冲突” 的知识点有疑问的读者可以看下我之前的文章 数据结构:哈希表以及哈希冲突的解决方案 。
为了方便,下文的 “bucket“ 都用 “桶“ 替代。

深入源码

两个参数

在具体学习源码之前,我们需要先了解两个HashMap中的两个重要参数,“初识容量” 和 “加载因子”,

初识容量是指数组的数量。加载因子则决定了 HashMap 中的元素在达到多少比例后可以扩容 (rehash),当HashMap的元素数量超过了加载因子与当前容量的乘积后,就需要对哈希表做扩容操作。

在HashMap中,加载因子默认是0.75,这是结合时间、空间成本均衡考虑后的折中方案,因为 加载因子太大的话发生冲突的可能性会变大,查找的效率反而低;太小的话频繁rehash,降低性能。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。

成员变量

好了,前面说了那么多,现在开始深入源码学习吧,先了解一下HashMap的主要的成员变量:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75F;
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
transient HashMap.Node<K, V>[] table;
transient Set<Entry<K, V>> entrySet;
transient int size;
int threshold;
final float loadFactor;

可以看出,HashMap主要的成员变量比较多,有些变量还初始化了值,下面一个个来做解释。

DEFAULT_INITIAL_CAPACITY:默认初识容量 1 << 4 ,也就是16,必须是2的整数次方。

DEFAULT_LOAD_FACTOR:默认加载因子,大小为0.75。

MAXIMUM_CAPACITY:最大容量, 2^ 30 次方。

TREEIFY_THRESHOLD :树形阈值,大于这个数就要树形化,也就是转成红黑树。

MIN_TREEIFY_CAPACITY:树形最小容量。

table:哈希表的链接数组,对应桶的下标。

entrySet:键值对集合。

size:键值对的数量,也就是HashMap的大小。

threshold:阈值,下次需要扩容时的值,等于 容量*加载因子。

loadFactor:加载因子。

介绍完变量,下面介绍HashMap的构造方法。

四个构造方法

HashMap共有四个构造方法,代码如下:

//加载默认大小的加载因子
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}
//加载默认大小的加载因子,并创建一个内容为参数 m 的内容的哈希表
public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        //添加整个集合
        putMapEntries(m, false);
}
//指定容量和加载因子
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);
}

不难发现,上面第三个构造函数可以自定义加载因子和容量,首先判断传入的加载因子是否符合要求,然后根据制定的容量执行 tableSizeFor() 方法,它会根据容量来指定阈值,为何要多这一步呢?

因为buckets数组的大小约束对于整个HashMap都至关重要,为了防止传入一个不是2次幂的整数,必须要有所防范。tableSizeFor()函数会尝试修正一个整数,并转换为离该整数最近的2次幂。

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

 

比如传入一个整数244,经过位移,或运算后会返回最近的2次幂 256
Java集合类:HashMap (基于JDK1.8)

插入数据的方法:put()

在集合中最常用的操作是存储数据,也就是插入元素的过程,在HashMap中,插入数据用的是 put() 方法。

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

put方法没有做多余的操作,只是传入 key 和 value 还有 hash 值 进入到 putVal方法中并返回对应的值,点击进入方法,一步步跟进源码:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //哈希表如果为空,就做扩容操作 resize()
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //要插入位置没有元素,直接新建一个包含key的节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //如果要插入的桶已经有元素,替换
    else {
        Node<K,V> e; K k;
        //key要插入的位置发生碰撞,让e指向p
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //没碰撞,但是p是属于红黑树的节点,执行putTreeVal()方法
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //p是链表节点,遍历链表,查找并替换
        else {
            //遍历数组,如果链表长度达到8,转换成红黑树
            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;
                }
                // 找到目标节点,退出循环,e指向p
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 节点已存在,替换value,并返回旧value
        if (e != null) { // existing mapping for key
            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() 方法计算哈希值
  • 然后调用 putVal() 方法中根据哈希值进行相关操作
  • 如果当前 哈希表内容为空,做扩容
  • 如果要插入的桶中没有元素,新建个节点并放进去
  • 否则从要插入的桶中第一个元素开始查找(这里为什么是第一个元素,下面会讲到)
    1. 如果没有碰撞,赋值给e,结束查找
    2. 有碰撞,而且当前采用的还是 红黑树的节点,调用 putTreeVal() 进行插入
    3. 链表节点的话从传统的链表数组中查找、找到赋值给e,结束
    4. 如果链表长度达到8,转换成红黑树
  • 最后检查是否需要扩容

put方法的代码中有几个关键的方法,分别是:

  1. hash():哈希函数,计算key对应的位置
  2. resize():扩容
  3. putTreeVal():插入红黑树的节点
  4. treeifyBin():树形化容器

前面两个是HashMap的桶链表操作的核心方法,后面的方法是Jdk1.8之后有关红黑树的操作,后面会讲到,先来看前两个方法。

哈希函数:hash()

hash() 方法是HashMap 中的核心函数,在存储数据时,将key传入中进行运算,得出key的哈希值,通过这个哈希值运算才能获取key应该放置在 “桶” 的哪个位置,下面是方法的源码:

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

从源码中可以看出,传入key之后,hash() 会获取key的hashCode进行无符号右移 16 位,然后进行按位异或,并把运算后的值返回,这个值就是key的哈希值。这样运算是为了减少碰撞冲突,因为大部分元素的hashCode在低位是相同的,不做处理的话很容易造成冲突。

之后还需要把 hash() 的返回值与table.length - 1做与运算,得到的结果即是数组的下标(为什么这么算,下面会说),在上面的 putVal() 方法中就可以看到有这样的代码操作,举个例子图:
Java集合类:HashMap (基于JDK1.8)
table.length - 1就像是一个低位掩码(这个设计也优化了扩容操作的性能),它和hash()做与操作时必然会将高位屏蔽(因为一个HashMap不可能有特别大的buckets数组,至少在不断自动扩容之前是不可能的,所以table.length - 1的大部分高位都为0),只保留低位,这样一来就总是只有最低的几位是有效的,就算你的hashCode()实现得再好也难以避免发生碰撞。这时,hash()函数的价值就体现出来了,它对hash code的低位添加了随机性并且混合了高位的部分特征,显著减少了碰撞冲突的发生。
另外,在putVal方法的源码中,我们可以看到有这样一段代码

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

上面的注释也说明了,这是检测要插入位置是否有元素,没有的话直接新建一个包含key的节点,那么这里为什么要用 i = (n - 1) & hash 作为索引运算呢?

下面这段解释摘自http://www.importnew.com/29724.html

这其实是一种优化手段,由于数组的大小永远是一个2次幂,在扩容之后,一个元素的新索引要么是在原位置,要么就是在原位置加上扩容前的容量。这个方法的巧妙之处全在于&运算,之前提到过&运算只会关注n
– 1(n =
数组长度)的有效位,当扩容之后,n的有效位相比之前会多增加一位(n会变成之前的二倍,所以确保数组长度永远是2次幂很重要),然后只需要判断hash在新增的有效位的位置是0还是1就可以算出新的索引位置,如果是0,那么索引没有发生变化,如果是1,索引就为原索引加上扩容前的容量。

效果图如下:

Java集合类:HashMap (基于JDK1.8)
这样在每次扩容时都不用重新计算hash,省去了不少时间,而且新增有效位是0还是1是带有随机性的,之前两个碰撞的Entry又有可能在扩容时再次均匀地散布开,真可谓是非常精妙的设计。

动态扩容:resize()

在HashMap中,初始化数组或者添加元素个数超过阈值时都会触发 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;
    //‘桶’数组的大小超过0,做扩容
    if (oldCap > 0) {
        //超过最大值不会扩容,把阈值设置为int的最大数
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //向左移动1位扩大为原来2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //旧数组大小为0,旧阈值>0,说明之前创建了哈希表但没有添加元素,初始化容量等于阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //旧容量、旧阈值都是0,说明还没创建哈希表,容量为默认容量,阈值为 容量*加载因子
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //新阈值还没有值,重新根据新的容量newCap计算大小
    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) {
        //遍历旧数组的每一个‘桶’,移动到新数组newTab
        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;
                        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;
}

上面的源码有点长,但总体逻辑就三步:

  1. 计算新桶数组的容量大小 newCap 和新阈值 newThr
  2. 根据计算出的 newCap 创建新的桶数组,并初始化桶的数组table
  3. 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型,则需要拆分红黑树 (调用**split()**方法 )。如果是普通节点,则节点按原顺序进行分组。

前面两步的逻辑比较简单,这里不多叙述。重点是第三点,涉及到了红黑树的拆分,这是因为扩容后,桶数组变多了,原有的数组上元素较多的红黑树就需要重新拆分,映射成链表,防止单个桶的元素过多。

红黑树的拆分是调用TreeNode.split() 来实现的,这里不单独讲。放到后面的红黑树一起分析。

节点树化、红黑树的拆分

红黑树的引进是HashMap 在 Jdk1.8之后最大的变化,在1.8以前,HashMap的数据结构就是数组加链表,某个桶的链表有可能因为数据过多而导致链表过长,遍历的效率低下,1.8之后,HashMap对链表的长度做了处理,当链表长度超过8时,自动转换为红黑树,有效的提升了HashMap的性能。

但红黑树的引进也使得代码的复杂度提高了不少,添加了有关红黑树的操作方法。本文只针对这些方法来做解析,不针对红黑树本身做展开,想了解红黑树的读者可以看我之前的文章

数据结构:红黑树的结构以及方法剖析 (上) 以及 数据结构:红黑树的结构以及方法剖析 (下)

节点树化

HashMap中的树节点的代码用 TreeNode 表示:

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

可以看到就是个红黑树节点,有父亲、左右孩子、前一个元素的节点,还有个颜色值。知道节点的结构后,我们来看有关红黑树的一些操作方法。

先来分析下树化的代码:

//将普通的链表转化为树形节点链表
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 桶数组容量小于 MIN_TREEIFY_CAPACITY,优先进行扩容而不是树化
    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
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            // 树形节点不为空,转换为红黑树
            hd.treeify(tab);
    }
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
}

上面的代码并不太复杂,大致逻辑是根据hash表的元素个数判断是需要扩容还是树形化,然后依次调用不同的代码执行。

值得注意的是,在判断容器是否需要树形化的标准是链表长度需要大于或等于 MIN_TREEIFY_CAPACITY,前面也说了,它是HashMap的成员变量,初始值是64,那么为什么要满足这个条件才会树化呢?

下面这段摘自https://segmentfault.com/a/1190000012926722#articleHeader6

当桶数组容量比较小时,键值对节点 hash
的碰撞率可能会比较高,进而导致链表长度较长。这个时候应该优先扩容,而不是立马树化。毕竟高碰撞率是因为桶数组容量较小引起的,这个是主因。容量小时,优先扩容可以避免一些列的不必要的树化过程。同时,桶容量较小时,扩容会比较频繁,扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下,将长链表转成红黑树是一件吃力不讨好的事。

所以,HashMap的树化过程也是尽量的考虑了容器性能,再看回上面的代码,链表树化之前是先把节点转为树形节点,然后再调用 treeify() 转换为红黑树,并且树形节点TreeNode 继承自 Node 类,所以 TreeNode 仍然包含 next 引用,原链表的节点顺序最终通过 next 引用被保存下来。

下面看下转换红黑树的过程:

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (root == null) {        //第一次进入循环,确定头节点,并且是黑色
            x.parent = null;
            x.red = false;
            root = x;
        }    
        else {        //后面进入循环走的逻辑,x 指向树中的某个节点
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            //从根节点开始,遍历所有节点跟当前节点 x 比较,调整位置,
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)    //当比较节点的哈希值比 x 大时, dir 为 -1
                    dir = -1;
                else if (ph < h)        //哈希值比 x 小时 dir 为 1
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    // 比较节点和x的key
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                //把 当前节点变成 x 的父亲
                //如果当前比较节点的哈希值比 x 大,x 就是左孩子,否则 x 是右孩子
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);
}

可以看到,代码的总体逻辑就是拿树中的节点与当前节点做比较,进而确定节点在树中的位置,具体实现的细节还是比较复杂的,这里不一一展开了。

红黑树拆分

介绍了节点的树化后,我们来学习下红黑树的拆分过程,HashMap扩容后,普通的节点需要重新映射,红黑树节点也不例外。

在将普通链表转成红黑树时,HashMap 通过两个额外的引用 next 和 prev 保留了原链表的节点顺序。这样再对红黑树进行重新映射时,完全可以按照映射链表的方式进行。这样就避免了将红黑树转成链表后再进行映射,无形中提高了效率。

下面看一下拆分的方法源码:

//map 容器本身
//tab 表示保存桶头结点的哈希表
//index 表示从哪个位置开始修剪
//bit 要修剪的位数(哈希值)
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    // 修剪后的两个链表,下面用lo树和hi树来替代
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        //如果当前节点哈希值的最后一位等于要修剪的 bit 值,用于区分位于哪个桶
        if ((e.hash & bit) == 0) {
            //把节点放到lo树的结尾
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        //把当前节点放到hi树
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
    
    if (loHead != null) {
        // 如果 loHead 不为空,且链表长度小于等于 6,则将红黑树转成链表
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            /* 
             * hiHead != null 时,表明扩容后,
             * 有些节点不在原位置上了,需要重新树化
             */
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    //与上面类似
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

源码的逻辑大概是这样:拆分后,将红黑树拆分成两条由 TreeNode 组成的链表(hi树和lo树)。如果链表长度小于 UNTREEIFY_THRESHOLD,则将链表转换成普通链表。否则根据条件重新将 TreeNode 链表树化。这里用两张图来展示一下拆分前后的变化

红黑树拆分前:
Java集合类:HashMap (基于JDK1.8)

拆分后:
Java集合类:HashMap (基于JDK1.8)

至此,有关红黑树的一些转换操作就介绍完毕了,除此之外,hashMap还提供了很多操作红黑树的方法,原理都差不多,读者们可以自己去研究。

总结

HashMap的源码解析就告一段落了,最后,总结一下HashMap的一些特性:

1、HashMap 允许 key, value 为 null;

2、HashMap源码里没有做同步操作,多个线程操作可能会出现线程安全的问题,建议用Collections.synchronizedMap 来包装,变成线程安全的Map,例如:

Map map = Collections.synchronizedMap(new HashMap<String,String>());

3、Jdk1.7以前,当HashMap中某个桶的结构为链表时,遍历的时间复杂度为O(n),1.8之后,桶中过多元素的话会转换成了红黑树,这时候的遍历时间复杂度就是O(logn)。

最后,感谢这几位大神的技术文章

https://blog.csdn.net/u011240877/article/details/53351188

https://segmentfault.com/a/1190000012926722

http://www.importnew.com/29724.html