hashmap的底层实现原理_hashtable底层数据结构

hashmap的底层实现原理_hashtable底层数据结构一:HashMap底层实现原理解析我们常见的有数据结构有三种结构:1、数组结构2、链表结构3、哈希表结构下面我们来看看各自的数据结构的特点:1、数组结构:存储区间连续、内存占用严重、空间复杂度大优点:随机读取和修改效率高,原因是数组是连续的(随机访问性强,查找速度快)缺点:插入和删除数据效率低,因插入数据,这个位置后面的数据在内存中都要往后移动,且大小固定不易动态扩展。2、链表结构:存储区间离散、占用内存宽松、空间复杂度小优点:插入删除速度快,内存利用率高,没有固定大小,扩展灵活

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一:HashMap底层实现原理解析

我们常见的有数据结构有三种结构:1、数组结构 2、链表结构 3、哈希表结构 下面我们来看看各自的数据结构的特点:
1、数组结构: 存储区间连续、内存占用严重、空间复杂度大

  • 优点:随机读取和修改效率高,原因是数组是连续的(随机访问性强,查找速度快)
  • 缺点:插入和删除数据效率低,因插入数据,这个位置后面的数据在内存中都要往后移动,且大小固定不易动态扩展。

2、链表结构:存储区间离散、占用内存宽松、空间复杂度小

  • 优点:插入删除速度快,内存利用率高,没有固定大小,扩展灵活
  • 缺点:不能随机查找,每次都是从第一个开始遍历(查询效率低)

3、哈希表结构:结合数组结构和链表结构的优点,从而实现了查询和修改效率高,插入和删除效率也高的一种数据结构
常见的HashMap就是这样的一种数据结构
在这里插入图片描述

HashMap中的put()和get()的实现原理

  • 1、map.put(k,v)实现原理
    (1)首先将k,v封装到Node对象当中(节点)。
    (2)然后它的底层会调用K的hashCode()方法得出hash值。
    (3)通过哈希表函数/哈希算法,将hash值转换成数组的下标,下标位置上如果没有任何元素,就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时,就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false,那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true,那么这个节点的value将会被覆盖。
  • 2、map.get(k)实现原理
    (1)先调用k的hashCode()方法得出哈希值,并通过哈希算法转换成数组的下标。
    (2)通过上一步哈希算法转换成数组的下标之后,在通过数组下标快速定位到某个位置上。如果这个位置上什么都没有,则返回null。如果这个位置上有单向链表,那么它就会拿着K和单向链表上的每一个节点的K进行equals,如果所有equals方法都返回false,则get方法返回null。如果其中一个节点的K和参数K进行equals返回true,那么此时该节点的value就是我们要找的value了,get方法最终返回这个要找的value。

为何随机增删、查询效率都很高的原因是?
原因: 增删是在链表上完成的,而查询只需扫描部分,则效率高。

HashMap集合的key,会先后调用两个方法,hashCode and equals方法,这这两个方法都需要重写。

为什么放在hashMap集合key部分的元素需要重写equals方法?
因为equals方法默认比较的是两个对象的内存地址

二:HashMap红黑树原理分析

相比 jdk1.7 的 HashMap 而言,jdk1.8最重要的就是引入了红黑树的设计,当hash表的单一链表长度超过 8 个的时候,链表结构就会转为红黑树结构。
为什么要这样设计呢?好处就是避免在最极端的情况下链表变得很长很长,在查询的时候,效率会非常慢。
在这里插入图片描述

  • 红黑树查询:其访问性能近似于折半查找,时间复杂度 O(logn);
  • 链表查询:这种情况下,需要遍历全部元素才行,时间复杂度 O(n);

简单的说,红黑树是一种近似平衡的二叉查找树,其主要的优点就是“平衡“,即左右子树高度几乎一致,以此来防止树退化为链表,通过这种方式来保障查找的时间复杂度为 log(n)。
在这里插入图片描述
关于红黑树的内容,网上给出的内容非常多,主要有以下几个特性:

  • 1、每个节点要么是红色,要么是黑色,但根节点永远是黑色的;

  • 2、每个红色节点的两个子节点一定都是黑色;

  • 3、红色节点不能连续(也即是,红色节点的孩子和父亲都不能是红色);

  • 4、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点;

  • 5、所有的叶节点都是是黑色的(注意这里说叶子节点其实是上图中的 NIL 节点);

在树的结构发生改变时(插入或者删除操作),往往会破坏上述条件 3 或条件 4,需要通过调整使得查找树重新满足红黑树的条件。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/195154.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 微信小程序开发【前端+后端(java)】

    微信小程序开发【前端+后端(java)】前言现在微信小程序越来越火了,相信不少人都通过各种途径学习过微信小程序或者尝试开发,作者就是曾经由于兴趣了解开发过微信小程序,最终自己的毕业设计也是开发一个微信小程序。所以现在用这篇博客记录我之前开发的一些经验和一些心得吧。主要内容springboot+mybatis构建小程序项目构建小程序组件讲解小程序api调用后台resetful接口编写小程序调用后台接口小…

  • Microsoft.XMLDOM相关资料

    Microsoft.XMLDOM相关资料

  • php小区物业管理系统_代挂网源码最新版

    php小区物业管理系统_代挂网源码最新版萌驰物管家目前采用的是:域名授权(不限制IP,域名只授权一个,但您可以解析多个域名到同一站点,授权的域名必须保证可以访问到站点)萌驰物管家老客户首次更换授权域名是免费的,之后收费标准:800/次关于支付微信支付官方通道可以走服务商自己的,非法人结算对私结算可以走悟能科技对接好的(汇付天下,随行付,乐刷,等)。独立部署只有后台跟公众号及小程序APP需要单独购买2万一个端。悟能科技官网:www.wun…

    2022年10月18日
  • C++星火03_valist用法

    C++星火03_valist用法1背景函数的参数一般是用栈的形式从右向左进行存储的,所以提取时候是从左向右提取例:#includeusingnamespacestd;voidfun(intnCnt,…){int*pTemp=&nCnt;pTemp++;for(inti=0;i{coutpTemp++;}cout}

    2022年10月27日
  • Vue子组件向父组件传值(this.$emit()方法)「建议收藏」

    Vue子组件向父组件传值(this.$emit()方法)「建议收藏」子组件使用this.$emit()向父组件传值首先必须在父组件中引用子组件,然后实现传值 第一步在父组件中引入子组件 使用import引入组件importindexImportOrderfrom’./components/indexImportOrder’声明//定义组件components:{indexImportOrder,…

  • java final keyword

    java final keyword

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号