查看完整视频
评论可见

您需要在视频最下面评论,方可查看完整视频

积分观看

您支付积分,方可查看完整视频

{{user.role.value}}
付费视频

您支付费用,方可查看完整视频

¥{{user.role.value}}
专属视频

只允许以下等级用户查看该视频

升级
会员专享

HashMap源码深度剖析,大厂必考!

一线资深java工程师招聘需求里明确了需要精通集合容器,尤其是今天我谈到的HashMap以及后续我要讲到的ConcurrentHashMap。

HashMap在Java集合的重要性不亚于Volatile在并发编程的重要性(可见性与有序性),所以需要重点来掌握。

本节课内容会比较多,我会把HashMap最为核心的点都讲到。

备注:学习技术要学会从骨干源码抓起,首先需要建立一个骨干源码大框架,然后才去抓各个分支的细节,千万不要一来就进入细节,切记!

好了现在开始进入的正题,抓重点,我讲到的以10个核心点都掌握了,基本上可以征服面试官了,本节课会讲1个小时左右。

HashMap的数据结构
1.核心成员
2.Node数组
HashMap的数据存储
1.哈希表来存储
2.哈希函数
3.哈希冲突:链式哈希表
HashMap的get方法:哈希函数
为什么槽位数必须使用2^n?
1.为了让哈希后的结果更加均匀
2.等价于length取模
分析HashMap的put方法
HashMap总结

HashMap的数据结构

首先我们从数据结构的角度来看:HashMap是:数组+链表+红黑树(JDK1.8增加了红黑树部分)的数据结构,如下所示:

这里需要搞明白两个问题:

  • 数据底层具体存储的是什么?
  • 这样的存储方式有什么优点呢?

1.核心成员

默认初始容量(数组默认大小):16,2的整数次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
装载因子用来衡量HashMap满的程度,表示当map集合中存储的数据达到当前数组大小的75%则需要进行扩容
 
链表转红黑树边界
static final int TREEIFY_THRESHOLD = 8;

红黑树转离链表边界
static final int UNTREEIFY_THRESHOLD = 6;

哈希桶数组
transient Node<K,V>[] table;

实际存储的元素个数
transient int size;

当map里面的数据大于这个threshold就会进行扩容
int threshold   阈值 = table.length * loadFactor

 

2.Node数组

从源码可知,HashMap类中有一个非常重要的字段,就是 Node[] table,即哈希桶数组,明显它是一个Node的数组。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;//用来定位数组索引位置
    final K key;
    V value;
    Node<K,V> next;//链表的下一个Node节点

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

Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)。

HashMap的数据存储

隐藏内容,您需要满足以下条件方可查看
End

课后作业

留一道大厂的面试题给你,这是去阿里几乎必问题目。

隐藏内容,您需要满足以下条件方可查看
End

请把你的答案写到问答区域输出是最好的学习:每一次输出都会让你离目标更进一步。

集合框架

史上最强ConcurrentHashMap核心源码解析

2020-7-23 19:21:48

集合框架

ArrayList、Vector、LinkedList等区别详解

2020-7-21 18:06:00

2 条回复 A文章作者 M管理员
  1. 1、HashMap是用数据+链表+红黑树(JDK1.8版本之后增加)的数据结构来实现的,
    通过哈希函数确定在桶(数组)中的位置,当发生哈希冲突的时候,往后挂链表(JDK1.8版本会有链表转红黑树的逻辑)
    2、(1)底层数据结构不一样,1.7是数组+链表,1.8是数组+链表+红黑树
    (2)计算哈希值时,jdk1.8版本相比jdk1.7版本多了对hasCode做无符号右移16位,与原hasCode做异或的操作
    (3)扩容策略不一样
    3、哈希函数的目的是尽量让计算出的哈希值分布均匀,减少哈希碰撞
    JDK1.8版本的优化是,将hascode的高16位做移位操作,可以让hascode高位的值也参与运算,掺杂的元素多了,生成的hash的值的随机性会增大,减少了hash碰撞

    • 核心点都谈到了 ,基本都掌握了,再补充一个点:就是HashMap 1.7版本在多线程的情况下会出现死循环,形成一个链表的死循环这个点,还可以线下有时间再做了解和补充,基本就没问题了。

      基本学习快一个月了,依然还在坚持输出作业,这个必须给赞 ,线下就坚持锻炼(keep见)+坚持作业输出,我就搬个小板凳在旁边给你呐喊加油了 ,继续加油 ✗咧嘴笑✗ ✗拳头✗

个人中心
今日签到
搜索