当前位置:首页 » 《休闲阅读》 » 正文

Java--敲重点!JDK1.8 HashMap特性及底层数组+单链表+红黑树知识(建议收藏)_JustinQin

23 人参与  2022年02月15日 15:07  分类 : 《休闲阅读》  评论

点击全文阅读


❤️‍大家好,我是贾斯汀!❤️‍

在这里插入图片描述


学习目录

  • 学习背景
  • HashMap特性
  • HashMap添加元素四步曲
    • 前奏:HashMap如何添加一个元素?
    • 第一步曲:根据key得到hashCode值
    • 第二步曲:根据hashCode值计算出hash值
    • 第三步曲:根据hash值计算出哈希表数组index下标
    • 第四步曲:将元素节点保存到哈希表指定数组index下标
    • 终曲:为什么HashMap底层源码用这么多位运算?
  • HashMap链表转为红黑树
    • 红黑树结构
    • 红黑树五大特性
    • HashMap链表转为红黑树过程
  • HashMap扩容机制
  • HashMap获取元素
  • HashMap常用的API方法
  • HashMap底层源码关键属性

学习背景

由于整个HashMap底层源码实现很多,很难全部剖析,望见谅,本文主要挑选工作和面试经常遇到的一些重点和难点进行剖析即可,希望对你有所帮助!
在进入正文之前,我们知道JDK底层源码很多地方都用到了位运算以及进制相关的知识,HashMap底层也不例外,二进制是计算机底层存储格式,你电脑上所有东西,文件,视频,音乐,全部是二进制方式存储的,十进制就是我们平时的阿拉伯数字没啥可说,在学习本文时,建议先快速了解下Java几种位运算以及常见进制说明,特别是二进制的位运算,可以查看我的这篇文章进行快速了解下 https://blog.csdn.net/JustinQin/article/details/120505776

HashMap特性

在这里插入图片描述

  • 继承AbstractMap抽象类,实现Map接口以及Cloneable, java.io.Serializable克隆和序列化
  • 底层是由数组+链表组成的哈希表,JDK1.8链表长度超过8并且table数组大小大于64时才会将链表优化为红黑树
  • 增删改查的效率都比较高,但多线程环境下是不安全的,可能存在问题
  • 存储的元素是键值对,key键是唯一的,并且允许为key/value为null但不保证顺序
  • 通过key的hash值计算出需要存放在哈希表中的数组位置index
  • 默认初始化容量大小为0,第一次调用put真正给默认大小16,每次扩容oldCap << 1即原来容量的2倍
  • 常用的API方法put(key,value)/get(key)/size()/isEmpty()/containsKey(key)/remove(key)
  • 底层源码关键属性table、threshold、loadFactor、modCount、size

HashMap添加元素四步曲

前奏:HashMap如何添加一个元素?

HashMap底层数据结构主要通过put(K key, V value)方法添加元素,底层四步曲如下:

  • 第一步曲:根据key得到hashCode值
  • 第二步曲:根据hashCode值计算出hash值
  • 第三步曲:根据hash值计算出哈希表数组index下标
  • 第四步曲:将元素节点保存到哈希表指定数组index下标

HashMap添加元素的示例代码:

        HashMap<Object, Object> map = new HashMap<>();
        map.put("name","Justin");

HashMap底层put(key,value)方法源码:

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

再看下,hash方法实现源码:

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

接下来将解读HashMap底层源码添加元素四部曲具体实现

第一步曲:根据key得到hashCode值

以上面示例代码说明,这里key是字符串"name",String重写了计算字符串hashCode值的hashCode()方法,源码如下:
在这里插入图片描述
计算得到hashCode值为3373707

第二步曲:根据hashCode值计算出hash值

hash值计算的过程用到了^(异或)和>>>(无符号右移)两种位运算
(h = key.hashCode()) ^ (h >>> 16)(3373707) ^ (3373707 >>> 16)
这里为了方便展示,二进制每四位使用空格格式化,位运算过程如下:
在这里插入图片描述
计算key="name"的hash值二进制结果是1100110111101010111000转成十进制为3373752

进制在线转换:https://c.runoob.com/front-end/58/
在这里插入图片描述
即计算key="name"的hash值为3373752,也可以debug断点往后查看hash值刚好也是这个值

第三步曲:根据hash值计算出哈希表数组index下标

公式:i = (n - 1) & hash
在这里插入图片描述
这里公式(n - 1) & hash 用到了&按位与运算(都为1则得1),奥妙之处在于n表示HashMap中的数组容量大小,并且刚好是16,32,64…2的次方,这种情况其实是等效于 hash % n 取模计算出的数组index下标值,并且下标不会超过容量(n-1)即能够保证不会数组下标越界

但是HashMap这里没有使用%取模,而是使用位运算,直接对内存数据进行操作,效率最高,如果使用%取模需要先将内存数据转成十进制再进行运算,多了这部分的性能开销,效率会变低

HashTable底层倒是用的%取模,hash值与十六进制0x7FFFFFFF做按位与运算目的是为了保证hash值始终是正数
在这里插入图片描述
有的小伙伴可能会问了,使用%取模计算,那这里为啥HashTable还在用,我想说的是其实也可以优化,只不过HashTable本身就是主打synchronized线程安全,也就不考虑优化%取模为位运算了吧
在这里插入图片描述

第四步曲:将元素节点保存到哈希表指定数组index下标

    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)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            //该位置首次添加节点,则直接新建节点添加
            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;
            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
                            //则当前节点,需要通过该方法进行添加
                            //如果数组容量大于64,该过程会进行链表转化为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //HashMap对于key已经存在的处理情况是
            //除非该key对应的value为null,否则一律不做任何处理
            //Hashtable中则是会直接更新key对应的value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //集合修改次数,没操作一次+1
        ++modCount;
        //HashMap容量大小大于临界值,则进行resize()扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

终曲:为什么HashMap底层源码用这么多位运算?

关于位运算的使用,文中在介绍第三步曲时,也提到了HashMap计算数组下标使用%取模和位运算的问题,使用于位运算的奥妙之处在直接从内存读取数据进行计算,不需要转成十进制,如果使用%取模需要先转成十进制,有性能开销,效率比较低

HashMap底层除了文中提到的^按位异或、>>>无符号右移、&按位与位运算,其实在HashMap的扩容机制resize()中,还用到了<<左移运算
oldCap << 1
在这里插入图片描述
这里oldCap << 1刚好是两倍,可以总结的说一个数与n进行左移运算,结果为这个数乘以2的n次方
oldCap << 1 等值 oldCap = oldCap * (2的n次方)
同理,一个数与n进行右移运算结果为这个数除以2的n次方
oldCap >> 1 等值 oldCap = oldCap / (2的n次方)

**

HashMap链表转为红黑树

红黑树结构

在这里插入图片描述

红黑树五大特性

  • 节点有红色或黑色两种;
  • 根节点是黑色;
  • 叶子节点全部是黑色(如图方框是叶子节点);
  • 红色节点必须配两个黑色节点(即保证任意路不会出现两个连续红色节点);
  • 从任意节点到该节点下所有叶子节点包含的黑色节点个数相同(也简称黑高)。

HashMap链表转为红黑树过程

代码示例:

public class Test {
    public static void main(String[] args) {
        HashMap<Object, Object> map = new HashMap<Object, Object>();
        //下标为0
        map.put(null, "Justin");
        map.put(16, "Justin");

        //下标为8
        map.put(8, "Justin");      //链表第1个节点
        map.put(24, "Justin");     //链表第2个节点
        map.put(40, "Justin");     //链表第3个节点
        map.put(56, "Justin");     //链表第4个节点
        map.put(72, "Justin");     //链表第5个节点
        map.put(88, "Justin");     //链表第6个节点
        map.put(104, "Justin");    //链表第7个节点
        map.put(120, "Justin");    //链表第8个节点
        map.put("name", "Justin"); //在添加第9个节点时,链表会被转换为红黑树
    }
}

上述代码添加元素完成后,大多数人认为,底层哈希表的数据结构如下:
在这里插入图片描述
看起来好像没啥毛病,但实际哈希表index=8的位置链表并不会转成红黑树,原因如下:
在这里插入图片描述
再来看下treeifyBin(tab,hash)为什么不将链表转成红黑树?
在这里插入图片描述
其中tab.length < MIN_TREEIFY_CAPACITY表示只要哈希表数组大小于64容量的,不可能会发生链表树化的过程,所以示例代码中,在哈希表数组下标index=8位置,添加第9个key="name"元素时,此时哈希表大小只有16, tab.length < MIN_TREEIFY_CAPACITY即16 < 64 接进行resize()扩容并重新计算各个元素存储的位置了,并不会走后面的链表转红黑树的过程。

在这里插入图片描述

当添加key="name"节点时,会进行扩容,容量大小由16变为32,此时oldMap数据迁移到newMap后数据排列如何呢?
这里比较简单,没涉及到红黑树的拆分,而且链表长度都是大于1个的,直接由(hash & oldCap)重新计算位置:

public class Test {
    public static void main(String[] args) {
        cal(null,0);
        cal(16,0);

        cal(8,8);
        cal(24,8);
        cal(40,8);
        cal(56,8);
        cal(88,8);
        cal(72,8);
        cal(104,8);
        cal(120,8);
        cal("name",8);
    }

    static void cal(Object key,int oldIndex) {
        //将oldMap容量和节点hash值进行&按位与运算
        if( (16 & hash(key)) ==  0){//结果为0,节点放到newMap位置与在oldMap下标index位置一样
            System.out.println("原key=" + key + ",迁移到newMap数组下标位置为:" + oldIndex);
        }else{//结果不为0,节点放到newMap位置刚好等于oldMap下标index位置 + oldMap数组容量大小
            System.out.println("原key=" + key + ",迁移到newMap数组下标位置为:" + (oldIndex + 16));
        }
    }

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

原来所有key,迁移到newMap后数组index下标位置如下:

原key=null,迁移到newMap数组下标位置为:0
原key=16,迁移到newMap数组下标位置为:16
原key=8,迁移到newMap数组下标位置为:8
原key=24,迁移到newMap数组下标位置为:24
原key=40,迁移到newMap数组下标位置为:8
原key=56,迁移到newMap数组下标位置为:24
原key=88,迁移到newMap数组下标位置为:24
原key=72,迁移到newMap数组下标位置为:8
原key=104,迁移到newMap数组下标位置为:8
原key=120,迁移到newMap数组下标位置为:24
原key=name,迁移到newMap数组下标位置为:24

所以示例代码,添加元素后,正确的数据结构应该是这样的:
在这里插入图片描述

通过debug断点,也可以看到扩容后节点主要被分配到了8、16、24这个三个数组下标位置:
在这里插入图片描述

不过一般情况下,HashMap扩容是发生在添加元素时,最后通过++size > threshold判断容量大于临界值时,才进行resize()扩容

HashMap扩容机制

  • 扩容情况1:第一次添加元素会进行扩容,默认初始化容量为16
  • 扩容情况2:哈希表容量小于64时,链表长度每次大于8,都会进行resize()扩容
  • 扩容情况3:HashMap容量大于临界值时

几种扩容情况的源码如下:

    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:第一次添加元素会进行扩容,默认初始化容量为16
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            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;
            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);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //扩容情况2:见treeifyBin方法说明
                            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);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize(); //扩容情况3:HashMap容量大于临界值时
        afterNodeInsertion(evict);
        return null;
    }

treeifyBin源码如下:

    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //扩容情况2:哈希表容量小于64时,链表长度每次大于8,都会进行resize()扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize(); 
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            //链表树化的过程...
        }
    }

再来看HashMap的resize()扩容关键源码:

    final Node<K,V>[] resize() {
        ...
        if (oldCap > 0) {
            ...
            //oldCap << 1即2倍扩容
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        ...
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            //遍历oldMap按一定规则,迁移数据到newMap
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        //对于哈希表数组后链表只有一个节点的
                        //需要根据hash值重新计算新的下标位置
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        //对红黑树进行拆分
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        //对于哈希表数组后链表有多个节点的
                        //通过(hash & oldMap)算法以及lo、hi节点进行分组巧妙迁移
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //这里是&按位与运算是oldMap迁移数据到newMap的奥妙之处
                            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;
                            //按位与结果为0的,节点迁移到newMap下标与oldMap中下标一样
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            //按位与结果不为0的,节点迁移到newMap下标
                            //则刚好等于原oldMap中下标 + oldCap老容量
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

可以看到其实HashMap扩容机制很简单,核心就是newCap = oldCap << 12倍扩容机制,难点在于oldMap旧数据迁移到newMap的过程,会涉及红黑树的拆分以及哈希表数组后链表有多个节点用的位运算(hash & oldMap)以及lohi两种节点,这个有点理解,特别是刚读源码的小伙伴,读不懂可以先放放,以后在慢慢深入理解。

HashMap获取元素

map.get("name");
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

这里hash值的获取跟添加元素一模一样:

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

主要看下获取节点元素getNode实现源码:

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //这里是确定元素在哈希表哪个数组下标,跟添加元素中原理一样
        //也是通过位运算(n-1) & hash能确定元素所在数组index下标
        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))))
                //每次都进行key判断和equals比较,都一样说明是要找的元素直接返回
                return first;
            if ((e = first.next) != null) {//继续取链表下一节点
                //如果节点是红黑树,则调用红黑树查找方法能快速找到节点元素返回
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //只是普通节点,则对链表进行遍历,逐一比对节点的key,找到就返回
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

HashMap常用的API方法

API说明
put(key,value)添加元素(键值对key/value),并且key/value可为null,存在key时,除了value为null会替换value为新值,其他value不会替换新值,HashTable不允许value为null,否则直接NullPointException空指针异常,并且直接替换value为新值
get(key)根据键key获取元素(键值对key/value)
size()获取HashMap容量大小,平时需注意未初始化HashMap对象时直接调用该方法会导致NullPointException空指针
isEmpty()判断HashMap的size容量大小是否为0,同样平时需注意未初始化HashMap对象时直接调用该方法会导致NullPointException空指针
containsKey(key)根据key判断HashMap中是否存在该key的键值对
remove(key)根据key删除HashMap中的该键值对

HashMap底层源码关键属性

属性说明
tableHashMap底层数据结构哈希表节点数组Node<K,V>[] table;
sizeHashMap容量大小,注意不是哈希表数组的长度table.length
loadFactor装载因子,默认是一个浮点数0.75f,这是一个综合计算比较优秀的值,可根据时间复杂度和空间负责度需要进行调整
threshold临界值,由HashMap容量大小 * loadFactor计算出,添加元素是当HashMap容量大小超过这个值就进行resize() 2倍扩容
modCount集合修改次数添加、删除操作都会++modCount

本文对HashMap特性及底层数据结构暂时分析到这里,希望对你有所帮助!

如果你是一名Java初学者,建议先去学习本文提到的HashMap特性以及常用API如何使用,然后查看源码了解几个关键属性有什么用,再深入剖析增、删、查方法底层实现的原理,其他Java基础类库也是一样,你会发现其中用到了很多数据结构与算法、位运算等奥妙之处。


❤️‍原创不易,觉得有用的小伙伴(点赞+收藏)支持一下哇!❤️‍

在这里插入图片描述


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/34807.html

节点  下标  数组  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1