史上最全的Java容器集合之HashMap(源码解读)(二)

简介: 史上最全的Java容器集合之HashMap(源码解读)(二)

HashMap的成员方法

put方法

//向哈希表中添加元素
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
复制代码
  • 向用户开放的put方法调用的是putVal方法:
  • putVal方法需要判断是否出现哈希冲突问题:
  • 其中如果哈希值相等,key也相等,则是覆盖value操作;如果不是覆盖操作,则插入一个普通链表节点;
  • 遍历到尾部,追加新节点到尾部;
  • 在元素添加的过程中需要随时检查是否需要进行转换成红黑树的操作;
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    //tab存放当前的哈希桶,p用作临时链表节点  
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果当前哈希表是空的,代表是初始化
    if ((tab = table) == null || (n = tab.length) == 0)
    //那么直接去扩容哈希表,并且将扩容后的哈希桶长度赋值给n
    n = (tab = resize()).length;
    //如果当前index的节点是空的,表示没有发生哈希碰撞。直接构建一个新节点Node,挂载在index处即可。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//否则 发生了哈希冲突。
        Node<K,V> e; K k;
        //如果哈希值相等,key也相等,则是覆盖value操作
        if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
            e = p;//将当前节点引用赋值给e
        else if (p instance of 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;
                }
                //如果找到了要覆盖的节点
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果e不是null,说明有需要覆盖的节点,
        if (e != null) { // existing mapping for key
            //则覆盖节点值,并返回原oldValue
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //这是一个空实现的函数,用作LinkedHashMap重写使用。
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //如果执行到了这里,说明插入了一个新的节点,所以会修改modCount,以及返回null。
    ++modCount;
    //更新size,并判断是否需要扩容。
    if (++size > threshold)
    resize();
    //这是一个空实现的函数,用作LinkedHashMap重写使用。
    afterNodeInsertion(evict);
    return null;
}
复制代码

image.png

总结一下put过程

  • 第一步当然是先计算key的hash值(有过处理的 (h = key.hashCode()) ^ (h >>> 16))
  • 第二步调用putval方法,然后判断是否容器中全部为空,如果是的话,就把容器的容量扩容。
  • 第三步,把最大容量和hash值求&值(i = (n - 1) & hash),判断这个数组下标是否有数据,如果没有就把它放进去。还要判断key的equals方法,看是否需要覆盖。
  • 第四步,如果有,说明发生了碰撞,那么继续遍历判断链表的长度是否大于8,如果大于8,就继续把当前链表变成红黑树结构。
  • 第五步,如果没有到8,那么就直接把数据存在链表的尾部
  • 第六步,最后将容器的容量+1。

key.hashCode()是Key自带的hashCode()方法,返回一个int类型的散列值。我们大家知道,32位带符号的int表值范围从-2147483648到2147483648。这样只要hash函数松散的话,一般是很难发生碰撞的,因为HashMap的初始容量只有16。但是这样的散列值我们是不能直接拿来用的。用之前需要对数组的长度取模运算。得到余数才是索引值。

get方法

public V get(Object key) {
    Node<K,V> e;
    //传入扰动后的哈希值 和 key 找到目标节点Node
    return (e = getNode(hash(key), key)) == null ? null : e.value; 
}
复制代码

HashMap向用户分开放的get方法是调用的getNode方法来实现的

//传入扰动后的哈希值 和 key 找到目标节点Node
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //查找过程,找到返回节点,否则返回null
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            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;
}
复制代码

简单讲讲查询过程,还是比较简单的

  • 第一步,看下整个容器是否为空。
  • 第二步,如果不为空,再比较hash值的同时需要比较key的值是否相同e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))
  • 然后返回

contains

 HashMap没有提供判断元素是否存在的方法,只提供了判断Key是否存在及Value是否存在的方法,分别是containsKey(Object key)、containsValue(Object value)。 containsKey(Object key)方法很简单,只是判断getNode (key)的结果是否为null,是则返回false,否返回true。

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null; 
}
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    //遍历哈希桶上的每一个链表
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
            //如果找到value一致的返回true
            if ((v = e.value) == value || (value != null && value.equals(v)))
                return true;
            }
        }
    }
    return false; 
}
复制代码

判断一个value是否存在比判断key是否存在还要简单,就是遍历所有元素判断是否有相等的值。这里分为两种情况处理,value为null何不为null的情况,但内容差不多,只是判断相等的方式不同。这个判断是否存在必须遍历所有元素,是一个双重循环的过程,因此是比较耗时的操作。

remove方法

HashMap中“删除”相关的操作,有remove(Object key)和clear()两个方法。 其中向用户开放的remove方法调用的是removeNode方法,,removeNode (key)的返回结果应该是被移除的元素,如果不存在这个元素则返回为null。remove方法根据removeEntryKey返回的结果e是否为null返回null或e.value。

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; 
}
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    // p 是待删除节点的前置节点
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //如果哈希表不为空,则根据hash值算出的index下 有节点的话。
    if ((tab = table) != null && (n = tab.length) > 0&&(p = tab[index = (n - 1) & hash]) != null) {
        //node是待删除节点
        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;//将待删除节点引用赋给node
        else if ((e = p.next) != null) {//否则循环遍历 找到待删除节点,赋值给node
            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);
            }
        }
        //如果有待删除节点node,  且 matchValue为false,或者值也相等
        if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)//如果node == p,说明是链表头是待删除节点
                tab[index] = node.next;
            else//否则待删除节点在表中间
                p.next = node.next;
            ++modCount;//修改modCount
            --size;//修改size
            afterNodeRemoval(node);//LinkedHashMap回调函数
            return node;
        }
    }
    return null;
}
复制代码

 clear()方法删除HashMap中所有的元素,这里就不用一个个删除节点了,而是直接将table数组内容都置空,这样所有的链表都已经无法访问,Java的垃圾回收机制会去处理这些链表。table数组置空后修改size为0。

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}
复制代码

总结

HashMap是我写的最长的一篇文章,但是还有很多没有写完,比如它的迭代器(Map是否有序,这个下篇得讲),它的红黑树,实在写不动了,我太难了。也是我菜,红黑树,还没好好学一下,什么左旋,右旋头晕。哈哈 以后有机会会好好补这个坑的。

问大家几个问题

  • HashMap 的容量为啥是2的幂次方
  • HashMap 的扩容伐值为什么是0.75
  • HashMap 它的链表的插入是头插入还是尾插

给大家讲个故事 再Jdk1.7的时候 tomcat 的url上的请求参数 是用HashMap存的 因为它的查询是n(o),但是黑客可以找一些url的参数HashCode相同,几十万个,这样就导致查询非常慢,搞几下就可以把一个网站搞死,后面tomcat 还去找了jdk的人,但是让人家说这不是bug,最后tomcat就自己做了限制 哈哈。

大家如果能对着源码跟着过一遍也好,至少看过源码不是,我们知道HashMap 是线程不安全的,那线程安全的Map是啥,我们知道HashMap是无序的,有序的Map又是啥。各位一起加油吧,路慢慢慢其修远。

版本说明

  • 这里的源码是JDK8版本,不同版本可能会有所差异,但是基本原理都是一样的。

因为博主也是一个开发萌新 我也是一边学一边写 我有个目标就是一周 二到三篇 希望能坚持个一年吧 希望各位大佬多提意见,让我多学习,一起进步。

目录
相关文章
|
15天前
|
XML Java 编译器
Java注解的底层源码剖析与技术认识
Java注解(Annotation)是Java 5引入的一种新特性,它提供了一种在代码中添加元数据(Metadata)的方式。注解本身并不是代码的一部分,它们不会直接影响代码的执行,但可以在编译、类加载和运行时被读取和处理。注解为开发者提供了一种以非侵入性的方式为代码提供额外信息的手段,这些信息可以用于生成文档、编译时检查、运行时处理等。
50 7
|
1月前
|
Java
Java之HashMap详解
本文介绍了Java中HashMap的源码实现(基于JDK 1.8)。HashMap是基于哈希表的Map接口实现,允许空值和空键,不同步且线程不安全。文章详细解析了HashMap的数据结构、主要方法(如初始化、put、get、resize等)的实现,以及树化和反树化的机制。此外,还对比了JDK 7和JDK 8中HashMap的主要差异,并提供了使用HashMap时的一些注意事项。
Java之HashMap详解
|
26天前
|
数据采集 人工智能 Java
Java产科专科电子病历系统源码
产科专科电子病历系统,全结构化设计,实现产科专科电子病历与院内HIS、LIS、PACS信息系统、区域妇幼信息平台的三级互联互通,系统由门诊系统、住院系统、数据统计模块三部分组成,它管理了孕妇从怀孕开始到生产结束42天一系列医院保健服务信息。
28 4
|
1月前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
71 2
|
7天前
|
存储 JavaScript 前端开发
基于 SpringBoot 和 Vue 开发校园点餐订餐外卖跑腿Java源码
一个非常实用的校园外卖系统,基于 SpringBoot 和 Vue 的开发。这一系统源于黑马的外卖案例项目 经过站长的进一步改进和优化,提供了更丰富的功能和更高的可用性。 这个项目的架构设计非常有趣。虽然它采用了SpringBoot和Vue的组合,但并不是一个完全分离的项目。 前端视图通过JS的方式引入了Vue和Element UI,既能利用Vue的快速开发优势,
54 13
|
21天前
|
缓存 监控 Java
Java线程池提交任务流程底层源码与源码解析
【11月更文挑战第30天】嘿,各位技术爱好者们,今天咱们来聊聊Java线程池提交任务的底层源码与源码解析。作为一个资深的Java开发者,我相信你一定对线程池并不陌生。线程池作为并发编程中的一大利器,其重要性不言而喻。今天,我将以对话的方式,带你一步步深入线程池的奥秘,从概述到功能点,再到背景和业务点,最后到底层原理和示例,让你对线程池有一个全新的认识。
50 12
|
15天前
|
JavaScript 安全 Java
java版药品不良反应智能监测系统源码,采用SpringBoot、Vue、MySQL技术开发
基于B/S架构,采用Java、SpringBoot、Vue、MySQL等技术自主研发的ADR智能监测系统,适用于三甲医院,支持二次开发。该系统能自动监测全院患者药物不良反应,通过移动端和PC端实时反馈,提升用药安全。系统涵盖规则管理、监测报告、系统管理三大模块,确保精准、高效地处理ADR事件。
|
1月前
|
人工智能 监控 数据可视化
Java智慧工地信息管理平台源码 智慧工地信息化解决方案SaaS源码 支持二次开发
智慧工地系统是依托物联网、互联网、AI、可视化建立的大数据管理平台,是一种全新的管理模式,能够实现劳务管理、安全施工、绿色施工的智能化和互联网化。围绕施工现场管理的人、机、料、法、环五大维度,以及施工过程管理的进度、质量、安全三大体系为基础应用,实现全面高效的工程管理需求,满足工地多角色、多视角的有效监管,实现工程建设管理的降本增效,为监管平台提供数据支撑。
40 3
|
17天前
|
人工智能 移动开发 安全
家政上门系统用户端、阿姨端源码,java家政管理平台源码
家政上门系统基于互联网技术,整合大数据分析、AI算法和现代通信技术,提供便捷高效的家政服务。涵盖保洁、月嫂、烹饪等多元化服务,支持多终端访问,具备智能匹配、在线支付、订单管理等功能,确保服务透明、安全,适用于家庭生活的各种需求场景,推动家政市场规范化发展。
|
1月前
|
运维 自然语言处理 供应链
Java云HIS医院管理系统源码 病案管理、医保业务、门诊、住院、电子病历编辑器
通过门诊的申请,或者直接住院登记,通过”护士工作站“分配患者,完成后,进入医生患者列表,医生对应开具”长期医嘱“和”临时医嘱“,并在电子病历中,记录病情。病人出院时,停止长期医嘱,开具出院医嘱。进入出院审核,审核医嘱与住院通过后,病人结清缴费,完成出院。
90 3
下一篇
DataWorks