[java进阶]——HashMap的底层实现原理和源码分析,另附几个高频面试题

简介: [java进阶]——HashMap的底层实现原理和源码分析,另附几个高频面试题

一、底层数据结构

JDK8以后底层使用 数组+链表+红黑树的数据结构,当链表长度大于8并且数组长度大于64,链表自动转为红黑树

node与treenode

hashmap中每一个元素都是一个node对象或treenode对象,node是链表节点,treenode是红黑树节点。

node属性有hash值、key、value、next,treenode无非就是多了记录父节点,左右节点,节点颜色,prev(前驱)节点-即比当前节点小的最大节点。在红黑树中,每个节点都有一个指向前驱节点的指针,用于快速查找前驱节点。

二、底层原理及源码分析

2.1 继承关系

继承了AbstractMap抽象类,实现了Map接口

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable{}
2.2 成员变量
  1. transient Node<K,V>[] table: 用于存储HashMap中的键值对的数组,每个元素是一个链表节点,该节点存储了一个键值对。
  2. transient Set<Map.Entry<K,V>> entrySet: 用于存储HashMap中的键值对的一个set集合,其中每个元素都是一个Map.Entry类型的对象,该对象包含了一个键值对。
  3. transient int size: 用于记录HashMap中键值对的数量。
  4. int threshold: 表示HashMap中键值对的数量达到该值(容量*加载因子)时,会触发扩容操作
  5. final float loadFactor: 表示HashMap的加载因子,用于计算threshold。
  6. transient int modCount: 用于记录HashMap中结构发生变化的次数,用于快速失败机制。
  7. static final int MAXIMUM_CAPACITY = 1<<30: 表示HashMap中数组的最大容量,即2的30次方。
  8. static final float DEFAULT_LOAD_FACTOR: 表示HashMap的默认加载因子,为0.75
  9. static final int DEFAULT_INITIAL_CAPACITY = 1<<4: 表示HashMap的默认容量,为16。
  10. static final int TREEIFY_THRESHOLD = 8: 链表长度,当同时满足10和11时,链表转红黑树。
  11. static final int MIN_TREEIFY_CAPACITY = 64: Hashmap容量(数组长度),当同时满足10和时,链表转红黑树。
  12. static final int UNTREEIFY_THRESHOLD = 6: 当红黑树节点数量小于该值时,树会转化为链表。
  13. transient Set<K> keySet: 用于存储HashMap中的键,它是一个Set集合。
  14. transient Collection<V> values: 用于存储HashMap中的值,它是一个Collection集合。
  15. private static final long serialVersionUID = 362498820763181265L :保证不同版本的HashMap在序列化和反序列化时的版本一致性。
2.3 构造方法

4种构造方法演示

public class Test {
    public static void main(String[] args) {
        HashMap<String, String> hm1 = new HashMap();
        hm1.put("张翠山", "殷素素");
        //指定默认容量
        HashMap<String, String> hm2 = new HashMap<>(16);
        //指定默认容量和加载因子
        HashMap<String, String> hm3 = new HashMap<>(16, 0.7f);
        HashMap<String, String> hm4 = new HashMap<>(hm1);
        System.out.println(hm4);
        System.out.println(hm1);
    }
}

注意:

空参构造只是把默认加载因子的值赋给了加载因子这个变量,并没有创建table[]数组,此时的table数组是默认初始值,为null。

2.4 重要的成员方法
    2.4.1 put()方法

调用putVal方法,方法参数讲解如下

返回值:返回被覆盖元素的值(value),如果没有覆盖,返回null

putval方法 原码讲解 重点来啦

首先明确一个问题:

hash是根据key值计算出来的,但是key值不同计算出来的hash值也可能相同,这叫hash碰撞,但是hash值不同key一定不同

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    //tab用于保存Hashmap中数组的地址
    //tab是在栈上开辟的,访存速度快,而外面的table是在堆上开辟的,访问慢
        Node<K,V>[] tab; 
    //要添加的节点p
    Node<K,V> p; 
    int n, i;
    //数组没有创建或者数组长度为0进if
        if ((tab = table) == null || (n = tab.length) == 0){
      //如果是第一次添加元素,调用resize()方法,底层会创建一个默认长度为16,加载因子为0.75的数组
      //将tab的长度赋给变量n
            n = (tab = resize()).length;
    }
      //不是第一次添加元素
      //1.计算要添加元素在数组中的索引,也就是i
      //2.判断:数组中索引处是否为null
        //如果为null 直接添加一个新的节点到tab中
        //如果不为null,走else,此时p是数组中索引处的节点,默念三遍!!!
        if ((p = tab[i = (n - 1) & hash]) == null)
      //是null添加新节点
            tab[i] = newNode(hash, key, value, null);
        else {
      //不是null
            Node<K,V> e; K k;
      //1.判断要添加的hash值与数组中索引处的节点(p)的hash值是否相同
        //相同并且key也相同 覆盖元素
        //不相同走elseif 或 else
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
        //覆盖原数组中的元素
                e = p;
            else if (p instanceof TreeNode)
        //与p的hash不同 可添加该节点
        //是红黑树结构就添加红黑树的节点
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
        //与p的hash不同,以p为迭代对象循环找该链表的尾节点
                for (int binCount = 0; ; ++binCount) {
          //判断p是否是尾节点
                    if ((e = p.next) == null) {
            //是尾节点,在p的后面添加新的链表节点
                        p.next = newNode(hash, key, value, null);
            //添加完后判断是否转为红黑树结构
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
          //迭代的过程中有与添加元素重复的key,break跳出,注意此时e是与添加元素重复key的节点
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
          //迭代p
                    p = e;
                }
            }
      //如果e是空 添加新元素
      //如果e不是空 覆盖元素
            if (e != null) { // existing mapping for key
        //记录老的value
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
          //覆盖
                    e.value = value;
                afterNodeAccess(e);
        //返回老的value
                return oldValue;
            }
        }
        ++modCount; //不用管
    //向数组中添加元素需要判断是否达到了扩容时机 达到就扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

再画个图便于你理解

三、高频面试题

问:

Hashmap的工作原理?

Hashmap中发生冲突怎么办?

Hashmap是如何扩容的

如果两个键的Hash值相同,你如何获取这两个Map.Entry对象

当发生冲突并且两节点的key相同时,是如何覆盖元素的

答:

     1. HashMap是一种基于哈希表实现的Map接口的键值对存储结构。工作原理可以简单概括为以下几个步骤:根据key值计算hashcode值,将键值对存储到表中,查找键值对。

     2. hash值相同叫做发生冲突,发生冲突之后依次比较待添加节点与链表或红黑树中的每一个节点的key值,如果key值相同,覆盖,返回要覆盖的元素的value。如果不相同并且到了尾节点,添加新节点。

     3. 当数组长度到达总长度的加载因子倍,扩容为原容量的两倍

     4. 当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置,然后获取值对象。找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。

     5.如果这个节点是数组中的,将新的节点替换原节点,如果是链表或红黑树中的节点,只修改原节点的value值。

📕总结

以上是hashmap的底层分析,希望对你有帮助

相关文章
|
1月前
|
安全 架构师 Java
Java大厂面试高频:Collection 和 Collections 到底咋回答?
Java中的`Collection`和`Collections`是两个容易混淆的概念。`Collection`是集合框架的根接口,定义了集合的基本操作方法,如添加、删除等;而`Collections`是一个工具类,提供了操作集合的静态方法,如排序、查找、同步化等。简单来说,`Collection`关注数据结构,`Collections`则提供功能增强。通过小王的面试经历,我们可以更好地理解这两者的区别及其在实际开发中的应用。希望这篇文章能帮助你掌握这个经典面试题。
44 4
|
2月前
|
存储 安全 Java
Java 集合框架中的老炮与新秀:HashTable 和 HashMap 谁更胜一筹?
嗨,大家好,我是技术伙伴小米。今天通过讲故事的方式,详细介绍 Java 中 HashMap 和 HashTable 的区别。从版本、线程安全、null 值支持、性能及迭代器行为等方面对比,帮助你轻松应对面试中的经典问题。HashMap 更高效灵活,适合单线程或需手动处理线程安全的场景;HashTable 较古老,线程安全但性能不佳。现代项目推荐使用 ConcurrentHashMap。关注我的公众号“软件求生”,获取更多技术干货!
52 3
|
3月前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
130 2
|
26天前
|
Java 程序员
Java社招面试中的高频考点:Callable、Future与FutureTask详解
大家好,我是小米。本文主要讲解Java多线程编程中的三个重要概念:Callable、Future和FutureTask。它们在实际开发中帮助我们更灵活、高效地处理多线程任务,尤其适合社招面试场景。通过 Callable 可以定义有返回值且可能抛出异常的任务;Future 用于获取任务结果并提供取消和检查状态的功能;FutureTask 则结合了两者的优势,既可执行任务又可获取结果。掌握这些知识不仅能提升你的编程能力,还能让你在面试中脱颖而出。文中结合实例详细介绍了这三个概念的使用方法及其区别与联系。希望对大家有所帮助!
163 60
|
2天前
|
Java 程序员 开发者
Java社招面试题:一个线程运行时发生异常会怎样?
大家好,我是小米。今天分享一个经典的 Java 面试题:线程运行时发生异常,程序会怎样处理?此问题考察 Java 线程和异常处理机制的理解。线程发生异常,默认会导致线程终止,但可以通过 try-catch 捕获并处理,避免影响其他线程。未捕获的异常可通过 Thread.UncaughtExceptionHandler 处理。线程池中的异常会被自动处理,不影响任务执行。希望这篇文章能帮助你深入理解 Java 线程异常处理机制,为面试做好准备。如果你觉得有帮助,欢迎收藏、转发!
33 14
|
5天前
|
安全 Java 程序员
Java 面试必问!线程构造方法和静态块的执行线程到底是谁?
大家好,我是小米。今天聊聊Java多线程面试题:线程类的构造方法和静态块是由哪个线程调用的?构造方法由创建线程实例的主线程调用,静态块在类加载时由主线程调用。理解这些细节有助于掌握Java多线程机制。下期再见! 简介: 本文通过一个常见的Java多线程面试题,详细讲解了线程类的构造方法和静态块是由哪个线程调用的。构造方法由创建线程实例的主线程调用,静态块在类加载时由主线程调用。理解这些细节对掌握Java多线程编程至关重要。
34 13
|
25天前
|
算法 安全 Java
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
65 16
|
22天前
|
Java 程序员 调度
Java 高级面试技巧:yield() 与 sleep() 方法的使用场景和区别
本文详细解析了 Java 中 `Thread` 类的 `yield()` 和 `sleep()` 方法,解释了它们的作用、区别及为什么是静态方法。`yield()` 让当前线程释放 CPU 时间片,给其他同等优先级线程运行机会,但不保证暂停;`sleep()` 则让线程进入休眠状态,指定时间后继续执行。两者都是静态方法,因为它们影响线程调度机制而非单一线程行为。这些知识点在面试中常被提及,掌握它们有助于更好地应对多线程编程问题。
55 9
|
27天前
|
安全 Java 程序员
Java面试必问!run() 和 start() 方法到底有啥区别?
在多线程编程中,run和 start方法常常让开发者感到困惑。为什么调用 start 才能启动线程,而直接调用 run只是普通方法调用?这篇文章将通过一个简单的例子,详细解析这两者的区别,帮助你在面试中脱颖而出,理解多线程背后的机制和原理。
59 12
|
1月前
|
监控 Dubbo Java
Java Dubbo 面试题
Java Dubbo相关基础面试题

热门文章

最新文章