不为谁而写的博客∎
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
29public 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 | String[] s = {"1","2","3"}; |
3. 匿名类
1 | new Thread(){ |
4. 双括号
通常情况下,初始化Java集合并向其中添加几个元素的步骤如下:1
2
3
4Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(3);
我们也可以在静态区域中向作为静态变量的集合中添加元素:
1 | private static final Set<Integer> set = new HashSet<>(); |
此方法从语法上来看,这样的初始化方法虽然格式清晰明了,但语法上略显冗余。况且只能向“静态变量集合”中添加的约束,而“静态变量集合”只能作为一个类的内部私有属性,如果在”main”方法中便不能用了。
那么,双括号就出现了,也叫反模式
。你可以在”main”中使用:
1 | Set<Integer> set = new HashSet<Integer>() {{ |
也可以在类中,给类集合属性初始化:
1 | public class Main { |
这是比较特殊的用法。一般在做题的时候会遇到,考你的知识点,笔试时见到了不会自闭就够了。但是不建议使用,它可能会出现“内存溢出”的bug。
1 | Map source = new HashMap(){{ |
你可以试一试运行上述代码,表面上简洁的初始化代码,但是,编译器在为每个”双括号“实例化类型都创建了一个类,我们可以查看目录下的.class
文件:
其中带有$
符号的文件,如Main$2$1.class
是什么意思呢? 是Main
下有个匿名类,它管这个匿名类叫”2“,而”2“的下面还有一个匿名类,它管这个匿名类叫”1“。
如此的话,你运行一次没毛病,但是但是如果类似这样的代码存在于一个大型的应用中,这将增加 ClassLoader 一些不必要的负担。所以我们尽量不要为了省事儿,去写双括号的形式。
参考链接
左倾红黑树的渊源
我们都知道,对于BST来说,最致命的缺点莫过于,当插入的键有序时,BST的树高是线性增长的,此时他的get(),put()操作的时间复杂度都是N,为了解决这个问题,就有了AVL(平衡二叉树,不在此篇讨论范围)的平衡操作(左旋,右旋)来保证树左右子树的平衡。那么,明明AVL看上去已经完美的结构,为什么还会冒出红黑树呢?因为,AVL也还是有缺点:插入时太多的平衡操作也会影响插入时的性能。我只是定性的提了提,定量的分析可以参考其他文献资料。而红黑树的插入操作所带来的平衡操作相对更少,从而更加高性能的插入,但是带来的负面结果便是树的高度有所增加:叶子节点到根节点的最长路径<=2*叶子节点到根节点的最短路径。可以说红黑树是更加折策略中的结果。
在《算法》(第4版)中,红黑树的实现直接采用了左倾红黑树的方法,左倾红黑树可以用更少的代码量实现红黑树,我也便使用他的方法理解。
2-3-4树和左倾红黑树的等价转换
我们把树中的链分为3种类型:
红链接连接两个2-节点构成一个3-节点
黑链接则是2-3树中的普通连接。
第三种,类型会临时出现,稳定的2-3树不会出现,2-3-4中会出现,它是4-节点
这么一来,我们便可以用一棵BST来代表2-3-4树了。
但是有个问题,对于三节点的表示,有两种表示方法,一种是红链左倾,另一种是红链右倾,所以要考虑很多种情况,但是我们只考虑左倾的情况,也就是对于3-节点,我们只有下图一种转换关系:
构成的树也称左倾红黑树(Left-Leaning Red-Black Trees),如下图:
不允许出现的情况
右倾的3-节点
两个红链接首尾相连
Java左倾红黑树的数据结构
1 | public class BST<Key extends Comparable<Key>, Value> |
除了红黑树的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
19private 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
12private 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
12private 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底部插入一个新的节点
- 把添加的新节点的color设为红色。
- 如果有必要的话,执行旋转操作。其中的有必要是指哪些情况呢?就是上文
不允许出现的情况
。转换关系如下图:
把4-节点分解
这个很好实现,把两个子节点的颜色改为黑,父节点的颜色改成红色即可。
书上的实现是这样的:1
2
3
4
5private void flipColors(Node h){
h.left.color = BLACK;
h.right.color = BLACK;
h.color = RED;
}
但是论文上的实现更加统一,也避免了再添加一个逆操作函数(在删除节点操作中,子节点颜色改为红,父节点颜色改为黑),1
2
3
4
5
6
7private Node colorFlip(Node h)
{
x.color = !x.color;
x.left.color = !x.left.color;
x.right.color = !x.right.color;
return x;
}
在LLRB中分解4-节点
- 分解4-节点,红链接会上升一个level
- 如果有必要,则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
JWT介绍
什么是JWT(Json Web Token)
详情请见jwt官网.直观来讲,它是一个格式为形如aaaa.bbbb.cccc
的字符串token,它存放了登录用户的信息,也是用户登录网站的凭证。
为什么要用JWT?
当我们登录了一个网站,然后因为手头有急事把浏览器关闭转而做其他事,但你不用担心下次重新打开浏览器后网站已经失去了登录状态(前提是你间隔的时间没有大于jwt的过期时间),这很方便。当然你会说,Session也可以实现这个功能,But在使用Session的同时,会增加服务器的存储压力,而JWT是将存储的压力分布到各个客户端,减轻服务器的压力。
JWT长什么样
JWT由三个子字符串组成
- Header(头部)
- Payload(负载)
- Signature(签名)
写成一行,就是这个样子:Header.Payload.Signature
- Header
Header是由一下这个格式的Json通过Base64编码生成的字符串(注意:Base64编码不是加密,加密一般不可破解,编码可以通过用编码反编码或得原来的Json数据,因此不安全,所以不存放敏感信息),Header中存放的内容是说明编码对象是一个JWT以及使用“SHA-256”的算法进行加密(加密用于生成Signature签名)
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 | { |
- Signature
Signature 是由Header和Payload组合而成,将Header和Claim这两个Json分别使用Base64方式进行编码,生成字符串Header和Payload,然后将Header和Payload以Header.Payload的格式组合在一起形成一个字符串,然后使用Header里指定的签名算法和一个密匙(这个secret存放在服务器上,用于进行验证)对这个字符串进行加密,形成一个新的字符串,公式如下
1 | HMACSHA256( |
SpringBoot使用JWT
SpringBoot整合JWT的方式有很多,也有第三方的库,比如auth0,但是我们不使用。我们最终需要实现两个功能,一个是实现用户登录(Authentication),另一个是用户授权(Authenrization)。工程目录结构如下:
1 | . |
- JwtCfg类
这个类中声明了一个@Bean ,用于生成一个过滤器类,对/api 链接下的所有资源访问进行JWT的验证
1 | /** |
- JwtFilter类
这个类声明了一个JWT过滤器类,从Http请求中提取JWT的信息,并使用了”secretkey”这个密匙对JWT进行验证
1 | /** |
UserController类,用户的注册和登录。
1 | /** |
- jwt工具类
1 | /** |
- ProductController类,测试JWT功能,只有当用户认证成功之后,
/api
下的资源才能被访问。
1 | /** |
代码功能测试
- 首先直接访问
/api
下的product资源,毫无疑问是不能访问的。 - 然后进行一个新的测试用户的注册,可以看到注册成功的提示返回
- 再让该用户进行登录,可以看到登录成功之后返回的JWT字符串
- 最后用获取到的JWT作为访问令牌,申请访问/api/products,可以访问成功。
参考链接:
https://jwt.io/
http://www.ruanyifeng.com/blog/2018/07/json_web_token-tutorial.html
https://blog.csdn.net/ltl112358/article/details/79507148
官网文档链接
https://git-scm.com/docs
在官网可以找到一个非常生动有趣的的git教程,简直不要太容易理解哦😌http://ndpsoftware.com/git-cheatsheet.html