SpringBoot2 整合 Sharding JDBC 实现 Mysql 读写分离

想直接要源码的,点这里


简介

Sharding-JDBC 定位为轻量级 Java 框架,在 Java 的 JDBC 层提供的额外服务。 它使用客户端直连数据库,以 jar 包形式提供服务,无需额外部署和依赖,可理解为增强版的 JDBC 驱动,完全兼容 JDBC 和各种 ORM 框架。

  • 适用于任何基于 Java 的 ORM 框架,如:JPA, Hibernate, Mybatis, Spring JDBC Template 或直接使用 JDBC
  • 基于任何第三方的数据库连接池,如:DBCP, C3P0, BoneCP, Druid, HikariCP 等
  • 支持任意实现JDBC规范的数据库。目前支持 MySQL,Oracle,SQLServer 和 PostgreSQL

前言

本例只是简单实现了 Sharding-JDBC 中的读写分离功能,请注意。

所用到的技术栈及版本:

  • SpringBoot 2.0.4
    • Spring Data JPA
    • HikariDataSource
    • Gson 2.8.5
    • lombok 1.16.22
    • mysql-connector-java 5.1.46
  • sharding-jdbc-core 2.0.3

主要部分

配置文件:application.yml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# JPA
spring:
jpa:
show-sql: true
database-platform: org.hibernate.dialect.MySQL5InnoDBDialect
hibernate:
ddl-auto: create

# Server
server:
port: 8888

# Sharding JDBC
sharding:
jdbc:
data-sources:
ds_master:
type: com.zaxxer.hikari.HikariDataSource
driver-class-name: com.mysql.jdbc.Driver
jdbc-url: jdbc:mysql://localhost:3306/master?characterEncoding=utf8&useSSL=false
username: root
password: root
ds_slave:
type: com.zaxxer.hikari.HikariDataSource
driver-class-name: com.mysql.jdbc.Driver
jdbc-url: jdbc:mysql://localhost:3306/slave?characterEncoding=utf8&useSSL=false
username: root
password: root
master-slave-rule:
name: ds_ms
master-data-source-name: ds_master
slave-data-source-names: ds_slave
load-balance-algorithm-type: round-robin

这里用的是 springboot2.0 默认的数据库连接池 HikariDataSource

  • load-balance-algorithm-type
    查询时的负载均衡算法,目前有2种算法,round_robin(轮询)和random(随机)
  • master-data-source-name: 主数据源名称
  • slave-data-source-names: 从数据源名称 多个用逗号隔开

存放数据源数据:ShardingMasterSlaveConfig.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package com.example.shardingjdbc.config;

import java.util.HashMap;
import java.util.Map;

import org.springframework.boot.context.properties.ConfigurationProperties;

import com.zaxxer.hikari.HikariDataSource;

import io.shardingjdbc.core.api.config.MasterSlaveRuleConfiguration;
import lombok.Data;

/**
* 存放数据源
*
* @author ffj
*
*/
@Data
@ConfigurationProperties(prefix = "sharding.jdbc")
public class ShardingMasterSlaveConfig {

private Map<String, HikariDataSource> dataSources = new HashMap<>();

private MasterSlaveRuleConfiguration masterSlaveRule;
}

用了 Lombok 显得简便了些

配置数据源:ShardingDataSourceConfig.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package com.example.shardingjdbc.config;

import java.sql.SQLException;
import java.util.HashMap;
import java.util.Map;

import javax.sql.DataSource;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.autoconfigure.condition.ConditionalOnProperty;
import org.springframework.boot.context.properties.EnableConfigurationProperties;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

import com.zaxxer.hikari.HikariDataSource;

import io.shardingjdbc.core.api.MasterSlaveDataSourceFactory;

/**
* 配置数据源详细信息
*
* @author ffj
*
*/
@Configuration
@EnableConfigurationProperties(ShardingMasterSlaveConfig.class)
@ConditionalOnProperty({ "sharding.jdbc.data-sources.ds_master.jdbc-url",
"sharding.jdbc.master-slave-rule.master-data-source-name" })
public class ShardingDataSourceConfig {

private static final Logger log = LoggerFactory.getLogger(ShardingDataSourceConfig.class);

@Autowired(required = false)
private ShardingMasterSlaveConfig shardingMasterSlaveConfig;

/**
* 配置数据源
*
* @return
* @throws SQLException
*/
@Bean("dataSource")
public DataSource masterSlaveDataSource() throws SQLException {
shardingMasterSlaveConfig.getDataSources().forEach((k, v) -> configDataSource(v));
Map<String, DataSource> dataSourceMap = new HashMap<>();
dataSourceMap.putAll(shardingMasterSlaveConfig.getDataSources());
DataSource dataSource = MasterSlaveDataSourceFactory.createDataSource(dataSourceMap,
shardingMasterSlaveConfig.getMasterSlaveRule(), new HashMap<>());
log.info("masterSlaveDataSource config complete!!");
return dataSource;
}

/**
* 可添加数据源一些配置信息
*
* @param dataSource
*/
private void configDataSource(HikariDataSource dataSource) {
dataSource.setMaximumPoolSize(20);
dataSource.setMinimumIdle(5);
}
}

主要的配置内容就是这些了,接下来我们编写几个方法来测试。

测试

  • 先创建一个实体类

大众测试实体类,我选 UserEntity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package com.example.shardingjdbc.entity;

import java.io.Serializable;

import javax.persistence.Column;
import javax.persistence.Entity;
import javax.persistence.Id;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
* 测试用户类
*
* @author ffj
*
*/
@AllArgsConstructor
@NoArgsConstructor
@Data
@Entity(name = "user")
public class UserEntity implements Serializable {

/**
*
*/
private static final long serialVersionUID = -6171110531081112401L;
@Id
private int id;
@Column(length = 32)
private String name;
@Column(length = 16)
private int age;

}

同样,Lombok 不可少。由于之前 application.ymlddl-auto 设置的是 create,所以每次重启程序都会重新生成空表。

  • 我选择 JPA 的原因就是它作为简单测试最适合不过了

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    package com.example.shardingjdbc.repository;

    import org.springframework.data.jpa.repository.JpaRepository;

    import com.example.shardingjdbc.entity.UserEntity;

    public interface UserRepository extends JpaRepository<UserEntity, Integer> {

    }

    只要继承 JpaRepository 就可以了,我们只需要使用它的基本方法即可。

  • 写个 Controller

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    package com.example.shardingjdbc.controller;

    import java.util.List;

    import javax.annotation.Resource;

    import org.springframework.web.bind.annotation.PostMapping;
    import org.springframework.web.bind.annotation.RestController;

    import com.example.shardingjdbc.entity.UserEntity;
    import com.example.shardingjdbc.service.UserService;
    import com.google.gson.Gson;

    /**
    * 用户测试类
    *
    * @author ffj
    *
    */
    @RestController
    public class UserController {

    @Resource
    private UserService userService;

    @PostMapping("/save")
    public String saveUser() {
    UserEntity user = new UserEntity(1, "张三", 22);
    userService.saveUser(user);
    return "success";
    }

    @PostMapping("/getUser")
    public String getUsers() {
    List<UserEntity> users = userService.getUsers();
    return new Gson().toJson(users);
    }

    }

    Service 就不贴了,就是简单调用。

方便查看测试结果,这里用 Gson 来转化为 Json 输出。

  • 启动程序

从上到下看启动日志:

1
2
3
4
5
2018-12-27 15:16:12.907  INFO 2940 --- [           main] com.zaxxer.hikari.HikariDataSource       : HikariPool-1 - Starting...
2018-12-27 15:16:13.132 INFO 2940 --- [ main] com.zaxxer.hikari.HikariDataSource : HikariPool-1 - Start completed.
2018-12-27 15:16:13.141 INFO 2940 --- [ main] com.zaxxer.hikari.HikariDataSource : HikariPool-2 - Starting...
2018-12-27 15:16:13.147 INFO 2940 --- [ main] com.zaxxer.hikari.HikariDataSource : HikariPool-2 - Start completed.
2018-12-27 15:16:13.148 INFO 2940 --- [ main] c.e.s.config.ShardingDataSourceConfig : masterSlaveDataSource config complete

可以看出有两个数据源,没毛病。

1
2
Hibernate: drop table if exists user
Hibernate: create table user (id integer not null, age integer, name varchar(32), primary key (id)) engine=InnoDB

程序启动 user 表重建,没毛病。

1
2
3
4
5
2018-12-27 15:16:15.198  INFO 2940 --- [           main] o.s.w.s.handler.SimpleUrlHandlerMapping  : Mapped URL path [/**] onto handler of type [class org.springframework.web.servlet.resource.ResourceHttpRequestHandler]
2018-12-27 15:16:15.550 INFO 2940 --- [ main] o.s.j.e.a.AnnotationMBeanExporter : Registering beans for JMX exposure on startup
2018-12-27 15:16:15.587 INFO 2940 --- [ main] o.s.b.w.embedded.tomcat.TomcatWebServer : Tomcat started on port(s): 8888 (http) with context path ''
2018-12-27 15:16:15.591 INFO 2940 --- [ main] c.e.s.ShardingJdbcApplication : Started ShardingJdbcApplication in 5.36 seconds (JVM running for 5.725)
2018-12-27 15:16:15.592 INFO 2940 --- [ main] c.e.s.ShardingJdbcApplication : ----------启动成功----------

端口为配置文件中指定的 8888,启动成功日志打印,也没毛病,成功。

注意:启动程序前别忘了先自行创建数据库!

现在我们在 slave 库中执行以下提供的 sql 文件,或者自行创建对应表(表结构必须一致,可以先建库然后从主库中复制已生成的表),并在其中添加数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
Navicat MySQL Data Transfer

Source Server : localhost
Source Server Version : 50720
Source Host : localhost:3306
Source Database : slave

Target Server Type : MYSQL
Target Server Version : 50720
File Encoding : 65001

Date: 2018-12-27 16:23:00
*/

SET FOREIGN_KEY_CHECKS=0;

-- ----------------------------
-- Table structure for user
-- ----------------------------
DROP TABLE IF EXISTS `user`;
CREATE TABLE `user` (
`id` int(11) NOT NULL,
`age` int(11) DEFAULT NULL,
`name` varchar(32) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

-- ----------------------------
-- Records of user
-- ----------------------------
INSERT INTO `user` VALUES ('2', '23', '李四');

好了,从库中表和数据都有了,进入正题。

  • 测试主库插入数据
    我用的是 Postman :选择 POST 方式,url:localhost:8888/save,点击 Send

    1
    Hibernate: insert into user (age, name, id) values (?, ?, ?) // 打印出这条日志

    返回 success,成功执行。查看主数据库中 user 表数据,确实插入,成功!

  • 测试从库查询数据
    还是 Postman :选择 POST 方式,url:localhost:8888/getUser,点击 Send

    1
    Hibernate: select userentity0_.id as id1_0_, userentity0_.age as age2_0_, userentity0_.name as name3_0_ from user userentity0_ // 打印出这条日志

    返回: [{"id":2,"name":"李四","age":23}],数据正确,成功!

以上就是 SpringBoot2.0 + ShardingJDBC 实现数据库读写分离的全部内容了。

参考博文


你好,依旧

你好,依旧 此篇作为对 2018 的整年回顾

尾巴,走了;你好,依旧。

2018 的尾巴已经来到,也是到了时候该让她的尾巴跟头部围成一个圈圈了。

2018,看过几场电影,吃过几场温馨的饭,睡过几场懒觉,看过几次凌晨的星空。

2018,分过一次手,游过几次怪味的泳,红过几次眼,回过不超五次的家。

2018,我重新拾起了运动,不为别的,只为自己能够多活两年。

2018,我重新调整了饮食,却始终调不过来作息。

2018,我看了好多书,有科幻代表《三体》,有经典散文集《自在独行》,有轻描淡写一生历程的《浮生六记》,也有极具讽刺的《兄弟》等等。当然,专业书籍也不能拉下。我自知是个爱书之人,我爱看书与爱看电影是一回事,都是喜欢故事,喜欢在这些源于生活中而来的作品之间,有所感悟,体会情愫。我想,这与我善于思考,善于总结,有些许相关吧。最近在看《城南旧事》。

今年 3 月,我换了份工作,因此也搬了个新的住处。很幸运,两位室友人很不错,还都是个硕士生,与优秀的人一同来往,谁人不喜欢呢?期间我还买了个方形玻璃缸,作为我那鳄龟的新住处(去年 8 月份买的两只苗子,现在只剩一只,长得倍儿快!有时间我可再另开一篇来专门絮叨絮叨)。后觉着这么个大缸就供着个龟大爷,浪费至极。于是我之后又陆陆续续往里丢过虾(包含着龙虾)、泥鳅,可几日后往往就不见其踪影,只有可怜的残骸在水中无目的晃荡。我不甘心,10 月份左右又进购了一批草金苗,大约五六十只。直到今日,12 月中旬,还剩下 7 只幸运儿,不知是否因为这气温影响了龟爷,还是幸运儿的过人闪躲之处,或是他们惺惺相惜,已成为了朋友?我不得知,我只知三天两头给它喂食鸡肉,应该是饿不着它的吧。话说幸运儿草金们,其中有两三条我甚是得意,身上条纹十分漂亮,尾巴又大又长,要是最终也遭遇不幸,我怕是会难过会后悔吧。可是,住所实在是小,我还能做些什么呢?我喜欢各种宠物,本想养猫养狗,一想处境,我便立刻就会打消这种不实际的念头,这也是我选择养龟的原因吧。

由于换了份工作,该司并非互联网公司,工作强度自然也没有那么大。也正是因为如此,我有了更多的时间能做我自己喜欢做的事情,就比如看书,跑步。独处的日子,看书是最好的项目了。晚上我也有了时间自己随意煮煮蔬菜,煮煮鸡胸,煮煮面条,健康又便宜,因此还与菜场的大爷变得熟知。虽然这种生活长期也不错,但是我是知道的,我是不愿意的。在这段时间里,我有了时间可以巩固基础,有了时间可以学习其他的东西,有了时间可以将之前未完全消化的东西一一吸干。我并没忘给自己充电,虽然也看了不少非专业书籍,但是那也是必要的,那些充实了我的灵魂,渐渐造就了我的气质,每每读完一本书我都有所收获。厚积而薄发,我一直在等待它的到来!

我在以前的随记中写过:时间往往在你回顾的时候,才会觉得过得好快。我也写过:原来我早已习惯了孤独,只是在孤独的岁月之中穿插了一段不那么孤独的时光,使我暂忘孤独。一个人的时候,往往会思考更多。虽说人类是群居动物,但是现在正慢慢走向独居世界,与外界网络相连即可。人们经常会畅想未来,畅想未来会变得多么科幻多么神奇多么智能,无可厚非,因为过去几年我们确实是发展可谓“神速”。但是我在想,过去是因为西方的互联网本就比中国发展要快,所以中国可以借鉴西方来避坑,从而快速发展。而如今,中国互联网已是首屈一指,无从可借鉴,只能我们自己一步一脚印来创新推进。畅想固然是好,人们也都想时代发展越快越好,可是我个人觉得还是不能太过于“妄想”,没必要过于急躁,就怕大家都在畅想美好未来的时候,天突然就塌了。当然,这也是我个人想法,磨刀不误砍柴工,美好生活人人都想,前提还是应脚踏实地。

也是在今年,租了服务器,重新注册了域名,搭建了自己的个人博客,开始了持续的记录总结。简书却是我最近才注册的,不为别的,我只想把一些生活感悟、牢骚,在这记录,也只会记录这些。从今年开始,每月我在自己博客都会写上一篇月结记录,初衷是为了让自己觉得过得不会那么虚空,同样更重要的是为了记录我的岁月。为了这些宝贵资料不丢失,我也做了备份。曾经,年少气盛的我丢失过许多美好记忆的书信,使得现在我都后悔不已,这些都是属于我们独一无二的财富。生活无远虑,只有近忧。不管如何,我们都要学会记录生活,也许也许,终有一日我也会有个幸福的家庭,子孙后辈也会静静坐在身边听一个糟老头子讲述他的过往。

犹记得去年 12 月底与朋友们欢聚苏州,共游园林。今年怕是没有机会了,前几日刚好去杭州出差,两位好友在杭州做事,便约出来一同吃了顿饭。这顿饭,我们吃了半小时,等了却将近两小时。那几日刚好是今年雪下得最大的日子,又正值周末,饭点,想想也难免。吃完后各自回府,下了地铁我本想打车,无奈道路积雪严重,天气恶劣。于是在等了十几分钟出租车后,我撑着小黑伞,踩着雪地,走了两三公里回到了宾馆,小黑伞已早成了小白伞了。距离毕业已过去了一年有余,大家身上也都多了一丝成熟稳重,几日前我还翻了下毕业相册,嗯,变化大倒是不大,就是头发好像都少了一些!

2018,我放慢了工作节奏,给了自己更多的时间去回顾,去务实基础,博观约取,厚积薄发

2018,我同时也加强了锻炼,没有一个好身体将来又怎么能够撑得起一番事业!

2018,是积累的一年,寒冬虽冷,却总有见到明媚一天的啊!

你好,19!


住在对面的居民

住在对面的居民,我想与我这边环境也相似,只是人口数量略有差异。

有段时间,每晚下班我进房间打开房灯,第一件事就是站在窗外静静的看着对面的居民们。因为是老式小区,楼层不高,每栋之间的间隔也不大,看不清对面的模样但至少看得清对面的举动。

住在对面的居民,每户人家做的事皆不相同,作息时间皆不相同,窗外布置也是皆不相同。有时我就呆呆的站在那看,不知为什么,我就是能呆呆的站在那看。

住在对面的居民,能看见内部情况的户数不多,却给我有种人生百态的感觉。我想这也是吸引我的原因,是我在此执笔想要记录的原因吧。

住在对面楼斜上角的住户,是一家三口。看不清他们具体模样,只是知道小孩还小,还不会走路。往往见到他们都是在轮流抱着孩子,哄着睡觉,经常就是一哄一两个小时。当小孩入睡后,夫妻俩才开始走到厨房,不知是洗吃完饭后的碗筷还是才开始动手做饭。

住在夫妻俩下两层的是一位好学之人,对其的了解甚少,因为当我驻窗前“偷窥”时,他八成是坐在桌前,也只有桌前那扇窗没拉窗帘。由于晚上视线昏暗加之一定的观察距离,我只知他是位男性,大多独自一人坐在桌前,看书或是写字,我便看不大清了。纵上观之,好学之人,那是定错不了的了。

住在正对面楼偏上一点的是一个大家庭,观察至今我看到出现过一个老头、一个老太、还有较之年轻的一男一女。因为楼层的原因,我只能看到其窗外晾晒的衣物,无法窥视到内部的情形。只是有时能看到一男的或是女的走过来拉上窗户,拉上窗帘,像似要与外界隔绝,美美地做个美美的梦。有个周末,我坐在床上看着投影中的电影,眼睛往窗外一瞥,霎时汗毛直立。待我定睛瞧时,原来是这户窗外挂了个人形玩偶在那晾晒,好不瘆人。

住在对面稍偏右下的一个小房间里住着一个人,应该是男性。经常看他坐在电脑桌前,毛玻璃的蒙眬使我看不清他在键盘上的手速,但我想,那定是青轴。偶尔起身,那便应该是尿意来袭或是口干舌燥了吧。

再往右数米处有间房间最近一直在粉刷装修,往往十一二点还能见到粉刷匠在吊灯下的身影。背后有个美满的家庭,再多的重担肩上扛着,脸上还是挂着幸福的笑容。

再往上一点有个房间好像是个女性独处,有次晚上偶尔看到其窗帘未拉上,她正趴在床上玩手机,还是毛玻璃蒙眬,也许是男性也说不准。后来我每每往那边瞧时,皆是漆黑一片。恐是精神作祟?好不瘆人。

前些日子降了几场大雪,我去杭州出差那几日正是雪下得最大的时候。出门时撑的是黑伞,没过几分钟便已是白伞了。一夜过后,清晨出门,看着路边单车坐垫上足足有五六公分积雪,已是多少年没下过如此大雪了。犹记得儿时,记忆中的过年都是在厚厚的白雪上渡过。那时我们喜欢玩鞭炮,点火花棒在空中使劲了甩,不像如今,我们老家已经禁炮许多年了。都说现在过年越来越没有年味儿了,不是年味儿它消失了,是我们不知觉中已然长大。

忙碌,如今整日忙碌,却有时又不知到底在忙碌些什么。我们不妨自己找个时间,静静呆会,可以看看月亮看看星星,看看过往的路人,也可以跟我一样看看住在对面的居民。

Life is like a box of chocolate,you never know what you are going to get.

共勉。


LeetCode 之三角形最小路径和(Triangle)

看标题不知是否让您想起了有向图中的最短路径,是有些许类似,不过该题比其更简单更加清晰、直观、好理解。相信您看完这个之后,脑回路肯定更加的明亮!

题目描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形:

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

说明:

如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

初看题目,上下有关联,有结束点,是个适合用递归的题目。以三角形的“行数”作为递归的结束判断,行数加上下标作为参数来回穿插。可行,可行!

于是大笔一挥:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int size = 0;
TreeSet<Integer> ts = new TreeSet<>();
List<List<Integer>> list;

/**
* 超时
*
* @param triangle
* @return
*/
public int minimumTotal(List<List<Integer>> triangle) {
list = triangle;
size = triangle.size();
if (size == 0)
return 0;

helper(0, 0, 0);
return ts.first();
}

/**
*
* @param row
* 行数
* @param index
* 在该行中下标
* @param sum_length
* 路径之和
*/
private void helper(int row, int index, int sum_length) {
if (row >= size) {
ts.add(sum_length);
return;
}
sum_length += list.get(row).get(index);
helper(row + 1, index, sum_length);
helper(row + 1, index + 1, sum_length);
}

是的,代码没有问题,可是拿去跑的时候,数据较大的测试用例却给了一个大红色的 超出时间限制。这里将 TreeSet 换成一个 MIN_LENGTH 整型变量每次进行比较取较小值,结果一样,都是超时。

本来是满怀欣喜,豪气撸码,结果给撞了个豆腐墙。

墙不硬,问题不大。我们换个思路,再摸摸青青草地。

以往出现这种求最小值、最大值啊,需要数据之间相关联相加减乘除的啊,用的都是 DP 居多啊!

脑浆乍现,回路高速擦亮,越擦越亮,越擦越闪,终于“吡”得一身,为数不多的小草又飘下几根,成了!

我也不用额外的空间了,就在你身上肆虐!

再回头看下那个“三角形”:

1
2
3
4
5
6
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

既然是要一个最小值,那我就逐步缩减法,自下而上攻之。

根据题目要求我们知道如果上一行的元素下标为 i,那它只能跟它下一行的下标为 i 和 i+1 两元素相加。当然,我们只需要这两者的较小值。

即:

1
2
3
4
5
6
7
8
9
10
11
12
13
 [6,5,7]   // i 行
[4,1,8,3] // j 行

以这两行为例 (条件:j = i + 1)

i 行中的 6 可以跟 j 行中的 4 或者 1 相加,由于我们结果取的是最小值,所以我们只留较小值
6 + 4 = 10, 6 + 1 = 7
因为 10 > 7,所以 i 行中的 6 我们就随之替换为 7

剩余元素同理,i 行最终便成了:
[7,6,10]

再由此,层层攻上。随着数量越来越少,最终顶上的那位佼佼者便是我们要取的首级!

武器献之:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* DP
*
* @param triangle
* @return
*/
public int minimumTotal(List<List<Integer>> triangle) {

// 从倒数第二行开始往上走
for (int i = triangle.size() - 2; i >= 0; i--) {
// 从每行的起始下标开始直到 i
for (int j = 0; j <= i; j++) {
// i 行 j 下标的值
int self = triangle.get(i).get(j);
// 将 i 行 j 下标的值赋为 : i 行 j 下标的值 与 i+1 行 j 下标和 j+1 下标值之和的较小值
triangle.get(i).set(j,
Math.min(triangle.get(i + 1).get(j) + self, triangle.get(i + 1).get(j + 1) + self));
}
}
// 层层往上 顶层值便是路径最小值
return triangle.get(0).get(0);
}

这道题容易理解,对 DP(动态规划) 会有一个较为清晰的认知,我认为还是很不错的,故特意整理之。


文笔不好,望见谅! End.


JVM 之字节码执行引擎

代码编译的结果从本地机器码转变为字节码,是存储格式发展的一小步,却是编程语言发展的一大步。

概述

执行引擎是 Java 虚拟机最核心的组成部分之一。在不同的虚拟机实现里面,执行引擎在执行 Java 代码的时候可能会有解释执行(通过解释器执行)和编译执行(通过即时编译器产生本地代码执行)两种选择,也可能两者兼备,甚至还可能会包含几个不同级别的编译器执行引擎。

但从外观上看起来,所有的 Java 虚拟机的执行引擎都是一致的:输入的是字节码文件,处理过程是字节码解析的等效过程,输出的是执行结果。接下来将主要从 概念模型的角度来总结下虚拟机的 方法调用字节码执行

运行时栈帧结构

栈帧是用于支持虚拟机进行方法调用和方法执行的数据结构,它是虚拟机运行时数据区中的虚拟机栈的栈元素。每一个方法从调用开始至执行完成的过程,都对应着一个栈帧在虚拟机栈里面从入栈到出栈的过程。

每一个栈帧都包括了局部变量表、操作数栈、动态连接、方法返回地址和一些额外的附加信息。在编译程序代码的时候,栈帧中需要多大的局部变量表,多深的操作数栈都已经完全确定了,并且写入到方法表的 Code 属性之中,因此,一个栈帧需要分配多少内存,不会受到程序运行期变量数据的影响,而仅仅取决于具体的虚拟机实现。

局部变量表

局部变量表是一组变量值存储空间,用于存放方法参数和方法内部定义的局部变量。它的容量以变量槽(Variable Slot,下称 Slot)为最小单位。

在方法执行时,虚拟机是使用局部变量表来完成参数值到参数变量列表的传递过程的,如果执行的是实例方法(非 static 的方法),那局部变量表中第 0 位索引的 Slot 默认是用于传递方法所属对象实例的引用,在方法中可以通过关键字 this 来访问到这个隐含的参数。其余参数则按照参数表顺序排列,占用从 1 开始的局部变量 Slot,参数表分配完毕后,再根据方法体内部定义的变量顺序和作用域分配其余的 Slot。

局部变量定义了但没有赋初始值,是不能使用的,切记!

操作数栈

操作数栈也常称为操作栈,它是一个后入先出栈。同局部变量表一样,它的最大深度也是在编译时就写入到 Code 属性的 max_stacks 数据项中。

当一个方法刚刚开始执行时,这个方法的操作数栈是空的,在方法的执行过程中,会有各种字节码指令往操作数栈中写入和提取内容,也就是出栈 / 入栈操作。如:在做算术运算的时候是通过操作数栈来进行的,又或者在调用其他方法的时候是通过操作数栈来进行参数传递的。

动态连接

每个栈帧都包含一个指向运行时常量池中该栈帧所属方法的引用,持有这个引用是为了支持方法调用过程中的动态连接。

字节码中的方法调用指令就以常量池中指向方法的符号引用作为参数。这些符号引用一部分会在类加载阶段或者第一次使用的时候就转化为直接引用,这种转化称为 静态解析。另外一部分将在每一次运行期间转化为直接引用,这部分称为 动态连接

方法返回地址

当一个方法开始执行后,只有两种方式可以退出这个方法:

  • 执行引擎遇到任意一个方法返回的字节码指令,这时候可能会有返回值传递给上层的方法调用者,是否有返回值和返回值的类型将根据遇到何种方法返回指令来决定,这种退出方法的方式称为正常完成出口。
  • 在方法执行过程中遇到了异常,并且这个异常没有在方法体内得到处理,无论是 Java 虚拟机内部产生的异常还是代码中使用 athrow 字节码指令产生的异常,只要在本方法的异常表中没有搜索到匹配的异常处理器,就会导致方法退出,这种退出方法的方式称为异常完成出口。

一个方法使用异常完成出口的方式退出,是不会给它的上层调用者产生任何返回值的。

方法退出的过程实际上就等同于把当前栈帧出栈,因此退出时可能执行的操作有:恢复上层方法的局部变量表和操作数栈,把返回值(如果有的话)压入调用者栈帧的操作数栈中,调整 PC 计数器的值以指向方法调用指令后面的一条指令等。

附加信息

虚拟机规范允许具体的虚拟机实现增加一些规范中没有描述的信息到栈帧之中,例如与调试相关的信息,这部分信息完全取决于具体的虚拟机实现。

在实际开发中,一般会把动态连接、方法返回地址与其他附加信息全部归为一类,称为栈帧信息。

附上手稿

方法调用

方法调用并不等同于方法执行,方法调用阶段唯一的任务就是确定被调用方法的版本(即调用哪一个方法),暂时还不涉及方法内部的具体运行过程。

一切方法调用在 Class 文件里面存储的都只是符号引用,而不是方法在实际运行时内存布局中的入口地址(相当于之前说的直接引用)。

解析

调用目标在程序代码写好、编译器进行编译时就必须确定下来。这类方法的调用称为解析。

在 Java 虚拟机里面提供了 5 条方法调用字节码指令:

  • invokestatic:调用静态方法
  • invokespecial:调用实例构造器 <init> 方法、私有方法和父类方法
  • invokevirtual:调用所有的虚方法
  • invokeinterface:调用接口方法,会在运行时再确定一个实现此接口的对象
  • invokedynamic:先在运行时动态解析出调用点限定符所引用的方法,然后再执行该方法,在此之前的 4 条调用指令,分派逻辑是固化在 Java 虚拟机内部的,而 invokedynamic 指令的分派逻辑是由用户所设定的引导方法决定的

只要能被 invokestatic 和 invokespecial 指令调用的方法,都可以在解析阶段中确定唯一的调用版本,符合这个条件的有静态方法、私有方法、实例构造器和父类方法 4 类。它们在类加载的时候就会把符号引用解析为该方法的直接引用,称为 非虚方法。其余的称为 虚方法

final 方法是一种非虚方法。

分派

静态分派

Human man = new Man()

上面代码中的 Human 称为变量的静态类型,或是外观类型,Man 称为变量的实际类型。静态类型和实际类型在程序中都可以发生一些变化,但是静态类型的变化仅仅在使用时发生,变量本身的静态类型不会被改变,并且最终的静态类型是在编译期可知的;而实际类型变化的结果在运行期才可确定,编译器在编译程序时并不知道一个对象的实际类型是什么。

编译器在重载时是通过参数的静态类型而不是实际类型作为判断依据的,所以,两个静态类型相同但实际类型不同的变量,在编译阶段,Javac 编译器会根据参数的静态类型决定使用哪一个重载版本。

动态分派

我们先说说重写,重写与动态分派关系密切。invokevirtual 指令执行是在 运行期确定接收者的实际类型,所以调用中的 invokevirtual 指令把常量池中的类方法符号引用解析到了不同的直接引用上,这个过程就是 Java 语言中方法重写的本质。

我们把这种在运行期根据实际类型确定方法执行版本的分派过程称为动态分派。

附上手稿

单分派与多分派

方法的接收者与方法的参数统称为方法的宗量,根据分派基于多少种宗量,可以将分派划分为单分派和多分派两种。

单分派是根据一个宗量对目标方法进行选择,多分派是根据多于一个宗量对目标方法进行选择。

基于栈的字节码解释执行引擎

探讨虚拟机是如何执行方法中的字节码指令的。

解释执行

编译过程

Java 语言中,Javac 编译器完成了程序代码经过词法分析、语法分析到抽象语法树,再遍历语法树生成线性的字节码指令流的过程。因为这一部分动作是在 Java 虚拟机之外进行的,而解释器在虚拟机的内部,所以 Java 程序的编译就是半独立的实现。

基于栈的指令集与基于寄存器的指令集

基于栈的指令集主要优点就是可移植,还可把一些访问频繁的数据放到寄存器中获取尽量好的性能,代码会相对更加紧凑,编译器实现更加简单等。

栈架构指令集的主要缺点是执行速度相对来说会稍慢一些,完成相同功能所需的指令数量较寄存器架构多,频繁的栈访问导致频繁的内存访问。


End.


忙碌十一月(2018)

这个十一月为什么说忙碌呢,因为忙着抽纸巾擤鼻涕,感冒了;因为忙着买买买,剁手了;因为忙着来来回回,出差了。

  • 感冒

怪我,都怪我,前一段时间温差变化大,我懒啊,没及时加被子,还没穿裤子就睡了,半夜那个冻的,知道冷但就是没爬起来加被子,然后,感冒了一周,鼻子都搞破皮了……

后来晚上还去夜跑,跑完当时感觉好点了,结果洗了个澡之后,鼻涕又来了,睡觉时候那个呼吸难受的啊,还好我床头纸管够……

  • 买买买

最近买了不少东西,买了件大衣,结果稍稍大了点,不换了吧来来回回的,凑活穿。还买了几双鞋,什么耐克阿迪的,便宜的太丑,好看的太贵还没货,倒是对彪马越来越感兴趣,价格还行,款式也还行(不还是因为较之便宜嘛……)。

气的是有双鞋刚买了不到一个月就又看到大降价,差了一百来块呢,唉,安慰自己毕竟早穿上了这么多天呢不是……

平时感觉穿的也都有,但是人嘛,喜新厌旧,而且这个购物啊,确实是精神上不一样啊,单身狗的刺激手段之一了,避免一直陷在麻木的生活状态之中。偶尔还是需要精神刺激的,啊,好疼~

搞了套迪卡侬的运动装备,迪卡侬性价比真高,懊恼自己以前怎么不去了解,东西感觉都不错,大赞!以后运动装备就尽量选择迪卡侬了。

  • 金链子

去年就跟老姐说过今年要给老妈买条大金链子的,身上什么首饰也没有,着实不好了点。故趁着发工资了,给老姐打过去 2000 块,“给老妈买条大金链子!其余的你补上!”哈哈,2000 肯定是不够买的,怪儿子出门在外没挣到什么钱,心意到了啊。回头给老爸搞双皮鞋,本来是去年买的,唉,加油加油!

说到金,家里爷爷还留给我一个纯金戒指来着。小时候我看着那戒指,心想,这纯金戒指,得值多少钱啊。现在知道了,也就值个千把块钱……还用来传家呢……看什么时候给它化了,弄成其他的,金戒指也忒俗气了些。

  • 路上姑娘

今儿早又看到这姑娘了,所以我才把这提上来。

姑娘长发小脸,笑意浓浓,纤细身材,气质不凡。

我们往往是在五角场附近相遇的。我骑着车,她低着头。

虽然我看她时她没看过我,但我却看到她眼睛在笑,即使我那只是短短的一瞥,看得却异常清楚。有一种熟悉的感觉爬上了我的心头。可能是我接触异性少了,脑子出现了毛病……用我大学室友一句口头禅来说就是:这个不孬。

也正是这几个月来遇到了很多次,且位置都大差不差,我这才记住了,不知道她是否注意到我没……

人的一生会遇到许许多多的人。佛说,前世的五百次回眸,才换来今生的擦肩而过。

如果无缘,我只愿你一生安好,陌生人。

  • 出差

出差了出差了,人生中的第一次出差啊。这次去杭州出差了一周,期间自然不是很顺利。项目上的就不多说了,这个晚上啊,因为还有一位同事一起的,所以我们就定的标间。

我那几天都是凌晨才慢慢睡去。为什么?旁边有位打呼跟电钻工装修一样的,要搁你,你能睡得着不……我还那会感冒没好全,身体素质是真不好,鼻血都流了好几回也不知道是不是擤鼻涕用力过猛了。

而且我这个头啊,右脑勺还真刺疼,公司体检卡发了,不过要下月才开始能预约,希望一切健康,买的保险用不上啊……

说到买的保险,买了个泰康的,送了个洗牙套餐,上月预约的都只能预约到一月份了,全家现在就我这口牙还行,最近好像也是开始出问题了,我得勤刷牙了,晚上不忘记能刷就刷。

拉回来说这个出差。由于我也没有经验,也没有什么准备,导致我根本就找不到可以冲账的发票,最后还是用的领导的燃油发票来报。看来,以后要多攒攒发票了,虽说出差少,备着吧。

  • 余华

余华,当代著名作家,他的许多作品获过国内外奖项。

不知道,没关系。《活着》这部小说,总看过吧,没看过总听说过吧。没听说过?那我劝你现在就拿起手机打开 APP,订购一本,不要 998,也不要 198,它只要二十来块就能买到。

记得当时我是花了一个晚上把《活着》给看完的,情节太紧凑了根本不给我歇的机会,看了停不下来,等歇下来了,原来后面没了,翻到了最后一页。

最近我又在看他的另一本长篇小说《兄弟》。文人骚客,不骚就不叫文人了。不过里面骚的恰到好处,连接情节,更能吸引读者,引人入胜。

大体上,我看到现在,主色调还是悲的,也是在文革前后那段时间下描述的故事。极具讽刺意味。

只要能捱过来,那就都不是事。

  • 蒋劲夫家暴

今天早上又刷到了这个新闻。家暴,我是不可能家暴的,真的很气愤也只会动动嘴皮子,大不了就出门透透气。个人认为,家暴确实是做不得,也不是男人该做的事。当然,会有些人有暴力倾向,更可怕的是有些女人还会十分享受被家暴的过程,这种人呢肯定是有的,而且可能还不少。

大家夫妻之间,情侣之间搞搞 SM 啊什么的我倒是觉得很正常,别动不动就搞出血还搞出命,不值当啊!所以,两人在一起,这些东西都是需要熟知的,要了解清楚,三观不合的怎么可能长久,那种一夜情的就没必要查户口了。


真快啊都要 2018 12 月份了,下次写个年终总结,好好借机回顾一下自己这一年来的成长。长肯定是有长的,长哪就不知道了。

哈哈,生死本无常,人应多思量。


LeetCode 之二叉树的各种遍历(Binary Tree Traversal)

在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

想必大家对二叉树也不陌生,被各种二叉树面试题支配的恐惧仍记忆犹新……

这篇就总结一下二叉树的各种遍历,包括前、中、后序遍历还有层次遍历。

让我们来想象,大脑是个无底洞,这个栈它没有深度,所以我们要时而把栈底那些强行挖上来,以防痴呆!你不想痴呆吧!go go go.

层次遍历

先来这个层次遍历,二叉树一层又一层,它有深度。既然是一层接着一层,那很清楚了,我们逐层遍历就行。

题目描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回其层次遍历结果:

[
[3],
[9,20],
[15,7]
]

清晰得不能再清晰了。递归调用 + 循环节点。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}

public List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> list = new ArrayList<>();
List<TreeNode> l = new ArrayList<>();
l.add(root);
helper(list, l);
return list;

}

/**
* 递归 层层遍历
*
* @param list
* @param treeList
*/
private void helper(List<List<Integer>> list, List<TreeNode> treeList) {
if (treeList.size() == 0)
return;
List<Integer> listInt = new ArrayList<>();
List<TreeNode> treeL = new ArrayList<>();
// 逐层添值
for (TreeNode node : treeList) {
if (node != null) {
listInt.add(node.val);
treeL.add(node.left);
treeL.add(node.right);
}
}
if (listInt.size() > 0)
list.add(listInt);

helper(list, treeL);
}

或者是使用队列 + while 循环搞定:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* 使用队列 queue
*
* @param root
* @return
*/
public List<List<Integer>> levelOrder1(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> wrapList = new LinkedList<List<Integer>>();

if (root == null)
return wrapList;

queue.offer(root);
while (!queue.isEmpty()) {
// 有值就塞入集合 同时将其左右子节点添加到队列中
int levelNum = queue.size();
List<Integer> subList = new LinkedList<Integer>();
for (int i = 0; i < levelNum; i++) {
if (queue.peek().left != null)
queue.offer(queue.peek().left);
if (queue.peek().right != null)
queue.offer(queue.peek().right);
subList.add(queue.poll().val);
}
wrapList.add(subList);
}
return wrapList;
}

这个问题不大。

中序遍历

中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。

也就是根结点遍历位置在中间: 左 -> 根 -> 右

题目描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
1
\
2
/
3

输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

既然都说了递归算法很简单,确实也很简单,先上递归算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}

/**
* 递归
*
* @param root
* @return
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
helper(list, root);
return list;
}

private void helper(List<Integer> list, TreeNode node) {
if (node != null) {
if (node.left != null)
helper(list, node.left);
list.add(node.val);
if (node.right != null)
helper(list, node.right);
}
}

这个递归算法在前、中、后序遍历都可以套用的,着实好用也好记。下面就不重复该代码了,无非就是结点的顺序换一换。

迭代算法,这里我们思考一下,我们需要先读其左结点,读完之后再读其根结点,左结点若是存在,那它不就是下一层的根结点吗?然后我们再一层层往上读。此时脑壳一抖,栈!

Stack 来解决:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* 栈 stack 来解决
*
* @param root
* @return
*/
public List<Integer> inorderTraversal1(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
// 将其左节点依次放入 因为先读左节点
stack.push(curr);
curr = curr.left;
}
// 将栈顶弹出
curr = stack.pop();
// 塞值
res.add(curr.val);
// 将右节点赋值给它 完美呈现了中序遍历 : 左 -> 根 -> 右
curr = curr.right;
}
return res;
}

代码也不长,该过程可以用大脑无底栈来走一遍。闭上眼睛,冥想。

前序遍历

前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

即根结点遍历位置在前面: 根 -> 左 -> 右

题目描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一个二叉树,返回它的 前序 遍历。

示例:

输入: [1,null,2,3]
1
\
2
/
3

输出: [1,2,3]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

递归算法不说了,见上。

迭代这里用双向链表 LinkedList,数据量大时存取数据性能好点。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* 双向队列
*
* @param root
* @return
*/
public List<Integer> preorderTraversal1(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
// 弹出队列中最后一个
TreeNode node = stack.pollLast();
output.add(node.val);
if (node.right != null) {
stack.add(node.right);
}
if (node.left != null) {
// 该节点就是下一个要读的根节点
stack.add(node.left);
}
}
return output;
}

这里需要注意的就是 stack.add() 先添加右结点在添加左结点,因为 stack.pollLast() 取出的是最后一个数据,这样就是左结点先弹出,满足前序遍历的顺序。

后序遍历

后序遍历(LRD)是二叉树遍历的一种,也叫做后根遍历、后序周游,可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中,先左后右再根,即首先遍历左子树,然后遍历右子树,最后访问根结点。

即根结点遍历位置在前面: 左 -> 右 -> 根

题目描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一个二叉树,返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
1
\
2
/
3

输出: [3,2,1]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

同样,递归算法不重复,见上。

这里的迭代算法我是看了官网的解法。秒。利用双向链表每次在起始位置添加值,顺序为根 -> 右 -> 左,然后遍历完后整个顺序从前往后就是左 -> 右 -> 根,后序遍历。

双向链表 LinkedList + 栈 Stack,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}

/**
* 根 -> 右 -> 左 存入,遍历完全后从前往后即是 左 -> 右 -> 根
*
* @param root
* @return
*/
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null)
return ans;

stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
// 将值塞到最前面
ans.addFirst(cur.val);
// 先左结点入栈
if (cur.left != null) {
stack.push(cur.left);
}
// 再是右结点入栈
if (cur.right != null) {
stack.push(cur.right);
}
}
return ans;
}

从后往前推,一气呵成。


其实,还是递归最好使……


JVM 之类加载机制

代码编译的结果从本地机器码转变为字节码,是存储格式发展的一小步,却是编程语言发展的一大步。

概述

虚拟机把描述类的数据从 Class 文件加载到内存,并对数据进行校验、转换解析和初始化,最终形成可以被虚拟机直接使用的 Java 类型,这就是虚拟机的类加载机制。

与那些在编译时需要进行连接工作的语言不同,在 Java 语言里面,类型的加载、连接和初始化过程都是在程序运行期间完成的,Java 里天生可以动态扩展的语言特性就是依赖 运行期动态加载动态连接这个特点实现的。

类加载的时机

类从被加载到虚拟机内存中开始,到卸载出内存为止,它的整个生命周期包括:加载、验证、准备、解析、初始化、使用和卸载 7 个阶段。其中验证、准备、解析 3 个部分统称为连接。

类的生命周期

加载、验证、准备、初始化和卸载这 5 个阶段的顺序是确定的,类的加载过程必须按照这种顺序按部就班地开始,而解析阶段则不一定:它在某些情况下可以在初始化阶段之后再开始,这是为了支持 Java 语言的运行时绑定(也称为动态绑定或晚期绑定)。

对于初始化阶段,虚拟机规范是严格规定了 有且只有 5 中情况必须对类进行“初始化”(而加载、验证、准备自然需要在此之前开始):

  • 遇到 new、getstatic、putstatic 或 invokestatic 这 4 条字节码指令时,如果类没有进行过初始化,则需要先触发其初始化
  • 使用 java.lang.reflect 包的方法对类进行反射调用的时候,如果类没有进行过初始化,则需要先触发其初始化
  • 当初始化一个类的时候,如果发现其父类还没有进行过初始化,则需要先触发其父类的初始化
  • 当虚拟机启动时,用户需要指定一个要执行的主类(包含 main() 方法的那个类),虚拟机会先初始化这个主类
  • 当使用 JDK 1.7 的动态语言支持时,如果一个 java.lang.invoke.MethodHandle 实例最后的解析结果 REF_getStatic、REF_putStatic、REF_invokeStatic 的方法句柄,并且这个方法句柄所对应的类没有进行过初始化,则需要先触发其初始化

这 5 中场景中的行为称为对一个类进行主动引用。除此之外,所有引用类的方式都不会触发初始化,称为被动引用。

被动引用举例:

  • 通过子类引用父类的静态字段,不会导致子类初始化
  • 通过数组定义来引用类,不会触发此类的初始化
  • 常量在编译阶段存入常量池中,调用时不会触发定义常量的类的初始化

接口的加载过程与类加载过程稍有一些不同,针对接口需要做一些特殊处理:接口也有初始化过程,虽然接口中不能使用 “static{}” 语句块,但编译器仍然会为接口生成 “<clinit>()” 类构造器,用于初始化接口中所定义的成员变量。

当一个类在初始化时,要求其父类全部都已经初始化过了,但是一个接口在初始化时,并不要求其父接口全部都完成了初始化,只有在真正使用到父接口的时候(如引用接口中定义的常量)才会初始化。

类加载的过程

类加载的全过程也就是加载、验证、准备、解析和初始化这 5 个阶段所执行的具体动作。

加载

“加载”是“类加载”过程的一个阶段,在加载阶段,虚拟机需要完成以下 3 件事情:

  • 通过一个类的全限定名来获取定义此类的二进制字节流
  • 将这个字节流所代表的静态存储结构转化为方法区的运行时数据结构
  • 在内存中生成一个代表这个类的 java.lang.Class 对象,作为方法区这个类的各种数据的访问入口

加载阶段完成后,虚拟机外部的二进制字节流就按照虚拟机所需的格式存储在方法区之中,方法区中的数据存储格式由虚拟机实现自行定义,虚拟机规范未规定此区域的具体数据结构。然后在内存中实例化一个 java.lang.Class 类的对象(并没有明确规定是在 Java 堆中,对于 HotSpot 虚拟机而言,Class 对象比较特殊,它虽然是对象,但是存放在方法区里面),这个对象将作为程序访问方法区中的这些类型数据的外部接口。

加载阶段与连接阶段的部分内容是交叉进行的,如一部分字节码文件格式验证动作。

验证

验证是连接阶段的第一步,这一阶段的目的是为了确保 Class 文件的字节流中包含的信息符合当前虚拟机的要求,并且不会危害虚拟机自身的安全。

从整体上看,验证阶段大致上会完成下面 4 个阶段的校验动作:

文件格式验证

第一阶段要验证字节流是否符合 Class 文件格式的规范,保证输入的字节流能正确地解析并存储于方法区之内,并且能被当前版本的虚拟机处理。

该阶段的验证是基于二进制字节流进行的,只有通过了这个阶段的验证后,字节流才会进入内存的方法区中进行存储。

元数据验证

第二阶段是对字节码描述的信息进行语义分析,对类的元数据信息进行语义校验,以保证其描述的信息符合 Java 语言规范的要求。

字节码验证

第三阶段是整个验证过程中最复杂的一个阶段,主要目的是通过数据流和控制流分析,确定程序语义是合法的、符合逻辑的。

如果一个类方法体的字节码没有通过字节码验证,那肯定是有问题的;但如果一个方法体通过了字节码验证,也不能说明其一定就是安全的。即使字节码验证之中进行了大量的检查,也不能保证这一点。即通过程序去校验程序逻辑是无法做到绝对准确的——不能通过程序准确地检查出程序是否能在有限的时间之内结束运行。

符号引用验证

最后一个阶段的校验发生在虚拟机将符号引用转化为直接引用的时候,这个转化动作将在连接的第三阶段——解析阶段中发生。符号引用验证可以看做是对类自身以外(常量池中的各种符号引用)的信息进行匹配性校验。

符号引用验证的目的是确保解析动作能正常执行。

对于虚拟机的类加载机制来说,验证阶段是一个非常重要的、但不是一定必要的阶段。

准备

准备阶段是正式为类变量分配内存并设置类变量初始值的阶段,这些变量所使用的内存都将在方法区中进行分配。

这时候进行内存分配的仅包括类变量(被 static 修饰的变量),而不包括实例变量,实例变量将会在对象实例化时随着对象一起分配在 Java 堆中。

public static int value = 123;

上述的 value 变量在准备阶段过后的初始值为 0 而不是 123,因为这时候尚未开始执行任何 Java 方法,而把 value 赋值为 123 的 putstatic 指令是程序被编译后,存放于类构造器 <clinit>() 方法之中,所以把 value 赋值为 123 的动作将在初始化阶段才会执行。

如果类字段的字段属性表中存在 ConstantValue 属性,那在准备阶段变量 value 就会被初始化为 ConstantValue 属性所指定的值,如:

public static final int value = 123;

编译时 Javac 将会为 value 生成 ConstantValue 属性,在准备阶段虚拟机就会根据 ConstantValue 的设置将 value 赋值为 123。

解析

解析阶段是虚拟机将常量池内的符号引用替换为直接引用的过程。

  • 符号引用:符号引用以一组符号来描述所引用的目标,符号可以是任何形式的字面量,只要使用时能无歧义地定位到目标即可。
  • 直接引用:直接引用可以是直接指向目标的指针、相对偏移量或是一个能间接定位到目标的句柄。

解析动作主要针对以下 7 类符号引用进行:

  • 类或接口的解析
  • 字段解析
  • 类方法解析
  • 接口方法解析
  • 方法类型解析
  • 方法句柄解析
  • 调用点限定符解析

初始化

类初始化阶段是类加载过程的最后一步,前面的类加载过程中,除了在加载阶段用户应用程序可以通过自定义类加载器参与之外,其余动作完全由虚拟机主导和控制。到了初始化阶段,才真正开始执行类中定义的 Java 程序代码(或者说是字节码)。

初始化阶段是执行类构造器 <clinit>() 方法的过程,在这执行过程中一些可能会影响程序运行行为的特点和细节:

  • <clinit>() 方法是由编译器自动收集类中所有类变量的赋值动作和静态语句块(static{} 块)中的语句合并产生的,编译器收集的顺序是由语句在源文件中出现的顺序所决定的,静态语句块中只能访问到定义在静态语句块之前的变量,定义在它之后的变量,在前面的静态语句块可以赋值,但是不能访问。
  • <clinit>() 方法与类的构造函数(或者说实例构造器 <init>() 方法)不同,它不需要显式地调用父类构造器,虚拟机会保证在子类的 <clinit>() 方法执行之前,父类的 <clinit>() 方法已经执行完毕。因此在虚拟机中第一个被执行的 <clinit>() 方法的类肯定是 java.lang.Object。
  • 由于父类的 <clinit>() 方法先执行,也就意味着父类中定义的静态语句块要优先于子类的变量赋值操作。
  • <clinit>() 方法对于类或接口来说并不是必需的,如果一个类中没有静态语句块,也没有对变量的赋值操作,那么编译器可以不为这个类生成 <clinit>() 方法。
  • 接口中不能使用静态语句块,但仍然有变量初始化的赋值操作,因此接口与类一样都会生成 <clinit>() 方法。但接口与类不同的是,执行接口的 <clinit>() 方法不需要先执行父接口的 <clinit>() 方法。只有当父接口中定义的变量使用时,父接口才会初始化。另外,接口的实现类在初始化时也一样不会执行接口的 <clinit>() 方法。
  • 虚拟机会保证一个类的 <clinit>() 方法在多线程环境中被正确地加锁、同步,如果多个线程同时去初始化一个类,那么只会有一个线程去执行这个类的 <clinit>() 方法,其他线程都需要阻塞等待,直到活动线程执行 <clinit>() 方法完毕。如果在一个类的 <clinit>() 方法中有耗时很长的操作,就可能造成多个进程阻塞,在实际应用中这种阻塞往往是很隐蔽的。

类加载器

虚拟机设计团队把类加载器阶段中的“通过一个类的全限定名来获取描述此类的二进制字节流”这个动作放到 Java 虚拟机外部去实现,以便让应用程序自己决定如何去获取所需要的类。实现这个动作的代码模块称为“类加载器”。

类与类加载器

对于任意一个类,都需要由加载它的类加载器和这个类本身一同确立其在 Java 虚拟机中的唯一性,每一个类加载器,都拥有一个独立的类名称空间。

双亲委派模型

从 Java 虚拟机的角度来讲,只存在两种不同的类加载器:

  • 启动类加载器,这个类加载器使用 C++ 语言实现,是虚拟机自身的一部分
  • 所有其他的类加载器,这些类加载器都由 Java 语言实现,独立于虚拟机外部,并且全部都继承自抽象类 java.lang.ClassLoader

类加载器还可以划分得更细致一些,绝大部分 Java 程序都会使用到一下 3 种系统提供的类加载器:

  • 启动类加载器(Bootstrap ClassLoader):这个类加载器负责将存放在 <JAVA_HOME>\lib 目录中的,或者被 -Xbootclasspath 参数所指定的路径中的,并且是虚拟机识别的类库加载到虚拟机内存中。启动类加载器无法被 Java 程序直接引用,用户在编写自定义类加载器时,如果需要把加载请求委派给引导类加载器,那直接使用 null 代替即可。
  • 扩展类加载器(Extension ClassLoader):这个加载器由 sun.misc.Launcher$ExtClassLoader 实现,它负责加载 <JAVA_HOME>\lib\ext 目录中的,或者被 java.ext.dirs 系统变量所指定的路径中的所有类库,开发者可以直接使用扩展类加载器。
  • 应用程序类加载器(Application ClassLoader):这个类加载器由 sun.misc.Launcher$AppClassLoader 实现。由于这个类加载器是 ClassLoader 中的 getSystemClassLoader() 方法的返回值,所以一般也称它为系统类加载器。它负责加载用户类路径(ClassPath)上所指定的类库,开发者可以直接使用这个类加载器,如果应用程序中没有自定义过自己的类加载器,一般情况下这个就是程序中默认的类加载器。

我们的应用程序都是由这 3 种类加载器互相配合进行加载的,如果有必要,还可以加入自己定义的类加载器。

类加载器双亲委派模型

上图中展示的类加载器之间的这种层次关系,称为类加载器的双亲委派模型。

双亲委派模型的工作过程是:如果一个类加载器收到了类加载器的请求,它首先不会自己去尝试加载这个类,而是把这个请求委派给父类加载器去完成,每一个层次的类加载器都是如此,因此所有的加载请求最终都应该传送到顶层的启动类加载器中,只有当父加载器反馈自己无法完成这个加载请求(它的搜索范围中没有找到所需的类)时,子加载器才会尝试自己去加载。


End.这一篇由于篇幅过大,故手稿就不丢出来了。还是一些概念,类加载是经常会被面试问到的知识点,可见其重要性了。该啃还是要啃的,就点醋……


JVM 之类文件结构

代码编译的结果从本地机器码转变为字节码,是存储格式发展的一小步,却是编程语言发展的一大步。

无关性的基石

实现语言无关性的基础是虚拟机和字节码存储格式。Java 虚拟机不和包括 Java 在内的任何语言绑定,它只与“Class 文件”这种特定的二进制文件格式所关联,Class 文件中包含了 Java 虚拟机指令集和符号表以及若干其他辅助信息。

基于安全方面的考虑,Java 虚拟机规范要求在 Class 文件中使用许多强制性的语法和结构化约束,但任一门功能性语言都可以表示为一个能被 Java 虚拟机所接受的有效的 Class 文件。

Java 虚拟机提供的语言无关性

Java 语言的各种变量、关键字和运算符号的语义最终都是由多条字节码命令组合而成的。

Class 类文件的结构

Class 文件是一组以 8 位字节为基础单位的二进制流,各个数据项目严格按照顺序紧凑地排列在 Class 文件之中,中间没有添加任何分隔符,这使得整个 Class 文件中存储的内容几乎全是程序运行的必要数据,没有空隙存在。

根据 Java 虚拟机规范的规定,Class 文件格式采用一种类似于 C 语言结构体的伪结构来存储数据,这种伪结构中只有两种数据类型:无符号数和表

  • 无符号数:属于基本的数据类型,以 u1、u2、u4、u8 来分别代表 1 个字节、2 个字节、4 个字节和 8 个字节的无符号数,无符号数可以用来描述数字、索引引用、数量值或者按照 UTF-8 编码构成字符串值。
  • 表:是由多个无符号数或者其他表作为数据项构成的复合数据类型,所有表都习惯性地以“_info”结尾。表用于描述有层次关系的复合结构的数据,整个 Class 文件本质上就是一张表。

(这里有关的详细介绍还是请看《深入理解 Java 虚拟机》中的第六章节)

魔数与 Class 文件的版本

每个 Class 文件的头 4 个字节称为魔数,它的唯一作用是 确定这个文件是否为一个能被虚拟机接受的 Class 文件。

Class 文件的魔数的获得很有“浪漫气息”,值为:0xCAFEBABE(咖啡宝贝……)

紧接着魔数的 4 个字节存储的是 Class 文件的版本号:第 5 和第 6 个字节是次版本号,第 7 和第 8 个字节是主版本号。

常量池

紧接着主次版本号之后的是常量池入口,常量池可以理解为 Class 文件之中的资源仓库,它是 Class 文件结构中与其他项目关联最多的数据类型,也是占用 Class 文件空间最大的数据项目之一,同时它还是在 Class 文件中第一个出现的表类型数据项目。

由于常量池中常量的数量是不固定的,所以在常量池的入口需要放置一项 u2 类型的数据,代表常量池容量计数值。与 Java 中语言习惯不一样的是,这个容量计数是从 1 开始而不是 0。

在 Class 文件格式规范制定之时,设计者将第 0 项常量空出来是为了满足后面某些指向常量池的索引值的数据在特定情况下需要表达“不引用任何一个常量池项目”的含义,这种情况就可以把索引值置为 0 来表示。

常量池主要存放两大类常量:字面量和符号引用。

字面量比较接近于 Java 语言层面的常量概念,比如文本字符串、声明为 final 的常量值等。

而符号引用则属于编译原理方面的概念,包括了下面三类常量:

  • 类和接口的全限定名
  • 字段的名称和描述符
  • 方法的名称和描述符

在 Class 文件中不会保存各个方法、字段的最终内存布局信息,因此这些字段、方法的符号引用不经过运行期转换的话无法得到真正的内存入口地址,也就无法直接被虚拟机使用。

当虚拟机运行时,需要从常量池获得对应的符号引用,再在类创建时或运行时解析、翻译到具体的内存地址之中。

附上手稿

访问标志

在常量池结束之后,紧接着的两个字节代表访问标志,这个标志用于识别一些类或者接口层次的访问信息,包括:

  • 这个 Class 是类还是接口
  • 是否定义为 public 类型
  • 是否定义为 abstract 类型
  • 如果是类的话,是否被声明为 final
  • …..

类索引、父类索引与接口索引集合

类索引和父类索引都是一个 u2 类型的数据,而接口索引集合是一组 u2 类型的数据的集合,Class 文件中由这三项数据来确定这个类的继承关系。

类索引用于确定这个类的全限定名,父类索引用于确定这个类的父类的全限定名。

由于 Java 语言不允许多重继承,所以父类索引只有一个,除了 java.lang.Object 之外,所有的 Java 类都有父类,因此除了 java.lang.Object 外,所有 Java 类的父类索引都不为 0。

接口索引集合就用来描述这个类实现了哪些接口,这些被实现的接口将按 implements 语句(如果这个类本身是一个接口,则应当是 extends 语句)后的接口顺序从左到右排列在接口索引集合中。

字段表集合

字段表用于描述接口或者类中声明的变量。

字段包括类级变量以及实例级变量,但不包括在方法内部声明的局部变量。

字段表集合中不会列出从超类或者父类接口中继承而来的字段,但有可能列出原本 Java 代码之中不存在的字段,譬如在内部类中为了保持对外部类的访问性,会自动添加指向外部类实例的字段。

另外,在 Java 语言中字段是无法重载的,两个字段的数据类型、修饰符不管是否相同,都必须使用不一样的名称,但是对于字节码来讲,如果两个字段的描述符不一致,那字段重名就是合法的。

方法表集合

方法表的结构如同字段表一样,依次包括了访问标志、名称索引、描述符索引、属性表集合几项。

方法里的 Java 代码,经过编译器编译成字节码指令后,存放在方法属性表集合中一个名为“Code”的属性里面。

与字段表集合相对应的,如果父类方法在子类中没有被重写,方法表集合中就不会出现来自父类的方法信息。但同样的,有可能会出现由编译器自动添加的方法,最典型的便是类的构造器“<clinit>”方法和实例构造器“<init>”方法。

在 Java 语言中,要重载一个方法,除了要与原方法具有相同的简单名称之外,还要求必须拥有一个与原方法不同的特征签名,特征签名就是一个方法中各个参数在常量池中的字段符号引用的集合,也就是因为返回值不会包含在特征签名中,因此 Java 语言里面是无法仅仅依靠返回值的不同来对一个已有方法进行重载的。但是在 Class 文件格式中,特征签名的范围更大一些,只要描述符不是完全一致的两个方法也可以并存。也就是说,如果两个方法有相同的名称和特征签名,但返回值不同,那么也是可以合法共存于同一个 Class 文件中的。

属性表集合

在 Class 文件、字段表、方法表都可以携带自己的属性表集合,以用于描述某些场景专有的信息。

Code 属性

Code 属性是 Class 文件中最重要的一个属性,如果把一个 Java 程序中的信息分为代码和元数据两部分,那么在整个 Class 文件中,Code 属性用于描述代码,所有的其他数据项目都用于描述元数据。

在实例方法的局部变量表中至少会存在一个指向当前对象实例的局部变量,局部变量表中也会预留出第一个 Slot 位来存放对象实例的引用,方法参数值从 1 开始计算。

ConstantValue 属性

ConstantValue 属性的作用是通知虚拟机自动为静态变量赋值。只有被 static 关键字修饰的变量(类变量)才可以使用这项属性。

对于非 static 类型的变量(也就是实例变量)的赋值是在实例构造器 <init> 方法中进行的;而对于类变量,则有两种方式可以选择:在类构造器 <clinit 方法中或者使用 ConstantValue 属性。

附上手稿

字节码指令简介

Java 虚拟机的指令由一个字节长度的、代表着某种特定操作含义的数字(称为操作码)以及跟随其后的零至多个代表此操作所需参数(称为操作数)而构成。

字节码与数据类型

对于大部分与数据类型相关的字节码指令,它们的操作码助记符中都有特殊的字符来表明专门为哪种数据类型服务:i 代表对 int 类型的数据操作,l 代表 long,s 代表 short,b 代表 byte,c 代表 char,f 代表 float,d 代表 double,a 代表 reference。

大部分的指令都没有支持整数类型 byte、char 和 short,甚至没有任何指令支持 boolean 类型。编译器会在编译期或运行期将 byte 和 short 类型的数据带符号扩展为相应的 int 类型数据,将 boolean 和 char 类型数据零位扩展为相应的 int 类型数据。与之类似,在处理 boolean、byte、short 和 char 类型的数据时,也会转换为使用对应的 int 类型的字节码指令来处理。因此,大多数对于 boolean、byte、short 和 char 类型数据的操作,实际上都是使用相应的 int 类型作为运算类型。

加载和存储指令

加载和存储指令用于将数据在栈帧中的局部变量表和操作数栈之间来回传输,这类指令包括如下内容:

  • 将一个局部变量加载到操作栈
  • 将一个数值从操作数栈存储到局部变量表
  • 将一个变量加载到操作数栈
  • 扩充局部变量表的访问索引的指令

运算指令

运算或算术指令用于对两个操作数栈上的值进行某种特定运算,并把结果重新存入到操作栈顶。

大体上算术指令可以分为两种:对整型数据进行运算的指令与对浮点型数据进行运算的指令。

Java 虚拟机要求在进行浮点数运算时,所有的运算结果都必须舍入到适当的精度,非精确的结果必须舍入为可被表示的最接近的精确值,如果有两种可表示的形式与该值一样接近,将优先选择最低有效位为零的。这种舍入模式称为向最接近数舍入模式。

在把浮点数转换为整数时,Java 虚拟机使用向零舍入模式,这种模式的舍入结果会导致数字被截断,所有小数部分的有效字节都会被丢弃掉。向零舍入模式将在目标数值类型中选择一个最接近但是不大于原值的数字来作为最精确的舍入结果。

附上手稿


End. 这一章节概念的东西比较多,讲了 Class 文件中的种种。


JVM 之垃圾收集器与内存分配策略

Java 与 C++ 之间有一堵由内存动态分配和垃圾收集技术所围成的“高墙”,墙外面的人想进去,墙里面的人却想出来。

对象死活

垃圾收集器在对堆进行回收前,第一件事就是要确认这些对象之中哪些还“存活”着,哪些已经“死去”(即不可能再被任何途径使用的对象)

引用计数法

给对象中添加一个引用计数器,每当有一个地方引用它时,计数器值就加 1;当引用失效时,计数器值就减 1;任何时刻计数器为 0 的对象就是不可能再被使用的。这就是引用计数法。

但是,主流的 Java 虚拟机里面没有选用引用计数算法来管理内存,其中最主要的原因是它很难解决对象之间相互循环引用的问题。

可达性分析算法

这个算法的基本思路就是通过一系列的称为“GC Roots”的对象作为起始点,从这些节点开始向下搜索,搜索所走过的路径称为 引用链,当一个对象到 GC Roots 没有任何引用链相连时,则证明此对象是不可用的。

可达性分析算法判定对象是否可回收

上图所示,对象 object 5、object 6、object 7 虽然互相有关联,但是它们到 GC Roots 是不可达的,所以它们将会判定为是可回收的对象。

在 Java 语言中,可作为 GC Roots 的对象包括下面几种:

  • 虚拟机栈(栈帧中的本地变量表)中引用的对象。
  • 方法区中类静态属性引用的对象。
  • 方法区中常量引用的对象。
  • 本地方法栈中 JNI(即一般说的 Native 方法)引用的对象。

引用

在 JDK 1.2 以前,Java 中的引用的定义很传统:如果 reference 类型的数据中存储的数值代表的是另外一块内存的起始地址,就称这块内存代表着一个引用。

在 JDK 1.2 之后,Java 对引用的概念进行了扩充,将引用分为强引用、软引用、弱引用、虚引用 4 种,这 4 种引用强度依次逐渐减弱。

  • 强引用就是指在程序代码之中普遍存在的,类似“Object obj = new Object()”这类的引用,只要强引用还存在,垃圾收集器永远不会回收掉被引用的对象。
  • 软引用是用来描述一些 还有用但并非必需的对象。对于软引用关联着的对象,在系统将要发生内存溢出异常之前,将会把这些对象列进回收范围之中 进行第二次回收。如果这次回收还没有足够的内存,才会抛出内存溢出异常。在 JDK 1.2 之后,提供了 SoftReference 类来实现软引用。
  • 弱引用也是用来描述非必需对象的,但是它的强度比软引用更弱一些,被弱引用关联的对象只能生存到下一次垃圾收集发生之前。当垃圾收集器工作时,无论当前内存是否足够,都会回收掉只被弱引用关联的对象。在 JDK 1.2 之后,提供了 WeakReference 类来实现弱引用。
  • 虚引用也称为幽灵引用或者幻影引用,它是最弱的一种引用关系。一个对象是否有虚引用的存在,完全不会对其生存时间构成影响,也无法通过虚引用来取得一个对象实例。为一个对象设置虚引用关联的唯一目的就是能在这个对象被收集器回收时收到一个系统通知。在 JDK 1.2 之后,提供了 PhantomReference 类来实现虚引用。

生存 Or 死亡

即使在可达性分析算法中不可达的对象,也并非是“非死不可”的,这时候它们暂时处于“缓刑”阶段,要真正宣告一个对象死亡,至少要经历两次标记过程:

  • 如果对象在进行可达性分析后发现没有与 GC Roots 相连接的引用链,那它将会被第一次标记并且进行一次筛选,筛选的条件是此对象是否有必要执行 finalize() 方法。当对象没有覆盖 finalize() 方法,或者 finalize() 方法已经被虚拟机调用过,虚拟机将这两种情况都视为“没有必要执行”。
  • 如果这个对象被判定为有必要执行 finalize() 方法,那这个对象将会放置在一个叫做 F-Queue 的队列之中,并在稍后由一个由虚拟机自动建立的、低优先级的 Finalize 线程去执行它。

finalize() 方法是对象逃脱死亡命运的最后一次机会,GC 将会对 F-Queue 中的对象进行第二次小规模的标记,对象只要重新与引用链上的任何一个对象建立关联才能拯救自己。

注意:任何一个对象的 finalize() 方法都只会被系统自动调用一次。

回收方法区

永久代的垃圾收集主要回收两部分内容:废弃常量和无用的类。

类需要同时满足下面 3 个条件才能算是“无用的类”:

  • 该类所有的实例都已经被回收,也就是 Java 堆中不存在该类的任何实例。
  • 加载该类的 ClassLoader 已经被回收。
  • 该类对应的 java.lang.Class 对象没有在任何地方被引用,无法在任何地方通过反射访问该类的方法。

附上手稿

垃圾收集算法

标记-清除算法

算法分为“标记”和“清除”两个阶段:首先标记出所有需要回收的对象,在标记完成后统一回收所有被标记的对象。

它的不足有两个:一个是效率问题,标记和清除两个过程的效率都不高;另一个是空间问题,标记清除之后会产生大量不连续的内存碎片,空间碎片太多可能会导致以后在程序运行过程中需要分配较大对象时,无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。

复制算法

为了解决效率问题,一种称为“复制”的收集算法出现了,它将可用的内存按容量划分为大小相等的两块,每次只使用其中的一块。当这一块的内存用完了,就将还存活着的对象复制到另外一块上面,然后再把已使用过的内存空间一次清理掉。

标记-整理算法

复制收集算法在对象存活率较高时就要进行较多的复制操作,效率将会变低。

根据老年代的特点,有人提出了这种算法,标记过程还是一样,后续则让所有存活的对象都向一端移动,然后直接清理掉端边界以外的内存。

HotSpot 的算法实现

枚举根节点

可达性分析从 GC Roots 节点找引用链这个操作,如果逐个检查这里面的引用必然会消耗很多时间,且此分析工作必须在一个能确保一致性的快照中进行,即不可以出现分析过程中对象引用关系还在不断变化的情况。所以 GC 进行时必须停顿所有 Java 执行线程。

在 HotSpot 的实现中使用一组称为 OopMap 的数据结构来得知哪些地方存放着对象引用。

安全点

HotSpot 没有为每条指令都生成 OopMap,只是在“特定的位置”记录了这些信息,这些位置称为安全点,即程序执行时并非在所有地方都能停顿下来开始 GC,只有在到达安全点时才能暂停。

安全区域

若是程序没有分配 CPU 时间,这时候线程就无法响应 JVM 的中断请求。如线程处于 Sleep 状态或者 Blocked 状态。这种情况下就需要安全区域来解决。

垃圾收集器

Serial 收集器

Serial 收集器是最基本、发展历史最悠久的收集器。它是一个单线程的收集器,进行垃圾收集时必须暂停其他所有的工作线程,直到它收集结束。

ParNew 收集器

ParNew 收集器其实就是 Serial 收集器的多线程版本。

Parallel Scavenge 收集器

Parallel Scavenge 收集器的目的是达到一个可控制的吞吐量。吞吐量就是 CPU 用于运行用户代码的时间与 CPU 总消耗时间的比值,即吞吐量 = 运行用户代码时间 /(运行用户代码时间 + 垃圾收集时间)。

Serial Old 收集器

Serial Old 是 Serial 收集器的老年代版本,同样是一个单线程收集器。

Parallel Old 收集器

Parallel Old 是 Parallel Scavenge 收集器的老年代版本,使用多线程和“标记-整理”算法。

CMS 收集器

CMS(Concurrent Mark Sweep)收集器是一种以获取最短回收停顿时间为目标的收集器。

CMS 收集器是基于“标记-清除”算法实现的,它的运作过程相对于前面几种收集器来说更复杂一些,整个过程分为 4 个步骤:

  • 初始标记(CMS initial mark)
  • 并发标记(CMS concurrent mark)
  • 重新标记(CMS remark)
  • 并发清除(CMS concurrent sweep)

CMS 有以下 3 个明显的缺点:

  • CMS 收集器对 CPU 资源非常敏感。
  • CMS 收集器无法处理浮动垃圾,可能出现“Concurrent Mode Failure”失败而导致另一次 Full GC 的产生。
  • CMS 是基于“标记-清除”算法实现的,收集结束时会产生大量空间碎片。

G1 收集器

G1 是一款面向服务端应用的垃圾收集器。与其他 GC 收集器相比,特点如下:

  • 并行与并发
  • 分代收集
  • 空间整合
  • 可预测的停顿

G1 收集器的运作大致可划分为以下几个步骤:

  • 初始标记(Initial Marking)
  • 并发标记(Concurrent Marking)
  • 最终标记(Final Marking)
  • 筛选回收(Live Data Counting and Evacuation)

附上手稿

内存分配与回收策略

Java 技术体系中所提倡的自动内存管理最终可以归结为自动化地解决两个问题:给对象分配内存以及回收分配给对象的内存。

对象优先在 Eden 分配

大多数情况下,对象在新生代 Eden 区中分配。当 Eden 区没有足够空间进行分配时,虚拟机将发起一次 Minor GC。

大对象直接进入老年代

所谓的大对象是指,需要大量连续内存空间的 Java 对象,最典型的就是很长的字符串以及数组。

长期存活的对象将进入老年代

虚拟机给每个对象定义了一个对象年龄计数器。如果对象在 Eden 出生并经过第一次 Minor GC 后仍然存活,并且能被 Survivor 容纳的话,将被移动到 Survivor 空间中,并且对象年龄设为 1。对象在 Survivor 区中每“熬过”一次 Minor GC,年龄就增加 1 岁,当它的年龄增加到一定程序(默认为 15 岁),就将会被晋升到老年代中。

动态对象年龄判定

如果在 Survivor 空间中相同年龄所有对象大小的总和大于 Survivor 空间的一半,年龄大于或等于该年龄的对象就可以直接进入到老年代。

空间分配担保

新生代使用复制收集算法,为了内存利用率之使用其中一个 Survivor 空间来作为轮换备份,因此当出现大量对象在 Minor GC 后仍然存活的情况,就需要老年代进行分配担保,把 Survivor 无法容纳的对象直接进入老年代。

附上手稿


好困啊……2018-11-20 00:37:02