图解 Java 中的数据结构及原理,傻瓜也能看懂!
最近在整理数据结构方面的知识, 系统化看了下Java中常用数据结构, 突发奇想用动画来绘制数据流转过程。
主要基于jdk8, 可能会有些特性与jdk7之前不相同, 例如LinkedList LinkedHashMap中的双向列表不再是回环的。
HashMap中的单链表是尾插, 而不是头插入等等, 后文不再赘叙这些差异, 本文目录结构如下:
LinkedList
经典的双链表结构, 适用于乱序插入, 删除. 指定序列操作则性能不如ArrayList, 这也是其数据结构决定的.
add(E) / addLast(E)
add(index, E)
这边有个小的优化, 他会先判断index是靠近队头还是队尾, 来确定从哪个方向遍历链入.
靠队尾
get(index)
也是会先判断index, 不过性能依然不好, 这也是为什么不推荐用for(int i = 0; i < lengh; i++)的方式遍历linkedlist, 而是使用iterator的方式遍历.
remove(E)
ArrayList
底层就是一个数组, 因此按序查找快, 乱序插入, 删除因为涉及到后面元素移位所以性能慢.
add(index, E)
扩容
一般默认容量是10, 扩容后, 会length*1.5.
remove(E)
循环遍历数组, 判断E是否equals当前元素, 删除性能不如LinkedList.
Stack
经典的数据结构, 底层也是数组, 继承自Vector, 先进后出FILO, 默认new Stack()容量为10, 超出自动扩容.
push(E)
pop()
后缀表达式
Stack的一个典型应用就是计算表达式如 9 + (3 - 1) * 3 + 10 / 2, 计算机将中缀表达式转为后缀表达式, 再对后缀表达式进行计算。
中缀转后缀
数字直接输出
栈为空时,遇到运算符,直接入栈
遇到左括号, 将其入栈
遇到右括号, 执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出。
遇到运算符(加减乘除):弹出所有优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈
最终将栈中的元素依次出栈,输出。
计算后缀表达
遇到数字时,将数字压入堆栈
遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算, 并将结果入栈
重复上述过程直到表达式最右端
运算得出的值即为表达式的结果
队列
与Stack的区别在于, Stack的删除与添加都在队尾进行, 而Queue删除在队头, 添加在队尾.
ArrayBlockingQueue
生产消费者中常用的阻塞有界队列, FIFO.
put(E)
put(E) 队列满了
take()
当元素被取出后, 并没有对数组后面的元素位移, 而是更新takeIndex来指向下一个元素.
takeIndex是一个环形的增长, 当移动到队列尾部时, 会指向0, 再次循环.
HashMap
最常用的哈希表, 面试的童鞋必备知识了, 内部通过数组 + 单链表的方式实现. jdk8中引入了红黑树对长度 > 8的链表进行优化, 我们另外篇幅再讲。推荐阅读:Java 程序员必须掌握的 8 道数据结构面试题,你会几道?
put(K, V)
put(K, V) 相同hash值
resize 动态扩容
当map中元素超出设定的阈值后, 会进行resize (length * 2)操作, 扩容过程中对元素一通操作, 并放置到新的位置。
具体操作如下:
在jdk7中对所有元素直接rehash, 并放到新的位置.
在jdk8中判断元素原hash值新增的bit位是0还是1, 0则索引不变, 1则索引变成"原索引 + oldTable.length".
LinkedHashMap
继承自HashMap, 底层额外维护了一个双向链表来维持数据有序. 可以通过设置accessOrder来实现FIFO(插入有序)或者LRU(访问有序)缓存.
put(K, V)
get(K)
accessOrder为false的时候, 直接返回元素就行了, 不需要调整位置.
accessOrder为true的时候, 需要将最近访问的元素, 放置到队尾.
removeEldestEntry 删除最老的元素
欢迎工作一到五年的Java工程师朋友们加入Java填坑之路:860113481
群内提供免费的Java架构学习资料(里面有高可用、高并发、高性能及分布式、Jvm性能调优、Spring源码,MyBatis,Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多个知识点的架构资料)合理利用自己每一分每一秒的时间来学习提升自己,不要再用"没有时间“来掩饰自己思想上的懒惰!趁年轻,使劲拼,给未来的自己一个交代!
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
java B2B2C源码电子商务平台
springCloud是基于SpringBoot的一整套实现微服务的框架。他提供了微服务开发所需的配置管理、服务发现、断路器、智能路由、微代理、控制总线、全局锁、决策竞选、分布式会话和集群状态管理等组件。愿意了解源码的朋友直接求求交流分享技术:二一四七七七五六三三 SpringBoot旨在简化创建产品级的 Spring 应用和服务,简化了配置文件,使用嵌入式web服务器,含有诸多开箱即用微服务功能。 pring cloud子项目包括: Spring Cloud Config:配置管理开发工具包,可以让你把配置放到远程服务器,目前支持本地存储、Git以及Subversion。 Spring Cloud Bus:事件、消息总线,用于在集群(例如,配置变化事件)中传播状态变化,可与Spring Cloud Config联合实现热部署。 Spring Cloud Netflix:针对多种Netflix组件提供的开发工具包,其中包括Eureka、Hystrix、Zuul、Archaius等。 Netflix Eureka:云端负载均衡,一个基于 REST 的服务,用于定位服务,以实现云端的负载均...
- 下一篇
Java程序员!进阿里前这6大知识点你真的需要梳理一下了(年后跳槽必看)
如果你的目标仅仅是提高自己,那么很容易实现,但是如果你的目标是成为一个高薪的Java架构师,那么这就不简单了。 工作越久,经验值越高,越能为企业创造价值。业内人士表示,实际上,在工作中往往会受到职业限制。随着分工的细化,一般的企业给员工安排工作岗位常常是“一锤子”买卖,多年一直不变。这样一来,员工的工作经验并没有随着年限的增长而增加,竞争力也会随着年龄的增加而下降。他们也会更加珍惜现有的岗位,尽力完成企业的要求。但是要想保住工作,光靠这点还远远不够。特别是一些年龄在30+,上有老下有小,更需要去努力证明自己的能力,靠自己多去付出来获取尊重,如果的思维还是停留在不跳槽不涨工资,太局限了吧! 很多人都愿意说,我想变得更好,但是更好是什么却很模糊,而且人们也不知道该怎么样去做。 时间到了,提高你的编程技能,认真+严肃,走起! 我在这里分享“6”个专项来帮助你顺利提高你的编程技能。 架构筑基篇 深入内核,直击故障,拒绝蒙圈 开源框架解析篇 站在巨人肩膀,收获不一样的视野 高性能架构篇 成为互联网架构师,你要的都在这里 微服务架构篇 你还不知道微服务?那怎么加(zhuang)薪(bi) 团队协作...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Docker安装Oracle12C,快速搭建Oracle学习环境
- CentOS8安装Docker,最新的服务器搭配容器使用
- Windows10,CentOS7,CentOS8安装Nodejs环境
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- Linux系统CentOS6、CentOS7手动修改IP地址
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- MySQL8.0.19开启GTID主从同步CentOS8