Do it now - sometimes LATER becomes NEVER.
post @ 2019-04-04

1. 关于gitalk

Gitalk 是一个基于 Github Issue 和 Preact 开发的评论插件。使用 Github 帐号登录,界面干净整洁,也支持 MarkDown语法。

Read More
post @ 2019-03-15

1. 作用域

“作用域”很常用,所以不用再讲了。。。吗?

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
public class A extends B {
{ // 局部作用域
int a = 233;
}
private static int a;
static {
System.out.println("The initial value of a is " + a);
}
public static void fun(){
System.out.println("The is a function from A.");
}
public A() {
System.out.println("This is A, over.");
}

public static void main(String[] args) {
A a1 = new A();
B b1 = new A();
}
}
class B {
static {
System.out.println("Hello, I am B");
}

B() {
System.out.println("This is B, over.");
}
}

如果你能正确写出上述代码执行后的结果,那么确实不用看了。反之,你没有掌握。至于结果是什么,自己跑一跑便知。在这串代码中,在A类中有个局部作用域,在A,B中各自含有一个static静态区域。

其中,局部作用域中的代码是不会影响局部作用域外的private static int a的,而在类加载后,会将a初始化成0。

static静态区,类会在加载时编译,因此在实例化之前,就会输出。

2. 初始化数组

没什么的好讲的。

1
2
String[]   s = {"1","2","3"};
String[][] s = {{"1","2"},{"3","4"}};

3. 匿名类

1
2
3
4
new Thread(){
public void run(){
}
}.start();

4. 双括号

通常情况下,初始化Java集合并向其中添加几个元素的步骤如下:

1
2
3
4
Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(3);

我们也可以在静态区域中向作为静态变量的集合中添加元素:

1
2
3
4
5
6
private static final Set<Integer> set = new HashSet<>();
static {
set.add(1);
set.add(2);
set.add(3);
}

此方法从语法上来看,这样的初始化方法虽然格式清晰明了,但语法上略显冗余。况且只能向“静态变量集合”中添加的约束,而“静态变量集合”只能作为一个类的内部私有属性,如果在”main”方法中便不能用了。

那么,双括号就出现了,也叫反模式。你可以在”main”中使用:

1
2
3
4
5
Set<Integer> set = new HashSet<Integer>() {{
add(1);
add(2);
add(3);
}};

也可以在类中,给类集合属性初始化:

1
2
3
4
5
6
7
8
public class Main {
private static final Set<String> stringSet = new HashSet<>(){{
add("I");
add("am");
add("stringSet");
}};
// ...others
}

这是比较特殊的用法。一般在做题的时候会遇到,考你的知识点,笔试时见到了不会自闭就够了。但是不建议使用,它可能会出现“内存溢出”的bug。

1
2
3
4
5
6
7
8
9
10
11
12
Map source = new HashMap(){{
put("firstName", "John");
put("lastName", "Smith");
put("organizations", new HashMap(){{
put("0", new HashMap(){{
put("id", "1234");
}});
put("abc", new HashMap(){{
put("id", "5678");
}});
}});
}};

你可以试一试运行上述代码,表面上简洁的初始化代码,但是,编译器在为每个”双括号“实例化类型都创建了一个类,我们可以查看目录下的.class文件:
TwoBraces.png

其中带有$符号的文件,如Main$2$1.class是什么意思呢? 是Main下有个匿名类,它管这个匿名类叫”2“,而”2“的下面还有一个匿名类,它管这个匿名类叫”1“。

如此的话,你运行一次没毛病,但是但是如果类似这样的代码存在于一个大型的应用中,这将增加 ClassLoader 一些不必要的负担。所以我们尽量不要为了省事儿,去写双括号的形式。

参考链接

http://www.importnew.com/15087.html

Read More
post @ 2019-03-12

思维导图

Java枚举/JavaEnum.png

Read More
post @ 2019-03-11

mind

Read More
post @ 2019-03-02

Java String类

字符串在java编程中应用广泛,有必要深入的了解一下。

创建字符串

java的String对象有2种创建方式:

  • 字面值对象
  • 构造方法创建对象。
Read More
post @ 2019-02-24

左倾红黑树的渊源

我们都知道,对于BST来说,最致命的缺点莫过于,当插入的键有序时,BST的树高是线性增长的,此时他的get(),put()操作的时间复杂度都是N,为了解决这个问题,就有了AVL(平衡二叉树,不在此篇讨论范围)的平衡操作(左旋,右旋)来保证树左右子树的平衡。那么,明明AVL看上去已经完美的结构,为什么还会冒出红黑树呢?因为,AVL也还是有缺点:插入时太多的平衡操作也会影响插入时的性能。我只是定性的提了提,定量的分析可以参考其他文献资料。而红黑树的插入操作所带来的平衡操作相对更少,从而更加高性能的插入,但是带来的负面结果便是树的高度有所增加:叶子节点到根节点的最长路径<=2*叶子节点到根节点的最短路径。可以说红黑树是更加折策略中的结果。

在《算法》(第4版)中,红黑树的实现直接采用了左倾红黑树的方法,左倾红黑树可以用更少的代码量实现红黑树,我也便使用他的方法理解。

2-3-4树和左倾红黑树的等价转换

我们把树中的链分为3种类型:

  1. 红链接连接两个2-节点构成一个3-节点

  2. 黑链接则是2-3树中的普通连接。

  3. 第三种,类型会临时出现,稳定的2-3树不会出现,2-3-4中会出现,它是4-节点

    这么一来,我们便可以用一棵BST来代表2-3-4树了。

    但是有个问题,对于三节点的表示,有两种表示方法,一种是红链左倾,另一种是红链右倾,所以要考虑很多种情况,但是我们只考虑左倾的情况,也就是对于3-节点,我们只有下图一种转换关系:

    构成的树也称左倾红黑树(Left-Leaning Red-Black Trees),如下图:

不允许出现的情况

  • 右倾的3-节点

  • 两个红链接首尾相连

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
public class BST<Key extends Comparable<Key>, Value>
{
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root;
private class Node
{
Key key;
Value val;
Node left, right;
boolean color;
Node(Key key, Value val, boolean color)
{
this.key = key;
this.val = val;
this.color = color;
}
}
public Value get(Key key)
// Search method.
public void put(Key key, Value val)
// Insert method.
public void delMax(Key key)
}
private boolean isRed(Node x)
{
if (x == null)
return false;
return (x.color == RED);
}

除了红黑树的put(),delete(),delMax(),delMin()这些涉及到节点颜色的操作之外,如get(),rank
(),max(),min(),floor(),ceiling()都是和BST一样的,一行都不用改,原因是红黑树本质上是一棵BST,所以说红黑树的确是个伟大的发明👍。

红黑树的插入

红黑树的插入是一个比较复杂的操作,使用递归实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private Node put(Node x, Key key, Value val){
// 从Node x 开始put
// 如果存在key,在更新key所在节点的val
// 否则新建一个叶子节点
if (x == null) return new Node(key,val,1);
int cmp = key.compareTo(x.key);
if (cmp < 0){
return put(x.left,key,val);
}
else if (cmp > 0){
return put(x.right,key,val);
}
else{
x.val = val;
}
// 更新子树的节点个数
x.N = x.left.N + x.right.N + 1;
return x;
}

平衡红黑树操作

在红黑树中只需要维护黑链接的平衡,只需要对红色的链接进行旋转操作,这俩是基本的工具方法,很多地方都要用到,所以封装成两个私有的内部方法。

1
2
3
4
5
6
7
8
9
10
11
12
private Node rotateLeft(Node h){
// 向左旋转
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
// 更新节点计数器 todo 此处略有不熟
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
return x;
}


1
2
3
4
5
6
7
8
9
10
11
12
private Node rotateRight(Node h){
// 向右旋转,与向左相反
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
// 更新节点计数器 todo 此处略有不熟
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
return x;
}

在LLRBtree底部插入一个新的节点

  1. 把添加的新节点的color设为红色。
  2. 如果有必要的话,执行旋转操作。其中的有必要是指哪些情况呢?就是上文不允许出现的情况。转换关系如下图:

把4-节点分解

这个很好实现,把两个子节点的颜色改为黑,父节点的颜色改成红色即可。

书上的实现是这样的:

1
2
3
4
5
private void flipColors(Node h){
h.left.color = BLACK;
h.right.color = BLACK;
h.color = RED;
}

但是论文上的实现更加统一,也避免了再添加一个逆操作函数(在删除节点操作中,子节点颜色改为红,父节点颜色改为黑),

1
2
3
4
5
6
7
private Node colorFlip(Node h)
{
x.color = !x.color;
x.left.color = !x.left.color;
x.right.color = !x.right.color;
return x;
}

在LLRB中分解4-节点

  1. 分解4-节点,红链接会上升一个level
  2. 如果有必要,则rotate。
  • 当父节点是2-节点时
  • 当父节点是3-节点时

LLRT的插入算法


这里代码的执行顺序是很重要的。
比如如果我们把colorfilp移到最后,那么会出现什么情况?
由于每次在最后都将4-node 进行color flip了,那么自然红黑树中不存在4-node了,所以就变成了2-3树的红黑树,这也是书本上的结果。

LLBT节点的删除

删除最大节点

参考链接:

https://blog.csdn.net/bytxl/article/details/40920165
http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
https://cloud.tencent.com/developer/article/1193097

Read More

JWT介绍

什么是JWT(Json Web Token)

详情请见jwt官网.直观来讲,它是一个格式为形如aaaa.bbbb.cccc的字符串token,它存放了登录用户的信息,也是用户登录网站的凭证。

为什么要用JWT?

当我们登录了一个网站,然后因为手头有急事把浏览器关闭转而做其他事,但你不用担心下次重新打开浏览器后网站已经失去了登录状态(前提是你间隔的时间没有大于jwt的过期时间),这很方便。当然你会说,Session也可以实现这个功能,But在使用Session的同时,会增加服务器的存储压力,而JWT是将存储的压力分布到各个客户端,减轻服务器的压力。

JWT长什么样

JWT由三个子字符串组成

  • Header(头部)
  • Payload(负载)
  • Signature(签名)

写成一行,就是这个样子:Header.Payload.Signature

  1. Header

Header是由一下这个格式的Json通过Base64编码生成的字符串(注意:Base64编码不是加密,加密一般不可破解,编码可以通过用编码反编码或得原来的Json数据,因此不安全,所以不存放敏感信息),Header中存放的内容是说明编码对象是一个JWT以及使用“SHA-256”的算法进行加密(加密用于生成Signature签名)

1
2
3
4
{
"alg": "HS256",
"typ": "JWT"
}
  1. Payload

虽然第二部分官网上写的是Payload,但你要认识到Payload是base64编码得到的字符串,编码之前它是个Json格式的数据,我们把它称作Claim,也就是Claim---Base64编码-->Payload.这也很好理解,那Claim里存放的是什么数据呢,它存放JWT自身的标准属性,所有的标准属性都是可选的,比如有:

  • “iss”:”Issuer —— 签发人”,
  • “sub”:”Subject —— 主题”,
  • “aud”:”Audience —— 受众”,
  • “exp”:”Expiration Time —— 过期时间”,
  • “nbf”:”Not Before —— 生效时间”,
  • “iat”:”Issued At —— 签发时间”,
  • “jti”:”JWT ID —— 编号”

除了以上的JWT官方标准属性,你还可以在这个部分添加自定义字段,以下的例子中admin即自定义字段。

1
2
3
4
5
{
"sub": "1234567890",
"name": "John Doe",
"admin": true
}
  1. Signature

Signature 是由Header和Payload组合而成,将Header和Claim这两个Json分别使用Base64方式进行编码,生成字符串Header和Payload,然后将Header和Payload以Header.Payload的格式组合在一起形成一个字符串,然后使用Header里指定的签名算法和一个密匙(这个secret存放在服务器上,用于进行验证)对这个字符串进行加密,形成一个新的字符串,公式如下

1
2
3
4
HMACSHA256(
base64UrlEncode(header) + "." +
base64UrlEncode(payload),
secret)

SpringBoot使用JWT

SpringBoot整合JWT的方式有很多,也有第三方的库,比如auth0,但是我们不使用。我们最终需要实现两个功能,一个是实现用户登录(Authentication),另一个是用户授权(Authenrization)。工程目录结构如下:

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
.
└── src
├── main
│   ├── java
│   │   └── com
│   │   └── bababadboy
│   │   ├── dealermng
│   │   │   ├── Application.java
│   │   │   ├── config
│   │   │   │   ├── SecurityConfig.java
│   │   │   │   └── WebMvcConfigurer.java
│   │   │   ├── controller
│   │   │   │   ├── ProductController.java
│   │   │   │   └── UserController.java
│   │   │   ├── dto
│   │   │   │   └── UserDataDTO.java
│   │   │   ├── entity
│   │   │   │   ├── Product.java
│   │   │   │   └── user
│   │   │   │   ├── Role.java
│   │   │   │   └── User.java
│   │   │   ├── repository
│   │   │   │   ├── ProductRepository.java
│   │   │   │   └── UserRepository.java
│   │   │   ├── security
│   │   │   │   ├── JwtCfg.java
│   │   │   │   ├── JwtFilter.java
│   │   │   │   ├── JwtTokenFilterConfigurer.java
│   │   │   │   ├── JwtTokenProvider.java
│   │   │   └── service
│   │   │   ├── ProductService.java
│   │   │   └── impl
│   │   │   ├── ProductServiceImpl.java
│   │   │   └── UserService.java
│   │   └── springboot1
│   └── resources
——...
  • JwtCfg类
    这个类中声明了一个@Bean ,用于生成一个过滤器类,对/api 链接下的所有资源访问进行JWT的验证
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @author wangxiaobin
*/
@Configuration
public class JwtCfg {
@Bean
public FilterRegistrationBean<JwtFilter> jwtFilter() {
FilterRegistrationBean<JwtFilter> registrationBean;
registrationBean = new FilterRegistrationBean<JwtFilter>();
registrationBean.setFilter(new JwtFilter());
registrationBean.addUrlPatterns("/api/*");

return registrationBean;
}
}
  • JwtFilter类
    这个类声明了一个JWT过滤器类,从Http请求中提取JWT的信息,并使用了”secretkey”这个密匙对JWT进行验证
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
/**
* 从Http请求中提取JWT的信息,并使用了”secretkey”这个密匙对JWT进行验证
* @author wangxiaobin
*/
public class JwtFilter extends GenericFilterBean {
public void doFilter(final ServletRequest req, final ServletResponse res, final FilterChain chain)
throws IOException, ServletException {

// Change the req and res to HttpServletRequest and HttpServletResponse
final HttpServletRequest request = (HttpServletRequest) req;
final HttpServletResponse response = (HttpServletResponse) res;

// Get authorization from Http request
final String authHeader = request.getHeader("authorization");

// If the Http request is OPTIONS then just return the status code 200
// which is HttpServletResponse.SC_OK in this code
if ("OPTIONS".equals(request.getMethod())) {
response.setStatus(HttpServletResponse.SC_OK);

chain.doFilter(req, res);
}
// Except OPTIONS, other request should be checked by JWT
else {

// Check the authorization, check if the token is started by "Bearer "
if (authHeader == null || !authHeader.startsWith("Bearer ")) {
throw new ServletException("Missing or invalid Authorization header");
}

// Then get the JWT token from authorization
final String token = authHeader.substring(7);

try {
// Use JWT parser to check if the signature is valid with the Key "secretkey"
// 使用了”secretkey”这个密匙对JWT进行验证
final Claims claims = Jwts.parser().setSigningKey("secretkey").parseClaimsJws(token).getBody();

// Add the claim to request header
request.setAttribute("claims", claims);
} catch (final SignatureException e) {
throw new ServletException("Invalid token");
}

chain.doFilter(req, res);
}
}
}

UserController类,用户的注册和登录。

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
/**
* @author wangxiaobin
*/
@RestController
@RequestMapping("/users")
public class UserController {

private final UserService userService;
private final ModelMapper modelMapper;

@Autowired
public UserController(UserService userService, ModelMapper modelMapper) {
this.userService = userService;
this.modelMapper = modelMapper;
}

@PostMapping("/signup")
public String signUp(@RequestBody User user) {
return userService.signUp(user);
}

@PostMapping("/login")
public Object logIn(@RequestParam String username,@RequestParam String password){
String token = userService.logIn(username,password);
UserDataDTO info = modelMapper.map(userService.search(username),UserDataDTO.class);
JSONObject result = new JSONObject();
result.put("userMsg",info);
result.put("accessToken",token);
return JSON.toJSON(result);
}
}
  • jwt工具类
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
66
67
68
69
70
71
72
73
/**
* @author wangxiaobin
*/
@Component
public class JwtTokenProvider {
/**
* THIS IS NOT A SECURE PRACTICE! For simplicity, we are storing a static key here. Ideally, in a
* microservices environment, this key would be kept on a config-server.
*/
@Value("${security.jrwt.token.secret-key:secret-key}")
private String secretKey;

@Value("${security.jwt.token.expire-length:3600000}")
private long validityInMilliseconds = 3600000; // 1h

@Autowired
private MyUserDetails myUserDetails;

@PostConstruct
protected void init() {
secretKey = Base64.getEncoder().encodeToString(secretKey.getBytes());
}

/**
* 生成jwt
*/
public String createToken(String username, List<Role> roles) {

Claims claims = Jwts.claims().setSubject(username);
claims.put("auth", roles.stream().map(s -> new SimpleGrantedAuthority(s.getAuthority())).filter(Objects::nonNull).collect(Collectors.toList()));

Date now = new Date();
Date validity = new Date(now.getTime() + validityInMilliseconds);

return Jwts.builder()//
.setClaims(claims)//
.setIssuedAt(now)//
.setExpiration(validity)//
.signWith(SignatureAlgorithm.HS256, "secretkey")//
.compact();
}

public Authentication getAuthentication(String token) {
UserDetails userDetails = myUserDetails.loadUserByUsername(getUsername(token));
return new UsernamePasswordAuthenticationToken(userDetails, "", userDetails.getAuthorities());
}

public String getUsername(String token) {
return Jwts.parser().setSigningKey(secretKey).parseClaimsJws(token).getBody().getSubject();
}


/**
* 分解request,获取token
*/
public String resolveToken(HttpServletRequest req) {
String bearerToken = req.getHeader("Authorization");
if (bearerToken != null && bearerToken.startsWith("Bearer ")) {
return bearerToken.substring(7, bearerToken.length());
}
return null;
}

public boolean validateToken(String token) {
try {
Jwts.parser().setSigningKey(secretKey).parseClaimsJws(token);
return true;
} catch (JwtException | IllegalArgumentException e) {
throw new CustomException("Expired or invalid JWT token", HttpStatus.INTERNAL_SERVER_ERROR);
}
}

}
  • ProductController类,测试JWT功能,只有当用户认证成功之后,/api下的资源才能被访问。
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
/**
* 描述:
* Product控制器
*
* @author wangxiaobin
*/
@Transactional
@RestController
@RequestMapping(value = "/api")
public class ProductController{
private final ProductRepository productRepository;
private final ProductServiceImpl productService;

@Autowired
public ProductController(ProductRepository productRepository, ProductServiceImpl productService) {
this.productRepository = productRepository;
this.productService = productService;
}
/**
* 产品列表分页查询
*/
@RequestMapping(value = "/products",method = RequestMethod.GET)
public Object retrieveAllProducts(@RequestParam(value = "page", defaultValue = "0") Integer page ,
@RequestParam(value = "size", defaultValue = "15") Integer size){
return JSON.toJSON(productService.findProductNoCriteria(page,size).getContent());
}

/**
* 根据产品编号"no"查询商品详情
*/
@GetMapping(value = "/products/{no}")
public Object retrieveProduct(@PathVariable("no") String no) {
Optional<Product> product = productService.retrieveProduct(no);
return JSON.toJSON(product);
}
}

代码功能测试

  1. 首先直接访问/api下的product资源,毫无疑问是不能访问的。
    500
  2. 然后进行一个新的测试用户的注册,可以看到注册成功的提示返回

signup

  1. 再让该用户进行登录,可以看到登录成功之后返回的JWT字符串

login

  1. 最后用获取到的JWT作为访问令牌,申请访问/api/products,可以访问成功。

get

参考链接:
https://jwt.io/
http://www.ruanyifeng.com/blog/2018/07/json_web_token-tutorial.html
https://blog.csdn.net/ltl112358/article/details/79507148

Read More
post @ 2018-11-24

Read More
post @ 2018-11-24

Read More
post @ 2018-11-18
git日记

git
官网文档链接
https://git-scm.com/docs
在官网可以找到一个非常生动有趣的的git教程,简直不要太容易理解哦😌http://ndpsoftware.com/git-cheatsheet.html

1. 在Mac OS上使用git删除.DS_Store

.DS_Store是什么

Read More
⬆︎TOP