飞哥王某

飞哥王某 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑

关注公众号 码上实战

个人动态

飞哥王某 发布了文章 · 2020-03-26

故事:走进JVM的世界(图文并茂)

原文:故事:走进JVM的世界(图文并茂)

走进JVM的世界

  1. 注意!本文较长,建议先收藏再阅读。更多文章可以关注作者公众号:码上实战
  2. 你也可以 star 我的 GitHub上本文所属仓库:https://github.com/flyhero/Ma...
  3. 说明:本文在 Java 8 Hotspot 64位操作系统下构思

小强是一个工作3年有余的开发工程师,从他的发量你就可以知道,小强资历还尚浅。

程序员惊人发量

最近公司没什么事,他也开始无聊起来了。这天下午,同事们在激烈的讨论这业务,但他没有参与,于是他决定学习些什么知识,无聊的翻着各个网页,发现JVM是各位大神们推荐过的知识,于是决定好好看一看。

5分钟过后……

小强感到这知识有些枯燥乏味,怪不得是大神们能看的!又看了几分钟,小强倦意袭来,揉了揉睡眼惺忪的眼睛。

然而就在这一刻,他突然发现周围同事激烈讨论的声音听不到了,安静到了极致。

1. 入界

小强努力的睁开眼睛,才发现自己竟然身处一个白茫茫的空间中,吓得一跳,心想我这是怎么了,穿越了?但穿越也得穿越到一个人间如画,美女如云的地方啊……,这境地……
JVM幻境

突然前方走来一个白胡子老头,小强正想开口,老头捷足先登:你好,我是这个JVM世界的缔造者,你可以叫我 “HotSpot”,不过这无所谓,因为我所创造的这个世界,是按照 “JVM规范” 来完成的。我正在休息时,发现来了一位客人,原来是你。

小强:我是想问……

老头: 不用问,我知道,你是想了解一下我创造的这个世界吧!跟我来吧。

这老头,我还没说话,这就结束了!好吧,跟你看看且说。

老头边走边道:JVM 的世界 空间是有限的,我们坚持一个原则 : 各司其职,不留无用之人!

小强: 啊!好残酷。

老头: 不,这不是残酷,我们这个世界生来就是为客户提供服务,为客户发光发热的,每个人奉献出了自己的能力就是圆满完成任务,退出舞台是理所应当的,也是他们最好的归宿。

小强:也是,这样这个世界才不会那么拥挤,才能井然有序的工作,我怎么这么不开窍呢……

2. 布局

过来,带你先看看我们世界的整体组成和中心区如何布局。
整体布局

先来看看我们最主要的日常工作区(运行时数据区),为了让我们工作起来更有效率,我们将世界空间划分为这几个板块。

居住区-堆

这里是人们工作外的居住区,居住区我们基于人们的年龄也进一步分出了,伊甸区,幸存者区,老年区。
居住区

工作区-栈

每个任务来临时,都会在工作区单独开辟出一个地方来用于完成这个任务。
栈帧

记录者-程序计数器

由于我们同时能做的任务有限,所以我们需要为不同的任务划分出不同的时间片,我们在切换任务的时候,需要一个记录者,能够记录我们这个任务做到了哪里,下次回来能够继续做。

仓库管理区-方法区

这里存放着工人的模板以及常用的不变的工具等。

3. 生与死

这里工作的人们都会经历生与死,大部分人们活不到老年,但这不重要,重要的是他为我们做出了贡献。

3.1 出生

老头:这里的每个人都有一个模板(类),看到那个正在居住区休息的高个吗?他叫张三,他是根据外部客户给定的模板 “ User Class” 创造的,他可是客户最喜爱的工人了。你知道客户的这些模板(类)是如何进入的到我们的世界中的吗?

小强:这个我知道点,之前看过一点点。这个过程还是有些复杂的,客户的模板(类)是通过一个翻译工厂(编译器) 将它翻译成class 字节码,因为你们这个世界只认识字节码,然后有你们的加载系统将它们加载到这里。

加载过程中有这些阶段:
loading-class.png

其中加载阶段是由加载器来完成的。

老头:是的,我们提供了三种工厂,启动类加载器,扩展类加载器,应用类加载器,当然客户也可以自定义加载器。
parents-delegation.png

小强:他们遵循着双亲委派模型,但是我一直不太理解这个词!

老头: 这是由于你们语言翻译的问题导致,这个模式叫 “parents delegation”,知道了吧!它是指有你的父辈们来帮你完成。

小强:那双亲委派模式 有什么好处呢?

老头:

  1. 具有优先级层次的关系可以避免模板(类)的重复加载
  2. 安全考虑可以防止Java核心api被替换

老头继续道:那连接过程中的三步,你知道是做什么吗?

小强:具体的我就不知道了哎……

老头笑了笑:对于客户定义的模板(类),我们可不是来者不拒的,为了我们这个世界的安全以及能提供更好的服务,我们会对模板做一些验证及后续操作。

验证包括格式验证,元数据验证,字节码验证,符号验证。当验证通过后,我们会为模板所依赖的东西(类变量)分配空间,最后将符号引用替换为直接引用。

老头看了看小强眉头紧皱,于是继续补充:你可能不了解什么是符号引用和直接引用!

符号引用就是在编译时,并不知道模板(类)所依赖的其他东西,会在我们的空间中的哪个位置,只能用符号来表示。

直接引用就是 所有东西被加载到这里后会有自己的真实空间地址,然后去替换符号引用。这样运行时就能找到它们所依赖的东西了。

最后就是初始化了,这个阶段主要是对类变量初始化,是执行类构造器的过程。

小强:我怎么没看到这些模板呢?

老头:这些模板我把他们隐藏在世界的后方,大多数人是见不到的,他们统称为 Klass。

小强:不对啊!你是不是搞错了?不应该叫 Class吗?

老头:哈哈!我刚才说了,大多数人见不到,你就是其中之一啊!你们平时见到的 Class只是对 Klass的一种封装而已,真正记录模板中的具体元信息的就是 Klass。这回要记住了,年轻人。

3.2 工人

小强: 为什么你的工人是等量差的身高呢?
obj-data.png

老头:你的观察还是挺仔细的嘛!是的,他们确实是等量差的,想要知道为什么,要先了解这些工人有哪些部分组成。
obj-length.png

它们头部大小是固定的,身体大小是由自己的属性数据决定的,而最后的脚部却是我来决定的,如果前面两个数据的大小没有达到 8 的倍数,那么我就会来填充,所以就是这里的填充使得他们拥有了等量的身高差(内存对齐)。

我是基于两点原因来这个缔造他们的:

  1. 平台原因:不是所有的硬件平台都能访问任意地址上的任意数据的;某些硬件平台只能在某些地址处取某些特定类型的数据,否则抛出硬件异常。
  2. 性能原因:中央大脑(CPU)访问内存是有内存访问粒度的,就是每次访问内存的长度是固定的,如果不这样做,那么中央大脑起需要访问两次内存,而对齐后只需要一次。

小强:嗯,明白了!那能给我说说这些工人在居住区为什么要不断的搬迁呢?

3.3 成长

老头:经过长时间的观察,我发现每个工人的生命长短是不一样的。所以我把居住区分为新生代,老年代,然后让他们合理的搬迁,这样能有效的利用空间而且让垃圾小分队工作更有效率。
堆区分代
工人诞生后会分配到Eden区,当Eden区人员快满时,垃圾小分队会来清扫,清扫后如果工人还活着,那么他们将搬迁至Survivor区中的其中一个,当这个Survivor快满时,垃圾小分队会将还活着的工人搬迁至另一个Survivor区中,就这样重复着,每经历一次垃圾小分队的清扫,活着的工人就会长大一岁,直到工人的年龄达到15岁,到达后会将他们搬迁至老年代生活的地方。但也有例外,如果某个工人吃的太胖,新生代容不下他,那么他将直接去老年代住下。当老年代快住满时,将会有垃圾大扫除(full gc)。

小强:原来如此啊!从此我再也不是只知道堆区栈区的菜鸟啦!哈哈哈哈……

老头:小伙子,不要高兴太早!你到目前为止所了解的仍是九牛一毛。

3.4 死亡证明

小强:如何确定工人是否到达生命的尽头呢?

第一种:引用计数法

给每个工人添加一个引用计数器,就是只要有人需要这个工人帮忙,那么就给这个工人的计数加1,反之,别人不再需要这个工人的帮忙,那么计数就减1,直到这个计数为0,那么表示这个工人生命到了尽头。

但这种方法有个问题:如果A工人和B工人相互需要帮忙,但没有任何其他工人或任务需要他们两个,那么他们两个会永远活下!所以这种方法我们不会采取的。

第二种:可达性分析法

我们找出被称为 “GC roots”的工人作为起点,依次寻找他们工作中依赖的工人,这就可以知道哪些工人是没有必要在存在下去了。

小强:我怎么知道哪些是 “GC roots”工人呢?

老头:

  1. 工作区(栈)中的需要用到的工人
  2. 仓库(方法区)中模板(类)本身需要的工人(静态,常量)
  3. 世界后方(native方法)需要的工人

小强:Got it!

4. 回收

老头:下面我带你去认识一下垃圾小分队的人物吧!不过在认识他们之前你最好了解一下,垃圾清除的基本方法论。

4.1 基本方法论

收集垃圾遵循的基本方法论有以下几种:

  • 标记-清除

    首先标记出所有需要回收的工人(对象),在标记完成后统一回收所有被标记的工人。

    但这个有两个缺点:1. 效率不高 2. 会产生许多碎片空间

  • 复制

    将可用的空间一分为二,每次只使用其中一块,当快使用完时,小分队回收,然后将活着的工人搬迁至另一块。

    这虽然解决了标记-清除的效率问题,但此种方法却缩小了一半空间。

  • 标记-整理

    首先标记出所有需要回收的工人(对象),然后将存活的工人移动到空间的一端,然后清理掉边界以外的工人。

小强笑了笑:原来是这三种算法啊!我知道!

老头:既然知道,那跟我来认识一下垃圾清扫队的人吧!

4.2 主要成员

垃圾清扫队有好几个小队组成,客户喜欢哪个小队可以指定让谁来工作,他们各个队伍的清扫方式各不相同也各有优劣。

我给你介绍一下两个主要成员吧,CMS,G1两个小队出列。

CMS:到,我们是CMS分队,全称叫 “Concurrent Mark Sweep”,顾名思义,我们是采用标记清除算法的并发小分队,我们以获取最短回收停顿时间为目标。

小强:那你说说你们是如何工作的?

CMS:我们主要分四个步骤工作,1. 初始标记 2.并发标记 3.重新标记 4.并发清除

小强:算啦,这么多步骤太需要时间来了解了,我现在知道你的优点了,那你的缺点有什么呢?

CMS:这怎么还带揭人伤疤的……

老头这时严肃的咳嗽了两声,其意CMS立马捕获到了,委屈的说:

我有三个缺点:

  1. 当资源不是很充足时,占用过多的资源,导致任务变慢
  2. 无法处理浮动垃圾,我们清理的时候,工人同时也在工作,我们标记后,正好有些工人不在需要了
  3. 我们分队遵循的是“标记-清除”算法,所以会产生大量碎片空间,导致世界大扫除(full gc)提前到来

心直口快的小强来了句:原来你的问题这么严重,老头竟然没把你们小分队辞掉……

CMS:你…… 想当年我们分队可是红极一时的……

那么我猜G1是不是可以弥补CMS的不足呢?

G1: 说实话,我们分队的目标就是替换CMS分队…… (JDK14 CMS正式落下帷幕)

小强不怀好意的笑了起来,哈哈……,CMS翻着白眼躲到一旁的角落暗自伤感去了。

角落哭.jpeg

小强:那G1说说你的能耐吧!

G1: 我们队是基于标记整理算法的,因此不会产生大量碎片空间

  • 我们同时引入了分区的思路,弱化了分代的概念
  • 我们的停顿时间是可控的,可避免雪崩现象
  • 我们也能充分利用客户给我们的资源,减少停顿时间

这是我们队的优势,接下来我给你详细介绍下我们队的情况……

小强:好的!你继续……

回归

就在小强听的兴趣浓浓时,天空中突然出现一只巨大无比的手向他袭来,小强躲闪不开,啊……

巴掌.png

小强捂着自己的头,有点恍惚,抬头一看,擦,技术总监……你怎么也在这?

总监:我不在这我在哪?在家睡大觉吗!

这时小强才回过神来,原来自己还在办公室,大事不妙啊!

总监:小强,回家多爽,明天就不用来了吧!

小强一慌,脑袋灵机一动:总监,知道我刚才在做什么吗?那可不是在睡觉,我有一个故事你且听听再做决定。

吧啦吧啦……

最后我将本文知识总结成了思维导图:
思维导图

说明:

  1. 【作者】:flyhero
  2. 【公众号】:码上实战。
  3. 【简介】:想做个拥有理论的实战派。
  4. 【福利】:关注微信公众号,回复:“JVM” 获取思维导图
  5. 【转载】:转载请说明出处,谢谢合作!
查看原文

赞 3 收藏 2 评论 0

飞哥王某 关注了专栏 · 2020-03-25

HYN的技术笔记

聚焦Java技术栈,前端亦有所涉猎,这儿可全是干货!

关注 429

飞哥王某 发布了文章 · 2020-03-18

集合去重三境界

原文:集合去重三境界

王国维在《人间词话》中说过治学三重境界,想要成大事者会经历三个阶段,而数组去重几个方式也显示出了我们所经历的三个阶段,你在哪个阶段呢?

给定最简单的整型集合

List list = new ArrayList<>(Arrays.asList(2,4,6,7,8,2,4,8));

第一重境界

"昨夜西风凋碧树,独上高楼,望尽天涯路。"

初入猿门,人生目标尚属迷茫,不知前路几何。

这个阶段你应该能想到的就是 使用一个新的List,将原来的内容存入其中,如果存在了就跳过,这样最后新的List中就没有重复的元素了。

List newList = new ArrayList<>();
for(int i=0; i<list.size(); i++){
    if (!newList.contains(list.get(i))){
        newList.add(list.get(i));
    }
}

此种方法的时间复杂度为 O(n^2) , 时间随着集合长度的增加而指数增加。

第二重境界

"衣带渐宽终不悔,为伊消得人憔悴。"

此刻你应该有了追逐的目标,coding虽虐你千百遍,但你仍不悔不弃。

当你学习了更多集合框架,你会发现一个Set接口,它的实现类要求包含的元素不能重复。

Set set = new HashSet(list);
List integers = new ArrayList<Integer>(set);

此种方法的时间复杂度为 O(n) , 时间随着集合长度的增加而线性增加。

第三重境界

"众里寻他千百度,蓦然回首,那人却在,灯火阑珊处。"

历经千百次的磨炼寻觅,突然柳暗花明,这就是升华。

如果你再进一步学习,对JDK8有些了解,那么你一定知道stream,它常用于对集合的操作,提供了非常丰富的API。

list.parallelStream()
   .distinct()
   .collect(Collectors.toList());

此种方式是比较流行的方式,时间复杂度我也不知怎么算了(手动捂脸),但利用lambda表达式书写起来行云流水,让人直叫爽。

image

但它的效率如何呢?

这个要了解一下stream的实现方式了,它底层使用了JDK7提供的forkjoin框架来完成,这个框架能够充分利用计算机的多核。
在多核心的计算机且数据量较大的情况下,效率相对for循环要好很多,但仍然赶不上set方式;
在数据量较小的情况下,stream相对于前面两种方式较差。

所以stream的方式和set来转换方式,可以根据你的要求和喜好来选择

查看原文

赞 0 收藏 0 评论 0

飞哥王某 发布了文章 · 2019-11-14

好消息!GitHub 官方发布APP了!

原文: 重大消息!GitHub 官方发布APP了!

这个消息对于GitHub用户可谓太好了,GitHub终于迎来了官方版本的 App .

GitHub for mobile (beta)

无论您身在何处,移动版GitHub均可让您灵活地推进工作并与团队保持联系。在GitHub上,您可以做很多事情,不需要复杂的开发环境,例如共享有关设计讨论的反馈并查看几行代码。现在,无论您在哪里工作,我们都能为您提供出色的本地体验,使您轻松执行这些任务。

查看代码并从任何地方合并更改。

合并

作为本地应用程序,移动版GitHub甚至可以根据您的设备偏好在暗模式下自动适应各种屏幕尺寸。

主题

面向移动设备的GitHub现在可以在iOS版Beta中使用-即将在Android版中推出。

使用iOS的小伙伴快去体验一把吧,让我等Android用户羡慕一把。

查看原文

赞 0 收藏 0 评论 0

飞哥王某 发布了文章 · 2019-11-07

面对数据库死锁差点跪

阅读原文:面对数据库死锁差点跪

21312312.png
数据库死锁这个问题不知道你有没有遇到过呢?一旦遇到该如何排查问题呢?

环境: MySQL 5.7.25 引擎 InnoDB

如果你的系统日志突然报这种错误,就问你慌不慌?心想:MD,之前遇到过,但完全不记得该怎么办了!!!完了完了!被领导知道我解决不了这个问题,不会被开除吧!

2019-10-23 13:07:17.144 ERROR nested exception is org.springframework.dao.DeadlockLoserDataAccessException: 
### Error updating database.  Cause: com.mysql.cj.jdbc.exceptions.MySQLTransactionRollbackException: Deadlock found when trying to get lock; try restarting transaction
### The error may involve com.x.x.mapper.XMapper.update-Inline
### The error occurred while setting parameters
### SQL: UPDATE tb_a SET start_time = ?, end_time = ? WHERE  id = ?
### Cause: com.mysql.cj.jdbc.exceptions.MySQLTransactionRollbackException: Deadlock found when trying to get lock; try restarting transaction
com.mysql.cj.jdbc.exceptions.MySQLTransactionRollbackException: Deadlock found when trying to get lock; try restarting transaction

想我一个堂堂工作几年的开发者,挂在这个地方,那岂不是很没面子啊!操练起来。

什么是死锁?

当多个进程访问同一数据库时,其中每个进程拥有的其他进程所需的,由此造成每个进程都无法继续下去。 简单的说,进程A等待进程B释放他的资源,B又等待A释放他的资源,这样就互相等待就形成死锁

查看数据库基本信息

查看数据库版本:select version();

事务隔离级别查询方法:select @@tx_isolation

通过命令show engines查看一下InnoDB的特点

20191107123525.jpg

InnoDB支持事务,行级锁及外键。

我们平时遇到的就是多个事务之间行级锁导致的。

分析

业务日志中的记录太过简单,只知道哪个方法的事务发生了死锁,没有多余的信息,所以我们要到数据库中寻找更多的有用信息,通过命令 show engine Innodb status 查看:

------------------------
LATEST DETECTED DEADLOCK
------------------------
2019-10-23 16:46:42 0x7fa919415700
# 事务1
*** (1) TRANSACTION:
TRANSACTION 21010939, ACTIVE 1 sec starting index read
mysql tables in use 1, locked 1
LOCK WAIT 4 lock struct(s), heap size 1136, 2 row lock(s), undo log entries 1
MySQL thread id 255825, OS thread handle 140363604055808, query id 179915249 localhost 127.0.0.1 root updating
UPDATE tb_b SET end_time = 1571821300000 WHERE id = 18199
# 等待b表的X锁
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 1924 page no 284 n bits 80 index PRIMARY of table `dmeeting`.`tb_b` trx id 21010939 lock_mode X locks rec but not gap waiting
Record lock, heap no 9 PHYSICAL RECORD: n_fields 26; compact format; info bits 0

# 事务2
*** (2) TRANSACTION:
TRANSACTION 21010938, ACTIVE 1 sec starting index read
mysql tables in use 1, locked 1
4 lock struct(s), heap size 1136, 2 row lock(s), undo log entries 1
MySQL thread id 255826, OS thread handle 140364249913088, query id 179915304 localhost 127.0.0.1 root updating
UPDATE tb_a SET  actual_start_time = 1571820362678, actual_end_time = null WHERE id = 14266
# 持有b表的X锁
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 1924 page no 284 n bits 80 index PRIMARY of table `dmeeting`.`tb_b` trx id 21010938 lock_mode X locks rec but not gap
Record lock, heap no 9 PHYSICAL RECORD: n_fields 26; compact format; info bits 0
# 等待a表的X锁
*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 1934 page no 324 n bits 112 index PRIMARY of table `dmeeting`.`tb_a` trx id 21010938 lock_mode X locks rec but not gap waiting
Record lock, heap no 45 PHYSICAL RECORD: n_fields 38; compact format; info bits 0
# 回滚事务2
*** WE ROLL BACK TRANSACTION (2)

分析上面的死锁日志,能够得出以下死锁场景:

20191107123508.jpg

仅仅根据死锁日志分析,我是百思不得其解,在事务1中并没有显示持有a表的X锁,那么这是怎么造成死锁的呢!我就是个愣头青,就知道面对死锁日志想来想去,浪费了时间,幸得身旁有大神指点,去看看业务系统中这两个事务代码,才发现原来事务1中在时间序列2时对a表进行了更新操作,已经持有了a表的行级锁!这下就完全明白了,两个事务互相等待对方释放锁,这就是造成死锁的原因。

死锁原因.png

原因知道了,那就通过更改代码,让两个事务里表更新的顺序一致即可。

总结排查步骤

  1. 通过业务系统日志快速定位到发生死锁的代码块
  2. 查看InnoDB的死锁日志,找出各个事务对应的代码块
  3. 通过死锁日志和业务代码推测画出死锁的事务发生场景

降低发生死锁的概率

  1. 避免大事务,可以拆分成多个小事务,因为大事务耗时长,与其他事务发生的概率就大。
  2. 多个事务操作相同的一些资源,尽量保持顺序一致。
  3. 更新语句尽量只更新必要的字段,内容相同的字段不要更新。

记录完整的死锁日志

show engine innodb status 时,显示的信息不全。

这是mysql客户端的一个bug:BUG#19825,交互式客户端限制了输出信息最大为 64KB,因此更多的信息无法显示。

但我们可以通过开启锁监控来查看完整的日志,方式如下:

# 建议排查问题后关闭,15秒输出一次,会导致日志越来越大
-- 开启标准监控 开ON/关OFF
set GLOBAL innodb_status_output=ON;
 
-- 开启锁监控  开ON/关OFF
set GLOBAL innodb_status_output_locks=ON;

也可以通过一个专门用于记录死锁日志的参数:

set GLOBAL innodb_print_all_deadlocks=ON;

内容一般输出到 mysql error log 里,查看日志位置:select @@log_error

锁的种类

锁级别

行级锁(引擎INNODB):开销大,加锁慢;会出现死锁;锁定粒度最小,发生锁冲突的概率最低,并发度也最高。

表级锁(引擎MyISAM):开销小,加锁快;不会出现死锁;锁定粒度大,发生锁冲突的概率最高,并发度最低。

锁类型

next KeyLocks锁,同时锁住记录(数据),并且锁住记录前面的Gap

Gap锁,不锁记录,仅仅记录前面的Gap

Recordlock锁(锁数据,不锁Gap)

所以其实 Next-KeyLocks=Gap锁+ Recordlock锁

锁模式

首先我们要知道两种最容易理解的锁模式,读加共享锁,写加排它锁。

  • LOCK_S(读锁,共享锁)
  • LOCK_X(写锁,排它锁)

还有:

  • LOCK_IS(读意向锁)
  • LOCK_IX(写意向锁)
  • LOCK_AUTO_INC (自增锁)
更加详细的介绍可以去看看这篇文章:https://www.aneasystone.com/a...

http://www.throwable.club/2019/05/11/mysql-deadlock-troubleshoot-1st/#%E5%AF%BC%E8%87%B4%E6%AD%BB%E9%94%81%E7%9A%84%E5%8E%9F%E5%9B%A0

查看原文

赞 2 收藏 2 评论 2

飞哥王某 发布了文章 · 2019-10-29

为什么数组下标总是从 0 开始呢?

原文地址: 为什么数组下总是从 0 开始呢?

image

这个问题有没有想过?会不会认为为何设计的如此反人类呢?

有两种比较好的说法,我们了解下:

说法一

表示范围的最佳形式,比如表示自然数序列 2,3,···,12,有四种方法:

a. 2 ≤ i < 13 ,或者记作 [2, 13)

b. 1 < i ≤ 12 ,或者记作 (1, 12]

c. 2 ≤ i ≤ 12 ,或者记作 [2, 12]

d. 1 < i < 13 ,或者记作 (1, 13)

a 方法是最好的,有如下原因:

  1. 范围的上限减去下限等于范围内元素的个数

比如方法 a 中,13 - 2 = 11,而范围内刚好就有 11 个元素,方法也有同样的性质,但方法 c 和 d 就没有。

  1. 连续的范围没有重叠

两个连续的范围我们希望可以写成 “0 到 5” 和“5 到 9”这样的形式。如果使用方法 c,12 就同时包含在 [2, 12] 和 [12, 24] 这两个范围里;类似的,使用方法 d,13 既不包含在 (2, 13) 里也不在 (13, 25) 里。用方法 a,b 就没有这样的问题。比如 [2, 13) 和 [13, 25) 是两个连续的范围,13 只会包含在后一个里。

方法 a 比方法 b 好的理由:我们常常会用到有下限无上限的集合,最典型的是自然数集合。比如要表示自然数集合内的范围 “0 到 10”, 用方法 a 可以写成 [0, 11) , 用方法 2 可以写成 (-1, 10] 。方法 b 的问题是形式中出现了 - 1 这个非自然数, 用非自然数来表示一个自然数集合内的范围显然不是一个好的选择。

说法二

我们常说的数组下标最精确的意思是”偏移量 “,a[0] 的偏移量是 0,即为首地址。a[i]的偏移量是 i,寻址公式:

a[i]地址 = 首地址 + i * 数据大小

如果下标从 1 开始,那对应的寻址公式

a[i]地址 = 首地址 + (i-1) * 数据大小

image

对 CPU 来说,每次随机访问,就多了一次减法运算,多发一条指令,所以从 0 开始可以减少 CPU 的计算。

想了解很多,请关注下面:
image

查看原文

赞 0 收藏 0 评论 0

飞哥王某 发布了文章 · 2019-10-21

这种方式更优雅,秒表计时

阅读原文: 这种方式更优雅,秒表计时!

秒表计时

你有看过学校百米赛跑时,体育老师手里的秒表吗?老师是怎么记八个跑道中的学生跑了多少时间的呢?

今天我们要做的就是实现老师手中的秒表,但是我们计算机无法真正同时跑n个任务,我们只能一个跑完跑下一个。

许多人统计用时会向下面这样,但方式并不优雅!现在我们来一起实现一个秒表让统计更加优雅吧。

public class Test{

    public static void main(String[] args) {
       long s =  System.currentTimeMillis();
       // 算法1
       // do something
       long s1 = System.currentTimeMillis() - s;
       System.out.println("第一段代码执行时间:"+s1);
       // 算法2
       // do something
       long s2 = System.currentTimeMillis() - s1;
       System.out.println("第二段代码执行时间:"+s2);
    }
}

看完这段代码就问你,烦不烦?

问题所在

那么我们烦在哪里?

  1. 每次都要获取获取时间代码
  2. 每次都要主动打印
  3. 无关紧要的计时打印代码占据了视线
  4. 如果n段代码统计对比,需要人工对比或硬编码对比

好了,问题知道了,来想想解决方案吧。

解决方案

  1. 封装一个方法代替每次时间相减的代替
  2. 将打印最后统一输出
  3. 统计每段用时,排序或对比

开始实现我们的秒表类 StopWatch 吧

  • 每段计时任务要有一个唯一标识和一个最终用时
  • 需要一个容器来存储每个计时任务
  • 需要记录总时长和任务数量

具体实现

  • 每个计时任务类
public class Task {
        private String name;
        private long timeMillis;

        public Task(String name, long timeMillis) {
            this.name = name;
            this.timeMillis = timeMillis;
        }
}
  • 秒表类
public class StopWatch {
    /*
     * 存储执行或的任务容器
     */
    private List<Task> tasks = new ArrayList<>();  
    /*
     * 当前执行的任务
     */
    private String currentName; 
    /*
     * 当前任务的开始时间
     */
    private long startMillis;   
    /*
     * 总用时
     */
    private long totalMillis;  

    public StopWatch() {
    }
    /**
     * 开始任务
     * @param taskName 任务名
     */
    public void start(String taskName) {
        if (currentName != null){
            stop();
        }
        this.currentName = taskName;
        this.startMillis = System.currentTimeMillis();
    }
    /**
     * 停止任务
     */
    public void stop() {
        if (null == currentName) {
            throw new RuntimeException("");
        }
        long spend = System.currentTimeMillis() - startMillis;
        totalMillis += spend;
        Task task = new Task(currentName, spend);
        tasks.add(task);
    }

    public int size() {
        return tasks.size();
    }

    /**
     * 打印结果
     */
    public void print() {
        if (currentName != null){
            stop();
        }
        StringBuilder s = new StringBuilder();
        s.append("任务名称\t用时\t占比\t\n");
        for (Task task : tasks) {
            s.append(task.getName() + "\t");
            s.append(task.getTimeMillis() + "\t");
            double l = task.getTimeMillis() / (double)totalMillis;
            s.append(String.format("%.2f",l)  + "\t\n");
        }
        s.append("总用时:" + totalMillis);
        System.out.println(s.toString());
    }
}
  • 那么看看现在如何做
public class Test {

    public static void main(String[] args){
        StopWatch stopWatch = new StopWatch();

        stopWatch.start("任务1");
        TimeUnit.SECONDS.sleep(1);

        stopWatch.start("任务2");
        TimeUnit.SECONDS.sleep(2);

        stopWatch.print();
    }
}

此时我漏出了满意的笑容![表情]

最后告诉你个消息: Apache commons , Spring core , Google guava 都给我们实现了稍有不同的StopWatch类!

如果你跟随我一块实现了StopWatch,那去看看这三个提供的,应该 so easy!

查看原文

赞 0 收藏 0 评论 0

飞哥王某 收藏了文章 · 2019-10-09

面试官问你B树和B+树,就把这篇文章丢给他

原文链接:面试官问你B树和B+树,就把这篇文章丢给他

在看这篇文章之前,我们回顾一下前面的几篇关于MySQL的文章,应该对你读下面的文章有所帮助。

1 B树

在介绍B+树之前, 先简单的介绍一下B树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。

1.1 B树概念

B树也称B-树,它是一颗多路平衡查找树。二叉树我想大家都不陌生,其实,B树和后面讲到的B+树也是从最简单的二叉树变换而来的,并没有什么神秘的地方,下面我们来看看B树的定义。

  • 每个节点最多有m-1个关键字(可以存有的键值对)。
  • 根节点最少可以只有1个关键字
  • 非根节点至少有m/2个关键字
  • 每个节点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键字都大于它。
  • 所有叶子节点都位于同一层,或者说根节点到每个叶子节点的长度都相同。
  • 每个节点都存有索引和数据,也就是对应的key和value。

所以,根节点的关键字数量范围:1 <= k <= m-1,非根节点的关键字数量范围:m/2 <= k <= m-1

另外,我们需要注意一个概念,描述一颗B树时需要指定它的阶数,阶数表示了一个节点最多有多少个孩子节点,一般用字母m表示阶数。

我们再举个例子来说明一下上面的概念,比如这里有一个5阶的B树,根节点数量范围:1 <= k <= 4,非根节点数量范围:2 <= k <= 4。

下面,我们通过一个插入的例子,讲解一下B树的插入过程,接着,再讲解一下删除关键字的过程。

1.2 B树插入

插入的时候,我们需要记住一个规则:判断当前结点key的个数是否小于等于m-1,如果满足,直接插入即可,如果不满足,将节点的中间的key将这个节点分为左右两部分,中间的节点放到父节点中即可。

例子:在5阶B树中,结点最多有4个key,最少有2个key(注意:下面的节点统一用一个节点表示key和value)。

  • 插入18,70,50,40

  • 插入22

插入22时,发现这个节点的关键字已经大于4了,所以需要进行分裂,分裂的规则在上面已经讲了,分裂之后,如下。

  • 接着插入23,25,39

分裂,得到下面的。

更过的插入的过程就不多介绍了,相信有这个例子你已经知道怎么进行插入操作了。

1.3 B树的删除操作

B树的删除操作相对于插入操作是相对复杂一些的,但是,你知道记住几种情况,一样可以很轻松的掌握的。

  • 现在有一个初始状态是下面这样的B树,然后进行删除操作。

  • 删除15,这种情况是删除叶子节点的元素,如果删除之后,节点数还是大于m/2,这种情况只要直接删除即可。

  • 接着,我们把22删除,这种情况的规则:22是非叶子节点,对于非叶子节点的删除,我们需要用后继key(元素)覆盖要删除的key,然后在后继key所在的子支中删除该后继key。对于删除22,需要将后继元素24移到被删除的22所在的节点。

此时发现26所在的节点只有一个元素,小于2个(m/2),这个节点不符合要求,这时候的规则(向兄弟节点借元素):如果删除叶子节点,如果删除元素后元素个数少于(m/2),并且它的兄弟节点的元素大于(m/2),也就是说兄弟节点的元素比最少值m/2还多,将先将父节点的元素移到该节点,然后将兄弟节点的元素再移动到父节点。这样就满足要求了。

我们看看操作过程就更加明白了。

  • 接着删除28,删除叶子节点,删除后不满足要求,所以,我们需要考虑向兄弟节点借元素,但是,兄弟节点也没有多的节点(2个),借不了,怎么办呢?如果遇到这种情况,首先,还是将先将父节点的元素移到该节点,然后,将当前节点及它的兄弟节点中的key合并,形成一个新的节点

移动之后,跟兄弟节点合并。

删除就只有上面的几种情况,根据不同的情况进行删除即可。

上面的这些介绍,相信对于B树已经有一定的了解了,接下来的一部分,我们接着讲解B+树,我相信加上B+树的对比,就更加清晰明了了。

2 B+树

2.1 B+树概述

B+树其实和B树是非常相似的,我们首先看看相同点

  • 根节点至少一个元素
  • 非根节点元素范围:m/2 <= k <= m-1

不同点

  • B+树有两种类型的节点:内部结点(也称索引结点)和叶子结点。内部节点就是非叶子节点,内部节点不存储数据,只存储索引,数据都存储在叶子节点。
  • 内部结点中的key都按照从小到大的顺序排列,对于内部结点中的一个key,左树中的所有key都小于它,右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
  • 每个叶子结点都存有相邻叶子结点的指针,叶子结点本身依关键字的大小自小而大顺序链接。
  • 父节点存有右孩子的第一个元素的索引。

下面我们看一个B+树的例子,感受感受它吧!

2.2 插入操作

对于插入操作很简单,只需要记住一个技巧即可:当节点元素数量大于m-1的时候,按中间元素分裂成左右两部分,中间元素分裂到父节点当做索引存储,但是,本身中间元素还是分裂右边这一部分的

下面以一颗5阶B+树的插入过程为例,5阶B+树的节点最少2个元素,最多4个元素。

  • 插入5,10,15,20

  • 插入25,此时元素数量大于4个了,分裂

  • 接着插入26,30,继续分裂

有了这几个例子,相信插入操作没什么问题了,下面接着看看删除操作。

2.3 删除操作

对于删除操作是比B树简单一些的,因为叶子节点有指针的存在,向兄弟节点借元素时,不需要通过父节点了,而是可以直接通过兄弟节移动即可(前提是兄弟节点的元素大于m/2),然后更新父节点的索引;如果兄弟节点的元素不大于m/2(兄弟节点也没有多余的元素),则将当前节点和兄弟节点合并,并且删除父节点中的key,下面我们看看具体的实例。

  • 初始状态

  • 删除10,删除后,不满足要求,发现左边兄弟节点有多余的元素,所以去借元素,最后,修改父节点索引

  • 删除元素5,发现不满足要求,并且发现左右兄弟节点都没有多余的元素,所以,可以选择和兄弟节点合并,最后修改父节点索引

  • 发现父节点索引也不满足条件,所以,需要做跟上面一步一样的操作

这样,B+树的删除操作也就完成了,是不是看完之后,觉得非常简单!

3 B树和B+树总结

B+树相对于B树有一些自己的优势,可以归结为下面几点。

  • 单一节点存储的元素更多,使得查询的IO次数更少,所以也就使得它更适合做为数据库MySQL的底层数据结构了。
  • 所有的查询都要查找到叶子节点,查询性能是稳定的,而B树,每个节点都可以查找到数据,所以不稳定。
  • 所有的叶子节点形成了一个有序链表,更加便于查找。
1、原创不易,老铁,文章需要你的 点赞 让更多的人看到,希望能够帮助到大家!

2、文章有不当之处,欢迎指正,如果喜欢微信阅读,你也可以关注我的微信公众号好好学java,公众号已有 6W 粉丝,回复:1024,获取公众号的大礼包,公众号长期发布 Java 优质系列文章,关注我们一定会让你收获很多!

查看原文

飞哥王某 发布了文章 · 2019-07-28

抽象类和接口的区别已经变了

原文:抽象类和接口的区别已经变了

随着JDK的不断迭代,抽象类和接口的区别已经有了些许改变,你是否还停留在JDK 7 的答案呢?

定义

  • 抽象类定义通过 abstract class
public abstract class A {}
  • 接口定义通过 abstract(默认) interface
public abstract interface A {}

派生方式

  • 子类继承抽象类通过 extends , 单继承
public abstract class A {}
public class B extends A {}
  • 抽象类实现接口通过 implements , 多实现,接口继承接口通过 extends
public interface A {}
public interface B {}

public interface C extends A {}

public class D implements B,C {}
  • 子类(非抽象类)必须实现 抽象父类或接口 的全部未实现方法

实例化

  • 抽象类和接口均不能实例化
  • 抽象类可以有构造方法,接口不能有构造方法
public abstract class A {
  public A () {}
}

属性

  • 接口中定义属性只能是 (public)静态常量
public interface A {
  //默认(public static final) String A="ABC";
  String A = "ABC";
}
  • 抽象类中可以定义有任意变量常量
//任意访问修饰符的变量及常量
public abstract class A {
    private String a = "a";
    boolean b = true;
    public char c = 'a';
    protected int d = 2;
    public static final int e = 1;
}

方法

抽象类

抽象类中可以和普通类中一样拥有各自普通方法,也可以拥有(不必须)抽象方法。

  • 抽象方法没有方法体
  • 抽象方法权限修饰符不能为 pirvate
public abstract class A {

  // protected or default
    public abstract void a();
}
抽象方法的目的就是为了让子类继承重写的,所以抽象方法不能私有,不能final修饰。

接口

JDK 7

  • 只能有方法的声明
  • 方法必须声明为 public (默认)
public interface A {
  //默认(public abstract) void test();
    void test();
}

JDK 8

  • 增加默认实现方法
public interface A {
  // 这里的 default 不能省略
  public(默认自动添加) default void defaultMethod(){
    //do something
  } 
}
默认方法的出现主要是面向类库的开发者的,在堆接口进行扩展时,大量的实现类会让人望而却步。拥有默认方法后,子类可直接继承使用或重写。另外,添加默认方法不会影响函数式接口的使用。
  • 增加静态方法
public interface A {
  // 静态方法
  public(默认自动添加) static void staticMethod(){
    //do something
  }
}
静态方法的调用直接通过接口名调用A.staticMethod() ,子类无法重写(override), 但可以有同名方法。

JDK 9

  • 增加私有方法
public interface A {
  // 不能被子类继承或重写
  private void privateMethod(){
    //do something
  } 
}
  • 增加私有静态方法
public interface A {
  // 不能被子类继承或重写
  private static void privateStaticMethod(){
    //do something
  } 
}
这两种私有方法其实是对JDK8 默认方法和静态方法 的补充,这样可以避免代码的冗余。

设计

  1. 抽象类是对一组类的共同特征进行抽象 ,是子类的模板(is-a)
  2. 接口是对行为的抽象,是一种行为的规范和约束 (like-a)

往期文章一览

千万不要这样使用 Arrays.asList !

八张图带你认识Java

Java开发必备手册

关注微信公众号 「码上实战」 回复 :面试视频 和 架构师 送你非常不错的资料!

查看原文

赞 0 收藏 0 评论 0

飞哥王某 发布了文章 · 2019-06-05

千万不要这样使用 Arrays.asList !

使用Arrays.asList()的原因无非是想将数组或一些元素转为集合,而你得到的集合并不一定是你想要的那个集合。

而一开始asList()的设计时用于打印数组而设计的,但jdk1.5开始,有了另一个比较更方便的打印函数Arrays.toString(),于是打印不再使用asList(),而asList()恰巧可用于将数组转为集合。

错误用法

如果你这样使用过,那你要注意下了。

  • 错误一

将基本类型数组作为asList的参数

int[] arr = {1,2,3};
List list = Arrays.asList(arr);
System.out.println(list.size());

猜一下输出结果?

  • 错误二

将数组作为asList参数后,修改数组或List

String[] arr = {"欢迎","关注","Java"};
List list = Arrays.asList(arr);
    
arr[1] = "爱上";
list.set(2,"我");
    
System.out.println(Arrays.toString(arr));
System.out.println(list.toString());

猜一下输出结果?

  • 错误三

数组转换为集合后,进行增删元素

String[] arr = {"欢迎","关注","Java"};
List list = Arrays.asList(arr);
    
list.add("新增");
list.remove("关注");

猜一下输出结果?

你是不是以为上面👆那个list是 java.util.ArrayList ?

答案很确定:NO!
吃惊.jpg

探索真理

我们通过asList()源码可发现,但为了更直观,我们通过IDEA debug来看看结果。

List<String> asList = Arrays.asList("欢迎","关注","码上实战");
ArrayList<String> aList = new ArrayList<>(asList);

debug-list.png

其实它返回的是 java.util.Arrays.ArrayList ,这个家伙是谁呢?

表演.jpg

请看下源码:

public class Arrays {
    
    //省略其他方法
    
    public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
    }
        
    //就是这个家伙             👇
    private static class ArrayList<E> extends AbstractList<E>
            implements RandomAccess, java.io.Serializable{
    
        private final E[] a;
    
        ArrayList(E[] array) {
            a = Objects.requireNonNull(array);
        }
    
        @Override
        public int size() {
            return a.length;
        }
        //省略其他方法
    }
}

但它和ArrayList貌似很像唉!有什么不同吗?

不同之处

Arrays.ArrayList 是工具类 Arrays 的一个内部静态类,它没有完全实现List的方法,而 ArrayList直接实现了List 接口,实现了List所有方法。

list对比.png

  • 长度不同 和 实现的方法不同

    Arrays.ArrayList是一个定长集合,因为它没有重写add,remove方法,所以一旦初始化元素后,集合的size就是不可变的。

  • 参数赋值方式不同

Arrays.ArrayList将外部数组的引用直接通过“=”赋予内部的泛型数组,所以本质指向同一个数组。

ArrayList(E[] array) {
    a = array;
}

ArrayList是将其他集合转为数组后copy到自己内部的数组的。

public ArrayList(Collection<? extends E> c) {
    // toArray 底层使用的是 数组clone 或 System.arraycopy
    elementData = c.toArray();
}

揭晓答案

  • 错误一

    由于Arrays.ArrayList参数为可变长泛型,而基本类型是无法泛型化的,所以它把int[] arr数组当成了一个泛型对象,所以集合中最终只有一个元素arr.

  • 错误二

    由于asList产生的集合元素是直接引用作为参数的数组,所以当外部数组或集合改变时,数组和集合会同步变化,这在平时我们编码时可能产生莫名的问题。

  • 错误三

    由于asList产生的集合并没有重写add,remove等方法,所以它会调用父类AbstractList的方法,而父类的方法中抛出的却是异常信息。

支持基础类型的方式

  • 如果使用Spring
int[]  a = {1,2,3};
List list = CollectionUtils.arrayToList(a);
System.out.println(list);
  • 如果使用Java8
int intArray[] = {1, 2, 3};
List<Integer> iList = Arrays.stream(intArray)
                            .boxed()
                            .collect(Collectors.toList());
System.out.println(iList);

数组转为ArrayList

  • 遍历转换
Integer intArray[] = {1, 2, 3};
ArrayList<Integer> aList = new ArrayList<>();
for (Integer i: intArray){
    aList.add(i);
}

显然这种方式不够优雅!反正我不愿意使用。

  • 使用工具类

    上面方案不够优雅,那么这种相对来说优雅一些。

List<String> list = new ArrayList(); 
Collections.addAll(list, "welcome", "to", "china");
你以为这种还不错?
too young too simple!
addAll()方法的实现就是用的上面遍历的方式。
  • 如果使用Java8

    既可以用于基本类型也可以返回想要的集合。

int intArray[] = {1, 2, 3};
List<Integer> iList = Arrays.stream(intArray)
                            .boxed()
                            .collect(Collectors.toList());
System.out.println(iList);
  • 两个集合类结合

    将Arrays.asList返回的集合作为ArrayList的构造参数

ArrayList arrayList = new ArrayList<>(Arrays.asList("welcome", "to", "china"));

最后

勿以点小而不闻!体现程序素养或许就在这些小地方,不要给自己或别人留坑。

那么这个知识点,你get到了吗?get到了,那来继续关注我。没get到?来来来,咱俩单独聊聊。

往期文章一览

把「策略模式」应用到实际项目中

造个轮子,我学到了什么

技术面试中的软技能

不同时重写equals和hashCode又怎样!

关注微信公众号 「码上实战」 回复 :面试视频 和 架构师 送你非常不错的资料!

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 95 次点赞
  • 获得 2 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 2 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2017-06-05
个人主页被 959 人浏览