# /
# 1、什么是装箱、拆箱
装箱是一种封装，是一种设计模式，可称为“装箱模式”。
装箱指基础类型（int、double等）转换为包装类型（Integer、Double等）的过程。
拆箱指从包装类型转换为基础类型的过程。
自动装箱的源码：Integer.valueOf。（见字节码）
自动拆箱的源码：Integer.intValue。（见字节码）
public class Test {
public static void main(String[] args) {
//装箱
Integer integer = new Integer(1);
Integer integer1 = Integer.valueOf(1);
Integer integer2 = 1;
//拆箱
int i = integer.intValue();
int i1 = integer;
//装箱
Boolean aBoolean = new Boolean(true);
Boolean aBoolean1 = Boolean.valueOf(true);
Boolean aBoolean2 = true;
//拆箱
boolean b = aBoolean.booleanValue();
boolean b1 = aBoolean;
//boolean Boolean
//byte Byte
//short Short
//char Character
//int Integer
//long Long
//float Float
//double Double
}
}
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
public class Test1 {
void test(){
Integer i = 1;
int j = i;
}
}
2
3
4
5
6
void test();
descriptor: ()V
flags:
Code:
stack=1, locals=3, args_size=1
0: iconst_1
1: invokestatic #2 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
4: astore_1
5: aload_1
6: invokevirtual #3 // Method java/lang/Integer.intValue:()I
9: istore_2
10: return
LineNumberTable:
line 9: 0
line 10: 5
line 11: 10
LocalVariableTable:
Start Length Slot Name Signature
0 11 0 this Ltemp/Test1;
5 6 1 i Ljava/lang/Integer;
10 1 2 j I
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 2、使用泛型表达一个任意类型
public class Node<T> {
T val;
Node<T> pre;
Node<T> next;
}
2
3
4
5
# 3、包装类型与Object类型的区别？
（1）装箱的过程中，Object类型与包装类型是一样的。
（2）拆箱的过程中，Object类型比包装类型多做一次类型转换检查。（注意：强制类型转换是一次类型转换检查。）
public class Test1 {
void test(){
Integer i = 1;
int j = i;
Object k = 1;
int l = (int) k;
}
}
2
3
4
5
6
7
8
void test();
descriptor: ()V
flags:
Code:
stack=1, locals=5, args_size=1
0: iconst_1
1: invokestatic #2 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
4: astore_1
5: aload_1
6: invokevirtual #3 // Method java/lang/Integer.intValue:()I
9: istore_2
10: iconst_1
11: invokestatic #2 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
14: astore_3
15: aload_3
16: checkcast #4 // class java/lang/Integer
19: invokevirtual #3 // Method java/lang/Integer.intValue:()I
22: istore 4
24: return
LineNumberTable:
line 9: 0
line 10: 5
line 11: 10
line 12: 15
line 13: 24
LocalVariableTable:
Start Length Slot Name Signature
0 25 0 this Ltemp/Test1;
5 20 1 i Ljava/lang/Integer;
10 15 2 j I
15 10 3 k Ljava/lang/Object;
24 1 4 l I
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
# 4、泛型与Object类型的区别？
（1）泛型其实是Object类型。（注意：传参的过程中，会自动装箱。）
（2）装箱、拆箱：泛型与Object类型一样。（见字节码）
public class Test1<T> {
void test(T t){
Integer i = 1;
int j = i;
Object k = 1;
int l = (int) k;//类型转换+拆箱
T a = t;
int b = (Integer) a;//类型转换+拆箱
Integer c = (Integer) t;//类型转换
int d = c;//类型转换+拆箱（字节码中没有再做一次类型转换，直接拆箱）
//int e = (int) t;//不兼容的类型: T无法转换为int
}
public static void main(String[] args) {
Test1<Integer> test1 = new Test1<>();
test1.test(1);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void test(T);
descriptor: (Ljava/lang/Object;)V
flags:
Code:
stack=1, locals=10, args_size=2
0: iconst_1
1: invokestatic #2 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
4: astore_2
5: aload_2
6: invokevirtual #3 // Method java/lang/Integer.intValue:()I
9: istore_3
10: iconst_1
11: invokestatic #2 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
14: astore 4
16: aload 4
18: checkcast #4 // class java/lang/Integer
21: invokevirtual #3 // Method java/lang/Integer.intValue:()I
24: istore 5
26: aload_1
27: astore 6
29: aload 6
31: checkcast #4 // class java/lang/Integer
34: invokevirtual #3 // Method java/lang/Integer.intValue:()I
37: istore 7
39: aload_1
40: checkcast #4 // class java/lang/Integer
43: astore 8
45: aload 8
47: invokevirtual #3 // Method java/lang/Integer.intValue:()I
50: istore 9
52: return
LineNumberTable:
line 9: 0
line 10: 5
line 12: 10
line 13: 16
line 15: 26
line 16: 29
line 18: 39
line 19: 45
line 20: 52
LocalVariableTable:
Start Length Slot Name Signature
0 53 0 this Ltemp/Test1;
0 53 1 t Ljava/lang/Object;
5 48 2 i Ljava/lang/Integer;
10 43 3 j I
16 37 4 k Ljava/lang/Object;
26 27 5 l I
29 24 6 a Ljava/lang/Object;
39 14 7 b I
45 8 8 c Ljava/lang/Integer;
52 1 9 d I
LocalVariableTypeTable:
Start Length Slot Name Signature
0 53 0 this Ltemp/Test1<TT;>;
0 53 1 t TT;
29 24 6 a TT;
Signature: #34 // (TT;)V
public static void main(java.lang.String[]);
descriptor: ([Ljava/lang/String;)V
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=2, args_size=1
0: new #5 // class temp/Test1
3: dup
4: invokespecial #6 // Method "<init>":()V
7: astore_1
8: aload_1
9: iconst_1
10: invokestatic #2 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
13: invokevirtual #7 // Method test:(Ljava/lang/Object;)V
16: return
LineNumberTable:
line 23: 0
line 24: 8
line 25: 16
LocalVariableTable:
Start Length Slot Name Signature
0 17 0 args [Ljava/lang/String;
8 9 1 test1 Ltemp/Test1;
LocalVariableTypeTable:
Start Length Slot Name Signature
8 9 1 test1 Ltemp/Test1<Ljava/lang/Integer;>;
}
Signature: #41 // <T:Ljava/lang/Object;>Ljava/lang/Object;
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
# 5、泛型与Object类型的区别？
（1）装箱：泛型与Object类型一样。（见字节码）
（2）拆箱：泛型与Object类型一样。（见字节码）
public class Main {
public static void main(String[] args) {
Node<Integer> n1 = new Node<>();
NodeObject n2 = new NodeObject();
n1.val = 1;
n2.val = 2;
int a1 = n1.val;
int a2 = (int) n2.val;
}
static class Node<T> {
T val;
Node<T> pre;
Node<T> next;
}
static class NodeObject {
Object val;
NodeObject pre;
NodeObject next;
}
}
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
public static void main(java.lang.String[]);
descriptor: ([Ljava/lang/String;)V
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=5, args_size=1
0: new #2 // class Main$Node
3: dup
4: invokespecial #3 // Method Main$Node."<init>":()V
7: astore_1
8: new #4 // class Main$NodeObject
11: dup
12: invokespecial #5 // Method Main$NodeObject."<init>":()V
15: astore_2
16: aload_1
17: iconst_1
18: invokestatic #6 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
21: putfield #7 // Field Main$Node.val:Ljava/lang/Object;
24: aload_2
25: iconst_2
26: invokestatic #6 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
29: putfield #8 // Field Main$NodeObject.val:Ljava/lang/Object;
32: aload_1
33: getfield #7 // Field Main$Node.val:Ljava/lang/Object;
36: checkcast #9 // class java/lang/Integer
39: invokevirtual #10 // Method java/lang/Integer.intValue:()I
42: istore_3
43: aload_2
44: getfield #8 // Field Main$NodeObject.val:Ljava/lang/Object;
47: checkcast #9 // class java/lang/Integer
50: invokevirtual #10 // Method java/lang/Integer.intValue:()I
53: istore 4
55: return
LineNumberTable:
line 4: 0
line 5: 8
line 7: 16
line 8: 24
line 10: 32
line 11: 43
line 13: 55
LocalVariableTable:
Start Length Slot Name Signature
0 56 0 args [Ljava/lang/String;
8 48 1 n1 LMain$Node;
16 40 2 n2 LMain$NodeObject;
43 13 3 a1 I
55 1 4 a2 I
LocalVariableTypeTable:
Start Length Slot Name Signature
8 48 1 n1 LMain$Node<Ljava/lang/Integer;>;
}
SourceFile: "Main.java"
InnerClasses:
static #13= #4 of #11; //NodeObject=class Main$NodeObject of class Main
static #15= #2 of #11; //Node=class Main$Node of class Main
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
# 6、protobuf
# protobuf编码
protobuf采用TLV(tag-length-value)编码格式。
tag表示字段的唯一标识。 length表示value的长度，可选（非必须）。 value表示数据本身的内容。
# WireType介绍
# Varint类型（变长）
Varint类型的值采用变长编码。
# Length-delimited类型（定长）
String类型的值采用UTF-8变长编码。如果字段都是字符串，则性能提升不大。
China -> 67 104 105 110 97
中国人 -> 228 184 173 229 155 189 228 186 186
2
# 7、Bitmap
bitmap使用场景：1、一亿用户周签到。2、一亿用户年登录状态。3、百亿QQ去重。
# 统计某个用户全年的登录日期
统计某个用户全年的登录日期。每个用户占用365位空间，1表示登录，0表示未登录。
365/8=45.625。
1个用户占用46字节。
1百万用户占用46字节*1百万=46m。
1亿用户占用46字节*1亿=4600m。
echo flushall |redis-cli
#参数1为用户,参数2为日期
#peter第1,7,364天登陆
echo setbit kpeter 1 1 |redis-cli
echo setbit kpeter 7 1 |redis-cli
echo setbit kpeter 364 1 |redis-cli
echo strlen kpeter |redis-cli
#全量,peter登陆数
echo bitcount kpeter |redis-cli
#本周,peter登陆数
echo bitcount kpeter -2 -1 |redis-cli
2
3
4
5
6
7
8
9
10
11
# 统计某一天的登录用户
统计某一天的登录用户。每个用户占用1位空间，1表示登录，0表示未登录。
1个用户占用1位。
1百万用户占用1位*1百万=0.125m。
1亿用户占用1位*1亿=12.5m。
比如：某东618做活动，618前一周有登录的用户送优惠券，要怎么统计？
比如：某多618做活动，618当天登录的用户送公仔，要准备多少礼物？
echo flushall |redis-cli
#参数1为日期,参数2为用户
#用户1,2,3,7登陆
echo setbit 20190101 1 1 |redis-cli
echo setbit 20190101 2 1 |redis-cli
echo setbit 20190102 1 1 |redis-cli
echo setbit 20190102 3 1 |redis-cli
echo setbit 20190110 7 1 |redis-cli
#本天,用户登陆数
echo bitcount 20190101 |redis-cli
#全量,用户登陆数(去重)
echo bitop or ko 20190101 20190102 20190110 |redis-cli
echo strlen ko |redis-cli
echo bitcount ko |redis-cli
#本周,用户登陆数(去重)
echo bitop or ko 20190101 20190102 |redis-cli
echo strlen ko |redis-cli
echo bitcount ko 0 -1 |redis-cli
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 布隆过滤器
数据结构：bitmap位图。
写入：插入一个元素到布隆过滤器时，对元素进行多次哈希，将对应的bit位记为1。
读取：查询一个元素是否存在时，同样对元素进行多次哈希，如果对应的bit位其一为0，则元素一定不存在；如果所有bit位都为1，则元素可能存在（有误判率）。
布隆过滤器位图模式的两个问题：
一个是误报，在查询时只能提供“一定不存在”与“可能存在”，因为不同元素可能被映射到相同bit位上，导致该位置1，那么一个不存在的元素可能会被误报为存在；
一个是漏报，如果删除了某个元素，导致bit位为0，那么本来存在的元素会被漏报成不存在。
漏报是严重问题，所以布隆过滤器不允许删除元素。可以错杀/误报不能放过/漏报。
# 布谷鸟过滤器
数据结构：哈希桶。
写入：插入一个元素时，计算出多个哈希值，在对应的槽位做标记。
读取：查询一个元素是否存在时，计算出对应的哈希值，检查对应的槽位上是否存在标记。
布谷鸟哈希算法：简单的布谷鸟哈希结构是一维数组，一个元素通过两个哈希函数映射到两个index位，（1）如果两个index位有一个空，将元素直接放进去；如果这两个index位都满了，随机踢走一个，自己霸占这个index位。（2）被踢走的元素需要判断自己的另一个index位是否空，如果空，自己挪进去；如果这个index位也被占据，则再将受害者的角色转嫁给这个元素，（3）这个新的受害者继续重复这个过程，直到所有的元素都找到index位。（4）这个过程不能无限重复，如果被踢的次数达到上限，则认为容器已满，插入失败。
布谷鸟过滤器算法：布谷鸟哈希算法是存储元素，布谷鸟过滤器算法是存储标记，所以有误判率。如果标记尽可能唯一（比如取长度160位的sha1(key)的前后32位作为标记），那么误判率会非常低，只是。。
# 9、RoaringBitmap
bitmap结构是数组。如果存储的两个key之间的偏移量为100w，那么bitmap的占用空间为100wbit，浪费大量空间。
RoaringBitmap结构是哈希表/哈希桶。将32位的整型int分为高16位short和低16位short，其中高16位使用数组存储，低16位有三种不同的container可选，ArrayContainer(数组容器)、BitmapContainer(位图容器)、RunContainer(步长容器)。
ArrayContainer：使用short[]存储。存储一个数据占用2字节，至多存储4096个数据，至多占用8kb。（注意：只能表示4096个数字。）
BitmapContainer：使用long[]存储。2^16=65536需要1024个long(64位)组成65536个bit，共占用8kb。（注意：bitmap固定长度为long[1024]，可以表示低16位所有65536个数字。）
RunContainer：使用short[]存储。对于连续出现的数字，只记录初始数字和后续数量。比如，数列9,11,12,13,14,15,21,22表示为[9,0],[11,4],[21,1]；源码使用short[] valueslength存储压缩后的数据。（注意：这个压缩算法与数据的连续性关系密切。连续的100个short，从200字节压缩为4字节，但完全不连续的100个short，反而从200字节变为400字节。）
面试经典150题 →