首页 > 其他分享 >思考:JDK1.8之后HashMap为什么要加入红黑树

思考:JDK1.8之后HashMap为什么要加入红黑树

时间:2024-01-26 12:11:06浏览次数:31  
标签:JDK1.8 HashMap equals hashCode 哈希 红黑树 重写

在JDK1.7时
如果构造1000w个哈希码相同的字符串,把他们全部插入HashMap中,这将导致严重的哈希冲突
1000w个字符串全部挤入到一个哈希桶中,从而形成一个超长链表,这时候的HashMap的性能将从O(1)退化到O(n)

为什么性能会退化到O(n)?
因为在插入的时候要先比较这个节点是不是存在,因为每个字符串都是不一样的,所以它要把所有节点全部遍历完之后,才能发现不存在
当插入的节点越多,那么它遍历的节点也就越多,自然而然性能就会持续往下降

这就是所谓的哈希攻击,通过精心构造的字符串,让他们的哈希code一样,最后把他们全部挤入到一个哈希桶中,从而形成一个超长的链表,把它的速度从O(1)退化到O(n)

如何防止这种哈希碰撞攻击?
JDK1.8之后的HashMap升级了红黑树,当冲突的节点超过了8个就会树化,而红黑树的性能是O(log n),虽然不及原来的O(1),但是这个速度也是可以接受的

那是不是升级了之后的HashMap就再也不用担心这种哈希攻击了?
那也不一定,如果去重写了hashCode和equals方法的话,在这种情况,红黑树也救不了

红黑树性能退化分析
我们知道红黑树的查找类似二分查找,查询时与当前节点比较,比他大就往右走,比他小就往左边走,但是这里的hashCode都是同一个值,就无法比较大小,只能全部遍历了,性能就会从O(log n)退化到O(n)

但是为什么没有重写hashCode和equals方法就可以抵御哈希攻击呢?
因为HashMap还留了一手

它的红黑树是经过特殊定制的,当比较的hashCode相等时,且key不相等,就会继续用key值比较大小,以继续支持二分查找
所以如果重写了hashCode和equals方法之后,这个key并不是一个可比较的对象,所以就直接退化到O(n)

给这个key实现Comparable接口可以重新恢复之前的效率

以下是个人的理解

JDK1.8HashMap为什么要去升级红黑树?
当有大量hashCode相同的数据插入时,会使哈希表中的某一个桶中链表过长,就会将其转换为红黑树,红黑树的任何操作都是O(log n),这样即使有大量相同的hashCode的数据,HashMap在该桶下操作的时间复杂度也只会从O(1)降到O(log n),而不会降到O(n)

红黑树为什么不直接用TreeMapp,而是自己去写一个?
虽然TreeMap也使用红黑树,但是TreeMap要求键实现Comparable接口或者提供Comparator来进行比较。而HashMap在使用红黑树时并不要求键实现Comparable接口。
这是因为HashMap在使用红黑树时,会使用特殊的比较方式来处理没有实现的Comparable接口的键

重写hashCode与equals方法到底会对HashMap造成哪些影响?
HashMap是通过实例对象的hashCode方法去找数据所在的桶,在通过对象的equals去该桶中寻找对应的数据,去比较对象是否相等
当我们new了两个相同数据的对象,不重写hashCode和equals方法。插入到HashMap中,由于hashCode和equals均不相等,HashMap会认为这是两个不同的对象
如果重写的了hashCode和equals方法则会认为这两个对象是相同的
具体要不要重写,怎么重写,还要看自己的业务

标签:JDK1.8,HashMap,equals,hashCode,哈希,红黑树,重写
From: https://www.cnblogs.com/zhao-zong-yu-hai/p/17989060

相关文章

  • ConcurrentHashMap源码逐行解读基于jdk1.8
    前导知识//node数组最大容量:2^30=1073741824privatestaticfinalintMAXIMUM_CAPACITY=1<<30;//默认初始值,必须是2的幕数privatestaticfinalintDEFAULT_CAPACITY=16;//数组可能最大值,需要与toArray()相关方法关联st......
  • 简单剖析Hashmap
    剖析JavaHashmap源码在Java的集合框架中,HashMap是一颗璀璨的明珠。通过深入挖掘其源码,我们将揭开HashMap的神秘面纱,理解其底层原理、扩容机制和数据结构。1.HashMap源码导读我们首先来看一段简单的代码,创建一个空的HashMap:importjava.util.HashMap;publicclass......
  • 《数据篇》HashMap
    简介参考链接:https://www.cnblogs.com/scxgy/p/15398631.htmlHashMap是一个散列表,它存储的内容是键值对(key-value)映射。它是无序的,不会记录插入的顺序。(散列表,英文hashtable)HashMap实现了Map接口,根据键的HashCode值存储数据,最多允许一条记录的键为null,不支持线程同步。HashMa......
  • 【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(下)
    承接上文在阅读了上篇文章《【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(上)》之后,相信您对HashMap的基本原理和基础结构已经有了初步的认识。接下来,我们将进一步深入探索HashMap的源码,揭示其深层次的技术细节。通过这次解析,您将更深入地理解HashMap的......
  • HashMap & HashSet源码阅读
    目录简介模型代码分析成员变量方法参考链接本人的源码阅读主要聚焦于类的使用场景,一般只在java层面进行分析,没有深入到一些native方法的实现。并且由于知识储备不完整,很可能出现疏漏甚至是谬误,欢迎指出共同学习本文基于corretto-17.0.9源码,参考本文时请打开相应的源码对照,否则......
  • 【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(上)
    知识盲点概念介绍HashMap是基于Map接口构建的数据结构,它以键值对的形式存储元素,允许键和值都为null。由于键的唯一性,HashMap中只能有一个键为null。HashMap的特点是元素的无序性和不重复性。注意,HashMap并不是线程安全的。在多线程环境下,如果不进行适当的同步处理,可能会导致数据不......
  • HashMap源码随笔
    源码第一块:概述:Map接口的基于哈希表的实现。此实现提供所有可选的映射操作,并允许null值和null键。(HashMap类大致等同于Hashtable,只不过它是不同步的,并且允许null。此类不保证地图的顺序;特别是,它不保证订单会随着时间的推移保持不变。此实现为基本操作(get和put)提供恒......
  • linux 部署 jdk1.8
    将文件(jdk-8u391-linux-x64.tar.gz)上传到服务器的文件中。我是放到了/usr/local/jdk文件夹下面。然后输入指令压文件tar-zvxfjdk-8u391-linux-x64.tar.gz找到 /etc/profile文件,在最后一行添加exportJAVA_HOME=/usr/local/jdk/jdk1.8.0_391exportCLASSPATH=$:......
  • 第十二节:红黑树性质、相对平衡的原理、与AVL树的区别
    一.        二.        三.         !作       者:Yaopengfei(姚鹏飞)博客地址:http://www.cnblogs.com/yaopengfei/声     明1:如有错误,欢迎讨论,请勿谩骂^_^。声     明2:原创博客请在转载......
  • JDK1.8 如何升级到JDK17?详细图文讲解亲测有效
    前言电脑上之前已经安装了jdk1.8的版本,由于现在很多新的jar包需要jdk11以上版本。那么如何升级到jdk17的版本一、检查当前jdk版本java-version如果你本地已经有1.8版本了找到环境变量设置地方JAVA_HOME二、JDK17下载官方下载地址(Oracle中国的官方网站)https://www.or......