老马说编程
2020-11-19 本文已影响0人
neo已经被使用
1.程序大概是怎么回事
计算机 = CPU+内存+硬盘+输入输出设备
2.赋值
char是两个字节！！！
数字常量默认是int类型，所以超过int长度的数字给long赋值时需要加L。eg：long a = 3232323232L
小数常量默认是double类型，所以float类型应该加f。eg：float f = 33.3f
也可以把整数直接赋值给float或double。eg：float f = 33; double d= 33333333333L
一个基本类型变量，内存中只会有一块对应的内存空间。但是数组或者对象会有两块，一块用于存储数组内容本身，另一块用于存储内容的位置eg：
| 代码 | 内存地址 | 内存数据 |
|---|---|---|
| int a = 100; | 1000 | 100 |
| int arr = {1,2,3} | 2000 | 3000 |
| 3000 | 1 | |
| 3004 | 2 | |
| 3008 | 3 |
为什么数组要用两块空间？
int[] aarA = {1,2,3}
int[] aarB = {4,5,6,7}
aarA = aarB;
这个代码中，arrA初始的长度是3，arrB的长度是4，后来将arrB的值赋给了arrA。如果arrA对应的内存空间是直接存储的数组内容，
那么它将没有足够的空间去容纳arrB的所有元素
用两块空间存储，这个就简单的多，arrA存储的值就变成了和arrB的一样，存储的都是数组内容{4,5,6,7}的地址，此后访问arrA就和arrB是一样的了，
而arrA {1,2,3}的内存空间由于无人引用会被垃圾回收，如下图所示：
arrA {1,2,3}
\
\
arrB -> {4,5,6,7}
4.整数的二进制表示与位运算
负数是以补码（取反+1）的形式表示的。对于byte单位eg：
-1：1的原码表示是00000001，取反是11111110，然后再加1，就是11111111。
-2：2的原码表示是00000010，取反是11111101，然后再加1，就是11111110
-127：127的原码表示是01111111，取反是10000000，然后再加1，就是10000001
byte类型，正数最大表示是01111111，即127，负数最大表示是10000000，即-128，表示范围就是 -128到127。其他类型的整数也类似，负数能多表示一个数
负数为什么要以补码表示？因为只有这种做法才能实现正确的加减法
计算机其实只能做加法，1-1其实是1+(-1)。如果用原码表示，计算结果是不对的。比如说：
1 -> 00000001
-1 -> 10000001
+ ------------------
-2 -> 10000010
用原码表示，1-1的结果是-2。
如果是补码表示：
1 -> 00000001
-1 -> 11111111
+ ------------------
0 -> 00000000
结果是正确的。
所以对于byte数据127+1 = -128 也就是这个原因
16进制：将四个二进制位简化为一个0到15的数，10到15用字符A到F表示。eg：1010 ---> A
Java中不支持直接写二进制常量，比如，想写二进制形式的11001，Java中不能直接写，可以在前面补0，补足8位，为00011001，然后用16进制表示，即 0x19
Integer.toBinaryString()//二进制
Integer.toHexString()//十六进制
无符号右移 >>>
有符号右移>>
5.小数计算为什么会错？
float f = 0.1f*0.1f;
System.out.println(f);
上面计算结果应该是0.01，但是实际上屏幕输出却是0.010000001，后面多了个1。原因如下：
计算机是用一种二进制格式存储小数的，这个二进制格式不能精确表示0.1，它只能表示一个非常接近0.1但又不等于0.1的一个数
小数点后面的权重为：10^-1 、10^-2、10^-3...
- 如何从乱码中恢复 (上)
ASCILL码：计算机发明之初没有考虑那么多，基本上只考虑了美国的需求，美国大概只需要128个字符，美国就规定了这128个字符的二进制表示方法
128个字符用7个位刚好可以表示，计算机存储的最小单位是byte，即8位，ASCII码中最高位设置为0，用剩下的7位表示字符
Ascii码对美国是够用了，但对别的国家而言却是不够的，于是，各个国家的各种计算机厂商就发明了各种各种的编码方式以表示自己国家的字符，为了保持与Ascii码的兼容性，一般都是将最高位设置为1。也就是说，当最高位为0时，表示Ascii码，当为1时就是各个国家自己的字符
在西欧国家中流行的是ISO 8859-1和Windows-1252，在中国是GB2312，GBK，GB18030和Big5
ISO 8859-1：一个字节表示一个字符，其中0到127与Ascii一样，128到255规定了不同的含义
Windows-1252兼容 ISO 8859-1有更多字符
GB2312：美国和西欧字符用一个字节就够了，中文不行。中文第一个标准是GB2312（两个字节，最高位都是1，如果是0，就认为是Ascii字符）。
GBK兼容GB2312，有更多中文（两个字节）
GB18030兼容GBK（变长编码：部分四个字节）
Big5针对繁体中文（两个字节）
Unicode：给世界上所有的字符分配了唯一一个数字编号，但是没有规定每一个字符对应的二进制表示（二进制表示反感：UTF-32, UTF-16和UTF-8）
UTF-32：四个字节浪费空间
UTF-16：变长字节（2、4字节）通常用于系统内部编码，对于美国和西欧只需要一个字节来说，浪费空间
UTF-8：变长字节（1、2、3、4字节），兼容ASCILL，上面两个不兼容。对大部分中文而言，一个中文字符需要用三个字节表示
乱码：A用Windows-1252写的文件，B用不同于Windows-1252的其他编码如GB18030解析它，就会造成乱码。
1.解析不对
2.解析不对的基础上还进行编码转换
乱码恢复：（简单的直接切换解析方式（查看）、复杂的先以B编码获得乱码的二进制形式，然后以A编码解析（查看）二进制）
Paste_Image.png
不是所有的乱码形式都是可以恢复的，如果形式中有很多不能识别的字符如�?，则很难恢复，另外，如果乱码是由于进行了多次解析和转换错误造成的，也很难恢复
8.char的真正含义
char本质上是一个固定占用两个字节的无符号正整数
char的赋值：
1.char c = 'A' //将一个能用Ascii码表示的字符赋给一个字符变量
2.char c = '马'//直接写字符常量的时候应该注意文件的编码
3.char c = 39532;//马对应的Unicode编码为39532,直接将十进制的常量赋给字符
4.char c = 0x9a6c;//将16进制常量赋给字符
5.char c = '\u9a6c';//按Unicode字符形式
2，3，4，5都是一样的，本质都是将Unicode编号39532赋给了字符
Pattern p = Pattern.compile("/u4e00-/u9fa5");//查找中文字符
9.条件执行的本质
条件的本质是跳转指令（分为条件跳转和无条件跳转）。if/else 会转换成条件指令。
switch的转换和具体系统实现有关。如果分支比较少，可能会转换为跳转指令。但如果分支比较多可能会使用更高效的方式-跳转表（映射表，其中key为整数，从小到大排序（二分查找提高效率））
如果key是连续的或者比较密集，则跳转表还会进行特殊优化，优化为一个数组，
10.函数调用的基本原理
栈来存放函数调用过程中需要的数据，包括参数、返回地址（用来无条件跳转时跳转的位置），函数内定义的局部变量也放在栈中
返回值不太一样，它可能放在栈中，但它使用的栈和局部变量不完全一样，有的系统使用CPU内的一个存储器存储返回值
递归函数的执行过程，函数代码虽然只有一份，但在执行的过程中，每调用一次，就会有一次入栈，生成一份不同的参数、局部变量和返回地址
15.初识继承和多态
super和this是不同的，this引用一个对象，是实实在在存在的，可以作为函数参数，可以作为返回值，但super只是一个关键字，不能作为参数和返回值，它只是用于告诉编译器访问父类的相关变量和方法
变量shape可以引用任何Shape子类类型的对象，这叫多态，即一种类型的变量，可引用多种实际类型对象
Shape shape = new Circle();
Shape shape = new Line();
Shape shape = new ArrowLine();
Shape s = new Shape();
对于变量shape，它就有两个类型，类型Shape，我们称之为shape的静态类型，类型Circle/Line/ArrowLine（子类），我们称之为shape的动态类型
对于变量s，只有一个静态类型Shape
子类对象可以赋值给父类引用变量，这叫多态，实际执行调用的是子类实现，这叫动态绑定
16.继承的细节
当通过b (静态类型Base) 访问时，访问的是Base的变量和方法，当通过c (静态类型Child)访问时，访问的是Child的变量和方法，这称之为静态绑定
当有多个重名函数的时候，在决定要调用哪个函数的过程中，首先是按照参数类型进行匹配的，换句话说，寻找在所有重载版本中最匹配的，然后才看变量的动态类型，进行动态绑定
一个父类的变量，能不能转换为一个子类的变量（强转），取决于这个父类变量的动态类型
重写方法的时候可以修改可见性，只能增加可见性。eg：父类是protected，子类可以是public、protected
17.继承的实现基本原理
类的加载：指将类的相关信息加载到内存（类是动态加载的，当第一次使用这个类的时候才会加载，加载一个类时，会查看其父类是否已加载，如果没有，则会加载其父类）
类的信息（Class对象）主要包括：类变量（静态变量）
类初始化代码（定义静态变量时的赋值语句、静态代码块-------执行顺序是书写顺序）
类方法（静态方法）
实例变量
实例初始化代码（定义实例变量时的赋值语句->实例代码块->构造方法(执行顺序)）
实例方法
父类信息引用
类加载过程包括：
1.分配内存保存类的信息(Java中的方法区保存类的信息，由此可知静态变量是存放在方法区中的)
2.给类变量赋默认值
3.加载父类
4.设置父子关系
5.执行类初始化代码(先执行父类的，再执行子类,父类执行时，子类静态变量的值也是有的，是默认值)
创建对象的过程：
1.分配内存（包括本类和所有父类的实例变量，但不包括任何静态变量）
2.对所有实例变量赋默认值
3.执行实例初始化代码
*每个对象除了保存类的实例变量之外，还保存着实际类信息的引用
*寻找要执行的实例方法的时候，是从对象的实际类型信息开始查找的，找不到的时候，再查找父类类型信息（动态绑定）
如果继承的层次比较深，要调用的方法位于比较上层的父类，则调用的效率是比较低的（虚方法表来优化）。
虚方法表：就是在类加载的时候，为每个类创建一个表，这个表包括该类的对象所有动态绑定的方法及其地址，包括父类的方法，但一个方法只有一条记录，子类重写了父类方法后只会保留子类的
变量访问：对变量的访问是静态绑定的
class Person{
static{sout("init");}
public static final String name = "neo";
public static final int age = 20;
}
Person.name;//调用这行代码的时候是不会初始化Person的，因为final静态变量存在常量池中
Person.age ;//调用这行代码的时候是不会初始化Person的，编译器会进行宏替换
class SuperClass{
static{
System.out.println("super class init.");
}
public static int value=123;
}
class SubClass extends SuperClass{
static{
System.out.println("sub class init.");
}
}
public class test{
public static void main(String[]args){
System.out.println(SubClass.value);
}
}
输出结果是：super class init
通过子类引用父类的静态字段，不会导致子类的初始化
Class[] class ={Person.class,Child.class};//注意这里是不会加载Person类和Child类
Person person;//声明不会加载类
18.为什么说继承是把双刃剑
优点：复用父类代码、重写父类行为、
缺点：继承可能破坏封装是因为子类和父类之间可能存在着实现细节的依赖。子类在继承父类的时候，往往不得不关注父类的实现细节，而父类在修改其内部实现的时候，如果不考虑子类，也往往会影响到子类
接口和抽象类往往配合使用
21.内部类的本质
内部类只是Java编译器的概念，对于Java虚拟机而言，它是不知道内部类这回事的, 每个内部类最后都会被编译为一个独立的类，生成一个独立的字节码文件
内部类的好处：直接访问外部类私有变量
在Java中，根据定义的位置和方式不同，主要有四种内部类：
1.静态内部类（可以直接访问外部类私有静态变量）
public class Outer {
private static int shared = 100;
public static class StaticInner {
public void innerMethod(){
System.out.println("inner " + shared);
}
}
public void test(){
StaticInner si = new StaticInner();
si.innerMethod();
}
}
public静态内部类可以被外部使用eg：Outer.StaticInner si = new Outer.StaticInner();
原理：以上代码实际上会生成两个类：
public class Outer {
private static int shared = 100;
public void test(){
Outer$StaticInner si = new Outer$StaticInner();
si.innerMethod();
}
static int access$0(){
return shared;
}
}
public class Outer$StaticInner {
public void innerMethod() {
System.out.println("inner " + Outer.access$0());
}
}
私有变量是不能被类外部访问的，Java的解决方法是，自动为Outer生成了一个非私有访问方法access$0，它返回这个私有静态变量shared
2.成员内部类
public class Outer {
private int a = 100;
public class Inner {
public void innerMethod(){
System.out.println("outer a " +a);
Outer.this.action();
}
}
private void action(){
System.out.println("action");
}
public void test(){
Inner inner = new Inner();
inner.innerMethod();
}
}
成员内部类对象总是与一个外部类对象相连的， 成员内部类中不可以定义静态变量和静态方法
外部使用:
Outer outer = new Outer();
Outer.Inner inner = outer.new Inner();
原理：
public class Outer {
private int a = 100;
private void action() {
System.out.println("action");
}
public void test() {
Outer$Inner inner = new Outer$Inner(this);
inner.innerMethod();
}
static int access$0(Outer outer) {
return outer.a;
}
static void access$1(Outer outer) {
outer.action();
}
}
public class Outer$Inner {
final Outer outer;
public Outer$Inner(Outer outer){
ths.outer = outer;
}
public void innerMethod() {
System.out.println("outer a "+ Outer.access$0(outer));
Outer.access$1(outer);
}
}
Outer$Inner类有个实例变量outer指向外部类的对象，它在构造方法中被初始化
3.方法内部类
4.匿名内部类
public class Outer {
public void test(final int x, final int y){
Point p = new Point(2,3){
@Override
public double distance() {
return distance(new Point(x,y));
}
};
System.out.println(p.distance());
}
}
创建Point对象的时候，定义了一个匿名内部类，这个类的父类是Point
new后面是父类或者父接口，然后是圆括号()，里面可以是传递给父类构造方法的参数，最后是大括号{}，里面是类的定义
匿名内部类只能被使用一次，用来创建一个对象。它没有名字，没有构造方法
原理：（也是生成了一个独立的类，名字只是数字编号）
public class Outer {
public void test(final int x, final int y){
Point p = new Outer$1(this,2,3,x,y);
System.out.println(p.distance());
}
}
public class Outer$1 extends Point {
int x2;
int y2;
Outer outer;
Outer$1(Outer outer, int x1, int y1, int x2, int y2){
super(x1,y1);
this.outer = outer;
this.x2 = x2;
this.y2 = y2;
}
@Override
public double distance() {
return distance(new Point(this.x2,y2));
}
}
从Java源代码到运行的程序，有编译和连接两个步骤。编译是将源代码文件变成一种字节码（.class文件），连接就是根据引用到的类加载相应的字节码并执行
23.枚举的本质
枚举类型实际上会被Java编译器转换为一个对应的类，这个类继承了Java API中的java.lang.Enum类
public final class Size extends Enum<Size> {
public static final Size SMALL = new Size("SMALL",0);
public static final Size MEDIUM = new Size("MEDIUM",1);
public static final Size LARGE = new Size("LARGE",2);
private static Size[] VALUES =
new Size[]{SMALL,MEDIUM,LARGE};
private Size(String name, int ordinal){
super(name, ordinal);
}
public static Size[] values(){
Size[] values = new Size[VALUES.length];
System.arraycopy(VALUES, 0,
values, 0, VALUES.length);
return values;
}
public static Size valueOf(String name){
return Enum.valueOf(Size.class, name);
}
}
24.异常（上）
image.png
RuntimeException(运行时异常)比较特殊，它的名字有点误导，因为其他异常也是运行时产生的，它表示的实际含义是unchecked exception (未受检异常)，
相对而言，Exception的其他子类和Exception自身则是checked exception (受检异常)，Error及其子类也是unchecked exception
checked还是unchecked，区别在于Java如何处理这两种异常，对于checked异常，Java会强制要求程序员进行处理，否则会有编译错误，而对于unchecked异常则没有这个要求
25.异常（下）
public static int test(){
int ret = 0;
try{
return ret;
}finally{
ret = 2;
}
}
上面代码会返回0，执行到return ret之前将ret的值保存到一个临时变量里面，最后会return这个临时变量，finally只是对ret本身做了修改
public static int test(){
int ret = 0;
try{
int a = 5/0;
return ret;
}finally{
return 2;
}
}
上面代码会返回2
- 剖析StringBuilder
String可以直接使用+和+=运算符，这是Java编译器提供的支持，背后，Java编译器会生成StringBuilder，+和+=操作会转换为append
String hello = "hello";
hello+=",world";
System.out.println(hello);
以上代码Java编译器会转换为：
StringBuilder hello = new StringBuilder("hello");
hello.append(",world");
System.out.println(hello.toString());
既然直接使用+和+=就相当于使用StringBuilder和append，那还有什么必要直接使用StringBuilder呢？在简单的情况下，确实没必要。
不过，在稍微复杂的情况下，Java编译器没有那么智能，它可能会生成很多StringBuilder，尤其是在有循环的情况下，比如说，如下代码：
String hello = "hello";
for(int i=0;i<3;i++){
hello+=",world";
}
System.out.println(hello);
转换后：
String hello = "hello";
for(int i=0;i<3;i++){
StringBuilder sb = new StringBuilder(hello);
sb.append(",world");
hello = sb.toString();
}
System.out.println(hello);
Arrays.sort内部对于基本数据类型使用的快速排序、对象类型是归并排序
32剖析日期和时间
总共24个时区，英国格林尼治是0时区，北京是东八区，也就是说格林尼治凌晨1点，北京是早上9点。0时区的时间也称为GMT+0时间，GMT是格林尼治标准时间，北京的时间就是GMT+8:00
时刻：距离格林尼治标准时间1970年1月1日0时0分0秒（Epoch Time (纪元时））的毫秒数，与时区无关，世界上各个地方都是同一个时刻（System.currentTimeMillis（））
Date：表示时刻
Calendar：表示年历（如公历）
DateFormat/SimpleDateFormat不是线程安全（Joda-Time是线程安全的）
34.随机
Math.random()生成[0，1）
Random rnd = new Random(),rnd.nextInt(100)生成[0,100)
构造方法public Random(long seed)，种子seed决定了随机产生的序列，种子相同，产生的随机数序列就是相同的
随机的基本原理：
Random（线程安全）产生的随机数不是真正的随机数，是伪随机数。
随机数基于一个种子，种子固定，随机数序列就固定，默认构造方法中，种子是一个真正的随机数
带权重的随机选择：
使用nextDouble()生成一个0到1的随机数，然后使用二分查找，看其落入那个区间，如果小于等于70%则选择第一个选项，70%和90%之间选第二个，90%以上选第三个
image.png
35.泛型（上）
原理：
对于泛型类，Java编译器会将泛型代码转换为普通的非泛型代码，将类型参数T擦除，替换为Object，插入必要的强制类型转换。Java虚拟机实际执行的时候，它是不知道泛型这回事的
好处：安全、可能性高
使用场景：泛型类（声明在类名后面）、泛型接口（声明在接口名后面）、泛型方法（声明在返回值前、注意：返回值也可以用泛型）
<T extends E>用于定义类型参数
<? extends E>用于实例化类型参数（通配符）
以下两种写法相等：
public void addAll(DynamicArray<? extends E> c)
public <T extends E> void addAll(DynamicArray<T> c)
通配符 只能读不能写!
DynamicArray<Integer> ints = new DynamicArray<>();
DynamicArray<? extends Number> numbers = ints;
Integer a = 200;
numbers.add(a);//非法
numbers.add((Number)a);//非法
numbers.add((Object)a);//非法
37.泛型（下）
类型对象（Class）只有一份，跟泛型无关
Pair<Integer>.class是非法的
Pair<Integer> p1 = new Pair<Integer>(1,100);
Pair<String> p2 = new Pair<String>("hello","world");
System.out.println(Pair.class==p1.getClass());//true
System.out.println(Pair.class==p2.getClass());//true
instanceof是运行时判断，也与泛型无关:
if(p1 instanceof Pair<Integer>）是非法的
if(p1 instanceof Pair<?>)合法
泛型类类型参数不能用于静态变量和方法（因为静态变量和方法都是类型的属性，且与类型参数无关）
泛型方法可以用于静态方法
Java中还支持多个上界（T extends Base & Comparable & Serializable，类放前面，类型擦除时，会用第一个上界替换）
类型参数之间有继承关系的容器之间是没有关系的，比如，一个DynamicArray<Integer>对象不能赋值给一个DynamicArray<Number>变量。不过，数组是可以的：
Integer[] ints = new Integer[10];
Number[] numbers = ints;
Object[] objs = ints;
java禁止创建泛型数组（可以使用原始类型的数组或容器）
泛型容器内部使用Object数组，如果要转换泛型容器为对应类型的数组，需要使用反射：
public E[] toArray(Class<E> type){
Object copy = Array.newInstance(type, size);
System.arraycopy(elementData, 0, copy, 0, size);
return (E[])copy;
}
38.ArrayList
下面两行代码是不一样的：
if(a>b)
if(a-b>0)
考虑a=Integer.MAX_VALUE, b=Integer.MIN_VALUE：a>b为true，但由于溢出，a-b的结果为-1
反之，再考虑a=Integer.MIN_VALUE, b=Integer.MAX_VALUE:a>b为false，但由于溢出，a-b的结果为1
ArrayList默认大小是0（ArrayList list = new ArrayList()）,在add第一个元素的时候就会扩容到默认大小10，
每次add把当前大小+1如果超过最大值再进行扩容（newSize = oldSize+(oldSize >> 1) 相当于1.5倍）
只要对象实现了Iterable接口，就可以使用foreach语法，编译器会转换为调用Iterable和Iterator接口的方法：
ArrayList<Integer> intList = new ArrayList<Integer>();
for(Integer a : intList){
System.out.println(a);
}
对于foreach语法，编译器会把它转换成迭代器形式：
Iterator<Integer> it = intList.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
迭代的陷阱：
迭代的中间调用容器的删除方法是会报错的（可以使用迭代器的remove方法）原理：
ArrayList默认的迭代器：public Iterator<E> iterator() {
return new Itr();
}
Itr中有一个int expectedModCount = modCount（容器的修改次数,在容器发生结构性变化时会加1，eg:add、remove。但是set不算）;
Itr的某些方法都会判断expectedModCount是不是等于modCount，不等于的话就会抛异常
迭代器的好处：
迭代器表示的是一种关注点分离的思想，将数据的实际组织方式与数据的迭代遍历相分离，是一种常见的设计模式
没有任何代码的接口在Java中被称之为标记接口，用于声明类的一种属性
Arrays中有一个静态方法asList可以返回对应的List，如下所示：
Integer[] a = {1,2,3};
List<Integer> list = Arrays.asList(a);
注意：Arrays.asList没有拷贝，也不会动态改变大小，所以对数组的修改也会反映到List中，对List调用add/remove方法会抛出异常
特点：
可以随机访问，按照索引位置进行访问效率很高，用算法描述中的术语，效率是O(1)，简单说就是可以一步到位。
除非数组已排序，否则按照内容查找元素效率比较低，具体是O(N)，N为数组内容长度，也就是说，性能与数组长度成正比。
添加元素的效率还可以，重新分配和拷贝数组的开销被平摊了，具体来说，添加N个元素的效率为O(N)。
插入和删除元素的效率比较低，因为需要移动元素，具体为O(N
39.LinkedList
LinkedList除了实现了List接口外，LinkedList还实现了Deque和Queue接口,可以按照队列、栈和双端队列的方式进行操作。
Java中的Stack栈已经过时了使用Deque（双端队列）接口代替
作为Queue的操作：
在尾部添加元素 (add, offer)
查看头部元素 (element, peek)，返回头部元素，但不改变队列
删除头部元素 (remove, poll)，返回头部元素，并且从队列中删除
在队列为空时，element和remove会抛出异常NoSuchElementException，而peek和poll返回特殊值null，在队列为满时，add会抛出异常IllegalStateException，而offer只是返回false
作为Stack的操作：
push表示入栈，在头部添加元素，栈的空间可能是有限的，如果栈满了，push会抛出异常IllegalStateException。
pop表示出栈，返回头部元素，并且从栈中删除，如果栈为空，会抛出异常NoSuchElementException。
peek查看栈头部元素，不修改栈，如果栈为空，返回null。
作为Deque：（descendingIterator（）从后往前遍历）
addFirst、addLast、offerFirst、offerLast、peekFirst、peekLast、pollFirst、pollLast、removeFirst、removeLast
特点：
按需分配空间，不需要预先分配很多空间
不可以随机访问，按照索引位置访问效率比较低，必须从头或尾顺着链接找，效率为O(N/2)。
不管列表是否已排序，只要是按照内容查找元素，效率都比较低，必须逐个比较，效率为O(N)。
在两端添加、删除元素的效率很高，为O(1)。
在中间插入、删除元素，要先定位，效率比较低，为O(N)，但修改本身的效率很高，效率为O(1)。
40.HashMap
keySet()/values()/entrySet()返回的是同一个对象，不是对象的拷贝，也就是说直接对对象进行操作会直接影响HashMap中的值
eg：map.keySet().clear()，会删除所有键值对。
一开始是一个空数组，在添加第一个键值对的时候会扩展到默认大小16，默认加载因子是0.75，
所以在Hashmap中size等于16*0.75 = 12时，会对数组进行扩容（2倍、ArrayList是1.5倍）
int h，length有 h&(length-1) == h%length
put基本步骤为：
1.计算键的哈希值
2.根据哈希值得到保存位置（取模）
3.插到对应位置的链表头部或更新已有值
4.根据需要扩展table大小
根据key查找值基本补助：
1. 计算键的hash值（如果key为null，那么hash = 0（table[0]））
2. 根据hash找到table中的对应链表
3. 在链表中遍历查找
4. 逐个比较，先通过hash快速比较，hash相同再通过equals比较
jdk1.8 链表长度太长（默认超过8）时，链表就转换为红黑树
相同的对象其hashCode()返回值必须
41.HashSet
HashSet底层使用HashMap实现的，是把add（E e）的值e当做HashMap的key（key是不能重复的）
42.排序二叉树
树的高度：根到叶子节点经过的最大的节点数
排序二叉树：没有重复元素，左边都小于根，右边都大于根。添加、删除、查询都为O(logn)（eg：AVL、红黑树、TreeMap）
AVL树：任何节点的左右子树的高度差最多为一（在插入和删除通过一次或多次旋转）
红黑树：对于任意一条从根到叶子节点的路径，没有任何一条路径的长度会比其他路径长过两倍（在插入和删除通过一次或多次旋转）
红黑树减弱了对平衡的要求，但降低了保持平衡需要的开销，在实际应用中，统计性能高于AVL树
Ascill: A(65)、a(97)
查找某个节点的后继节点的算法：
如果有右孩子(t.right!=null)，则后继为右子树中最小的节点。
如果没有右孩子，后继为某祖先节点，从当前节点往上找，如果它是父节点的右孩子，则继续找父节点，直到它不是右孩子或父节点为空，第一个非右孩子节点的父亲节点就是后继节点，如果父节点为空，则后继为null
删除节点的算法：
有三种情况：
1.叶子节点：这个容易处理，直接修改父节点对应引用置null即可。
2.只有一个孩子：就是在父亲节点和孩子节点直接建立链接。
3.有两个孩子：先找到后继，找到后，替换当前节点的内容为后继节点，然后再删除后继节点，因为这个后继节点一定没有左孩子，所以就将两个孩子的情况转换为了前面两种情况。
43.TreeMap
基于红黑树实现
按键有序
TreeSet基于TreeMap
有一个单独的内部类Entry，Entry有三个引用，分别指向父节点、左孩子、右孩子
45.神奇的堆
1
2 3
4 5 6 7
8 9 10 11
堆是完全二叉树，会给每一个节点一个编号，从1开始，所以根据一个节点的编号可以计算出其父节点和孩子节点的编号
如果编号为i，则父节点编号即为i/2，左孩子编号即为2*i,右孩子编号即为2。eg对于5号节点，父节点为5/2即2，左孩子为2*5即10，右孩子为2*5+1即11
由于堆的这种特性所以可以使用数组存储
可以有重复元素，元素间不是完全有序的，但对于父子节点之间，有一定的顺序要求，根据顺序分为两种堆，一种是最大堆，另一种是最小堆
算法：
添加元素(Ologn)：
1.添加元素到最后位置。
2.与父节点比较，如果大于等于父节点，则满足堆的性质，结束，否则与父节点进行交换，然后再与父节点比较和交换，直到父节点为空或者大于等于父节点。
从头部删除元素(Ologn)：
1.用最后一个元素替换头部元素，并删掉最后一个元素。
2.将新的头部与两个孩子节点中较小的比较，如果不大于该孩子节点，则满足堆的性质，结束，否则与较小的孩子进行交换，交换后，再与较小的孩子比较和交换，一直到没有孩子，或者不大于两个孩子节点。这个过程我们般称为siftdown
从中间删除元素(Ologn)：
先用最后一个元素替换待删元素。不过替换后，有两种情况，如果该元素大于某孩子节点，则需向下调整(siftdown)，否则，如果小于父节点，则需向上调整(siftup)
构建初始堆（ON）:给定一个无序数组
从最后一个非叶子节点开始，一直往前直到根，对每个节点，执行向下调整siftdown。
换句话说，是自底向上，先使每个最小子树为堆，然后每对左右子树和其父节点合并，调整为更大的堆，因为每个子树已经为堆，所以调整就是对父节点执行siftdown，就这样一直合并调整直到根。这个算法的伪代码是：
void heapify() {
for (int i=size/2; i >= 1; i--)
siftdown(i);
}
优先队列(PriorityQueue)使用堆(物理上使用数组存储)
优先队列的应用：
1.求前K个最大的元素
使用最小堆维护这K个元素，最小堆中，根即第一个元素永远都是最小的，新来的元素与根比就可以了，如果小于根，则堆不需要变化，
否则用新元素替换根，然后向下调整堆即可，调整的效率为O(log2(K))，这样，总体的效率就是O(N*log(2k)）
2.求中值（排序后中间的那个值）
-一个简单的思路是排序，排序后取中间那个值就可以了，排序可以使用Arrays.sort()方法，效率为O(N*log2(N))
-使用两个堆，一个最大堆，一个最小堆:
1.假设当前的中位数为m，最大堆维护的是<=m的元素，最小堆维护的是>=m的元素，但两个堆都不包含m。
2.当新的元素到达时，比如为e，将e与m进行比较，若e<=m，则将其加入到最大堆中，否则将其加入到最小堆中。
3.第二步后，如果此时最小堆和最大堆的元素个数的差值>=2 ，则将m加入到元素个数少的堆中，然后从元素个数多的堆将根节点移除并赋值给m
使用堆不仅实现效率更高，而且还可以应对数据量不确定且源源不断到来的情况，可以给出实时结果。
49 LinkedHashMap
默认是按插入排序、可以按访问排序（每次get/put操作就把该节点移动到链表尾部，最末尾的是最近访问的，最开始的最久没被访问的，应用：LRU缓存）
下面就是一个简单的LRU缓存的实现，它有一个容量限制，这个限制在构造方法中传递，代码是：
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int maxEntries;
public LRUCache(int maxEntries){
super(16, 0.75f, true);
this.maxEntries = maxEntries;
}
@Override//返回true代表需要删除最旧没有被访问的元素
protected boolean removeEldestEntry(Entry<K, V> eldest) {
return size() > maxEntries;
}
}
内部维护了一个单独的双向链表，每个节点即位于哈希表中，也位于双向链表中
50.EnumMap
Map<Size, Integer> map = new EnumMap<>(Size.class);//需要传递类信息
- EnumSet
EnumSet的实现与EnumMap没有任何关系，而是用极为精简和高效的位向量实现的
EnumSet是一个抽象类，不能直接通过new新建，而是提供了若干静态工厂方法
什么是位向量呢？就是用一个位表示一个元素的状态，用一组位表示一个集合的状态，每个位对应一个元素，而状态只可能有两种
56.文件概述
所有文件都是以0、1的二进制保存的，我们所看到的图片、视频、文本，都是应用程序对这些二进制的解析结果
Windows 换行符两个字符："\r\n"、Linux 一个字符："\n"
Linux系统中，如果文件名以.开头，则为隐藏文件
常识1：硬盘的访问延时，相比内存，是很慢的，操作系统和硬盘一般是按块批量传输，而不是按字节，以摊销延时开销，块大小一般至少为512字节，即使应用程序只需要文件的一个字节，操作系统也会至少将一个块读进来
常识2：一般读写文件需要两次数据拷贝，先从硬盘拷贝到操作系统内核（内核态），再从内核拷贝到应用程序（用户态）分配的内存中，需要两次环境的切换，先从用户态切到内核态，再从内核态切到用户态（用户态/内核态的切换是有开销）
为了提升文件操作的效率，使用缓冲区。读文件时，即使目前只需要少量内容，但预知还会接着读取，就一次读取比较多的内容，放到读缓冲区，下次读取时，缓冲区有，就直接从缓冲区读，减少访问操作系统和硬盘。
写文件时，先写到写缓冲区，写缓冲区满了之后，再一次性的调用操作系统写到硬盘。在写结束的时候，要记住将缓冲区的剩余内容同步到硬盘
操作系统操作文件一般有打开和关闭的概念。打开文件会在操作系统内核建立一个有关该文件的内存结构（消耗内存），用一个整数索引（文件描述符）来引用，不用文件的时候，应该记住关闭文件,关闭文件一般会同步缓冲区内容到硬盘，并释放占据的内存结构
基本的流按字节读写，没有缓冲区.使用装饰器模式，引入了很多装饰类，对基本的流增加功能，以方便使用
以InputStream/OutputStream为基类的流基本都是以二进制形式处理数据的，不能够方便的处理文本文件，没有编码的概念，能够方便的按字符处理文本数据的基类是Reader和Writer
57.二进制文件和字节流
InputStream/OutputStream: 这是基类，它们是抽象类。
FileInputStream/FileOutputStream: 输入源和输出目标是文件的流。
ByteArrayInputStream/ByteArrayOutputStream: 输入源和输出目标是字节数组的流。
DataInputStream/DataOutputStream: 装饰类，按基本类型和字符串而非只是字节读写流。因为比较麻烦所以有了序列化机制
BufferedInputStream/BufferedOutputStream: 装饰类，对输入输出流提供缓冲功能。
InputStream：
read(byte[] b)返回值是实际读取到的字节个数（不一定=b的值）
public long skip(long n) throws IOException //跳过输入流的n个字节，返回值为实际略过的字节个数（不一定是n），默认实现是读取n个字节并扔掉，子类有更高效的方法（native方法）
public int available() throws IOException//返回下一次不需要阻塞就能读取到的大概字节个数,从网络读取数据时，可以根据该方法的返回值在网络有足够数据时才读，以避免阻塞
public synchronized void mark(int readlimit)//readLimit表示设置标记后往后最多能读取readLimit个字节，如果超过了，标记则无效
public boolean markSupported()
public synchronized void reset() throws IOException
mark/reset/markSupported，用于支持从读过的流中重复读取.mark方法将当前位置标记下来，在读取了一些字节，希望重新从标记位置读时，调用reset方法
不是所有流都支持mark/reset的，是否支持可以通过markSupported的返回值进行判,。InpuStream的默认实现是不支持，FileInputStream也不直接支持，但BufferedInputStream和ByteArrayInputStream可以
OutputStream：
write(int b)//写入方法参数虽然是int，但其实只会用到最低的8位也就是一个字节
flush()//对于BufferedOutputStream，调用flush会将其缓冲区的内容写到其装饰的流中，并调用该流的flush方法
//对于FileOutputStream，调用flush没有任何效果数据，只是传递给了操作系统，但操作系统什么时候保存到硬盘上，这是不一定的。
要想确保数据保存在硬盘上，调用FileDescriptor.sync()//一般不用调用，系统会自动写入
flush只能将应用程序缓冲的数据写到操作系统，sync则确保数据写到硬盘
new一个FileOutputStream/FileInputStream对象会实际打开文件，操作系统会分配相关资源
FileOutputStream还有两个额外的方法：
public FileChannel getChannel()
public final FileDescriptor getFD()//文件描述符
如果不确定文件内容的长度，不希望一次性分配过大的byte数组，又希望将文件内容全部读入,使用ByteArrayOutputStream
ByteArrayOutputStream的输出目标是一个byte数组，这个数组的长度是根据数据内容动态扩展的
ByteArrayOutputStream output = new ByteArrayOutputStream();
byte[] buf = new byte[1024];
int bytesRead = 0;
while((bytesRead=input.read(buf))!=-1){
output.write(buf, 0, bytesRead);//append模式
}
int [] src = {1,2,3,4,5};
int [] des = new int[5];
System.arraycopy(src,1,des,0,4);//(源数组,源数组起始位置,目标数组，目标数组起始位置，拷贝长度)
System.out.println(Arrays.toString(des));//输出[2, 3, 4, 5, 0]
int[] temp = Arrays.copyOf(src,5);//第二个参数是要拷贝的长度
System.out.println(Arrays.toString(temp));//[1, 2, 3, 4,5]
使用缓冲：
InputStream input = new BufferedInputStream(new FileInputStream("hello.txt"));
OutputStream output = new BufferedOutputStream(new FileOutputStream("hello.txt"));
DataOutputStream output = new DataOutputStream(new BufferedOutputStream(new FileOutputStream("students.dat")));
DataInputStream input = new DataInputStream(new BufferedInputStream(new FileInputStream("students.dat"))
58.文本文件和字符流
Reader/Writer：字符流的基类，它们是抽象类。
InputStreamReader/OutputStreamWriter：适配器类，输入是InputStream，输出是OutputStream，将字节流转换为字符流。
FileReader/FileWriter：输入源和输出目标是文件的字符流。
CharArrayReader/CharArrayWriter: 输入源和输出目标是char数组的字符流。//用法类似于ByteArrayOutputStream（while循环每次读固定字节文件知道读完）
StringReader/StringWriter：输入源和输出目标是String的字符流。
BufferedReader/BufferedWriter：装饰类，对输入输出流提供缓冲，以及按行读写功能。
PrintWriter：装饰类，可将基本类型和对象转换为其字符串形式输出的类
字节流是按字节读取的，而字符流则是按char读取的，一个char在文件中保存的是几个字节与编码有关，但字符流给我们封装了这种细节，我们操作的对象就是char
一个char不完全等同于一个字符，对于绝大部分字符，一个字符就是一个char,某些增补字符需要两个char表示一个字符
FileReader/FileWriter（是InputStreamReader/OutputStreamWriter子类）不能指定编码类型，只能使用默认编码，如果需要指定编码类型，可以使用InputStreamReader/OutputStreamWriter
写文件时，可以优先考虑PrintWriter，因为它使用方便，支持自动缓冲、支持指定编码类型、支持类型转换等。
读文件时，如果需要指定编码类型，需要使用InputStreamReader，不需要，可使用FileReader，但都应该考虑在外面包上缓冲类BufferedReader
59.文件和目录操作
getPath()返回构造File对象时的完整路径名，包括路径和文件名称。
getAbsolutePath()返回完整的绝对路径名。
getCanonicalPath()返回标准的完整路径名，它会去掉路径中的冗余名称如".",".."，跟踪软连接(Unix系统概念)等
File f = new File("../io/test/students.txt");
System.out.println(System.getProperty("user.dir"));---/Users/majunchang/io
System.out.println("path: " + f.getPath());---path: ../io/test/students.txt
System.out.println("absolutePath: " + f.getAbsolutePath());---absolutePath: /Users/majunchang/io/../io/test/students.txt
System.out.println("canonicalPath: " + f.getCanonicalPath());---canonicalPath: /Users/majunchang/io/test/students.txt
getParent()返回父目录路径//File对象是相对路径则返回null,解决方法：f.getCanonicalFile().getParent()
getParentFile()返回父目录的File对象//File对象是相对路径则返回null，解决方法：f.getCanonicalFile().getParentFile()
文件路径分隔符，在Windows系统中，一般为"\"，Linux系统中一般为"/"
mkdir() mkdirs()区别在于，如果某一个中间父目录不存在，则mkdir会失败，返回false，而mkdirs则会创建必需的中间父目录
60.随机读写文件及其应用
RandomAccessFile既可以读，也可以写，还可以随机读写、重复读。构造方法有一个mode：
"r": 只用于读
"rw": 用于读和写
"rws": 和"rw"一样，用于读和写，另外，它要求文件内容和元数据的任何更新都同步到设备上
"rwd": 和"rw"一样，用于读和写，另外，它要求文件内容的任何更新都同步到设备上，和"rws"的区别是，元数据的更新不要求同步
RandomAccessFile内部有一个文件指针，指向当前读写的位置，各种read/write操作都会自动更新该指（getFilePointer()//获取当前文件指正、 seek(long pos)///更改当前文件指针到pos 两个方法都是native方法）
skipBytes(int n)//类似于InputStream的skip方法(先读再抛弃)，但是更高效
writeBytes(String sr)和readLine()//没有编码的概念，都假定一个字节就代表一个字符，对于中文有问题，所以尽量不要使用
62.神奇的序列化（read、writeObject用了反射）
序列化就是将对象转化为字节流，反序列化就是将字节流转化为对象
能自动处理引用同一个对象(A、B都引用C反序列化时C还时被A、B引用)和循环引用（A引用B，B引用A反序列化不变）的情况
定制序列化：1.transient关键字 2.自己实现writeObject和readObject方法。
序列化：
1、用途：对象持久化，跨网络的数据交换、远程过程调用
2、局限性：a.不能实现跨语言的数据交换
b. Java在序列化字节中保存了很多描述信息，使得序列化格式比较大。
c.Java的默认序列化使用反射分析遍历对象结构，性能比较低。
d.Java的序列化格式是二进制的，不方便查看和修改
zip能压缩多个文件、gzip只能压缩一个文件
65.线程的基本概念
调用start()方法后，操作系统会分配线程相关的资源，每个线程会有单独的程序执行计数器和栈，
操作系统会把这个线程作为一个独立的个体进行调度，分配时间片让它执行
无论是通过继承Thead还是实现Runnable接口来实现线程，启动线程都是调用Thread对象的start方法
优先级对操作系统而言是一种建议和提示，而非强制，不要过于依赖优先级
线程的状态：
NEW: 没有调用start的线程状态为NEW
TERMINATED: 线程运行结束后状态TERMINATED
RUNNABLE: 调用start后线程在执行run方法且没有阻塞时状态为RUNNABLE，
不过，RUNNABLE不代表CPU一定在执行该线程的代码，可能正在执行也可能在等待操作系统分配时间片，只是它没有在等待其他条件
BLOCKED、WAITING、TIMED_WAITING：都表示线程被阻塞了，在等待一些条件
isAlive():线程被启动后，run方法运行结束前，返回值都是true
deamon守护线程：当整个程序中剩下的都是daemo线程的时候，程序就会退出eg（gc线程）
sleep():会让当前线程睡眠指定的时间（不会释放锁），睡眠期间，该线程会让出CPU，但睡眠的时间不一定是确切的给定毫秒数，可能有一定的偏差
偏差与系统定时器和操作系统调度器的准确度和精度有关，睡眠期间如果被中断会抛InterruptedException
yield():告诉操作系统的调度器，我现在不着急占用CPU，你可以先让其他线程运行,这对调度器也仅仅是建议，调度器如何处理是不一定的，它可能完全忽略该调用
join():让调用join的线程等待该线程结束,被中断，会抛出InterruptedException( join(0)表示无期限等待)
stop() suspend() resume()已过时，不推荐使用
竞态条件：counter++这个操作不是原子操作，它分为三个步骤：
1.取counter的当前值
2.在当前值基础上加1
3.将新值重新赋值给counter
两个线程可能同时执行第一步，取到了相同的counter值，比如都取到了100，第一个线程执行完后counter变为101，而第二个线程执行完后还是101
内存可见性（基于两个线程的共享变量）:一个线程对一个共享变量的修改，另一个线程不一定马上就能看到，有可能过一段时间能看到、有可能永远也看不到（解决方法：volitile、synchronized)
private static boolean shutdown = false;
static class HelloThread extends Thread {
@Override
public void run() {
while(!shutdown){
// do nothing
}
System.out.println("exit hello");
}
}
public static void main(String[] args) throws InterruptedException {
new HelloThread().start();
Thread.sleep(1000);
shutdown = true;
System.out.println("exit main");
}
上面代码在主线程把shutdown变量置为true，但是在HelloThread线程里面任然从自己的缓存里面取的值false，
导致程序无法退出
- 理解synchronized
每个对象有一个锁和两个等待队列(一个是等待锁的队列、一个是用于协作的条件队列)，当前线程不能获得锁的时候，它会加入等待队列等待，线程的状态会变为BLOCKED
多个线程是可以同时执行同一个synchronized实例方法的，只要它们访问的对象是不同的
synchronized方法不能防止非synchronized方法被同时执行，所以，一般在保护变量时，需要在所有访问该变量的方法上加上synchronized
synchronized静态方法保护的是类对象（类也是对象.class、万物皆对象）
synchronized实例方法保护的是类的实例对象
所以不同的两个线程，可以同时，一个执行synchronized静态方法，另一个执行synchronized实例方法
synchronized关键字获取锁的过程中不响应中断请求，解决方法：显式锁
理解synchronized：
a.可重入性：对同一个执行线程，它在获得了锁之后，在调用其他需要同样锁的代码时，可以直接调用（不是所有锁都是可重入的）
b.内存可见性：在释放锁时，所有写入都会写回内存，而获得锁后，都会从内存中读最新数据
c.死锁：有a, b两个线程，a持有锁A，在等待锁B，而b持有锁B，在等待锁A，a,b陷入了互相等待，最后谁都执行不下，解决办法：
1.应该尽量避免在持有一个锁的同时去申请另一个锁，如果确实需要多个锁，所有代码都应该按照相同的顺序去申请锁
2.显式锁接口Lock方法，可以在获取不到锁的时候释放已经持有的锁，然后再次尝试获取锁或干脆放弃，以避免死锁
同步容器(给所有容器方法都加上synchronized来实现安全的)
Collections.synchronizedCollection
Collections.synchronizedList
Collections.synchronizedMap
绝对安全吗？不是的，至少有以下情况需要注意：
1.复合操作：
public class EnhancedMap <K, V> {
Map<K, V> map;
public EnhancedMap(Map<K,V> map){
this.map = Collections.synchronizedMap(map);
}
public V putIfAbsent(K key, V value){
V old = map.get(key);
if(old!=null){
return old;
}
map.put(key, value);
return null;
}
public void put(K key, V value){
map.put(key, value);
}
//... 其他代码
}
putIfAbsent()组合了get、put操作，是不安全的。比如多个线程到get这一步，发现old为null，最终导致put多次
2.伪同步
给上面的putIfAbsent()方法加上synchronized就能线程安全吗？还是不安全！因为同步对象不同。解决方法：synchronized(map){//...}
3.迭代
一个线程修改集合(add)、一个线程迭代集合会抛出java.util.ConcurrentModificationException，解决：给遍历加锁(注意和第二点一样要锁集合对象)
除了以上这些注意事项，同步容器的性能也是比较低的，当并发访问量比较大的时候性能很差。Java中还有很多专为并发设计的容器类：
CopyOnWriteArrayList
ConcurrentHashMap
ConcurrentLinkedQueue
ConcurrentSkipListSet
这些容器类都是线程安全的，但都没有使用synchronized、没有迭代问题、直接支持一些复合操作、性能也高得多
67.线程的基本协作机制(上)
1.wait()：把当前线程放到条件队列上并阻塞
public class WaitThread extends Thread {
private volatile boolean fire = false;
@Override
public void run() {
try {
synchronized (this) {
while (!fire) {
wait();
}
}
System.out.println("fired");
} catch (InterruptedException e) {
}
}
public synchronized void fire() {
this.fire = true;
notify();
}
public static void main(String[] args) throws InterruptedException {
WaitThread waitThread = new WaitThread();
waitThread.start();
Thread.sleep(1000);
System.out.println("fire");
waitThread.fire();
}
}
wait/notify方法只能在synchronized代码块内被调用，如果调用wait/notify方法时，当前线程没有持有对象锁，会抛出异常java.lang.IllegalMonitorStateException
如果wait必须被synchronzied保护，那一个线程在wait时，另一个线程怎么可能调用同样被synchronzied保护的notify方法呢？它不需要等待锁吗？
调用wait时，线程会释放对象锁（notify不会释放、所以得等notify的synchronzied代码块执行完）。
1.把当前线程放入条件等待队列，释放对象锁，阻塞等待，线程状态变为WAITING或TIMED_WAITING
2.等待时间到或被其他线程调用notify/notifyAll从条件队列中移除，这时，要重新竞争对象锁
如果能够获得锁，线程状态变为RUNNABLE，并从wait调用中返回
否则，该线程加入对象锁等待队列，线程状态变为BLOCKED，只有在获得锁后才会从wait调用中返回。
线程从wait调用中返回后，不代表其等待的条件就一定成立了，它需要重新检查其等待的条件，一般的调用模式是：
synchronized (obj) {
while (条件不成立)
obj.wait();
... // 执行条件满足后的操作
}
68.线程的基本协作机制 (下)
1.同时开始：每个线程start都wait()，在所有线程start之后notifyAll
static class FireFlag {
private volatile boolean fired = false;
public synchronized void waitForFire() throws InterruptedException {
while (!fired) {
wait();
}
}
public synchronized void fire() {
this.fired = true;
notifyAll();
}
}
static class Racer extends Thread {
FireFlag fireFlag;
public Racer(FireFlag fireFlag) {
this.fireFlag = fireFlag;
}
@Override
public void run() {
try {
this.fireFlag.waitForFire();
System.out.println("start run "+ Thread.currentThread().getName());
} catch (InterruptedException e) {
}
}
}
public static void main(String[] args) throws InterruptedException {
int num = 10;
FireFlag fireFlag = new FireFlag();
Thread[] racers = new Thread[num];
for (int i = 0; i < num; i++) {
racers[i] = new Racer(fireFlag);
racers[i].start();
}
Thread.sleep(1000);
fireFlag.fire();
}
2.等待结束(CountDownLatch)：等待所有子线程执行结束后再执行后面的代码，使用join有时比较麻烦，需要主线程逐一等待每个子线程
思路：使用一个共享变量等于线程的数量，每个线程结束后-1，为0时notifyAll
public class MyLatch {
private int count;
public MyLatch(int count) {
this.count = count;
}
public synchronized void await() throws InterruptedException {
while (count > 0) {
wait();
}
}
public synchronized void countDown() {
count--;
if (count <= 0) {
notifyAll();
}
}
}
static class Worker extends Thread {
MyLatch latch;
public Worker(MyLatch latch) {
this.latch = latch;
}
@Override
public void run() {
try {
// simulate working on task
Thread.sleep((int) (Math.random() * 1000));
this.latch.countDown();
} catch (InterruptedException e) {
}
}
}
public static void main(String[] args) throws InterruptedException {
int workerNum = 100;
MyLatch latch = new MyLatch(workerNum);
Worker[] workers = new Worker[workerNum];
for (int i = 0; i < workerNum; i++) {
workers[i] = new Worker(latch);
workers[i].start();
}
latch.await();
System.out.println("collect worker results");
}
上面这种方式和java中CountDownLatch类似，也可以实现同时开始的需求，令workNum=1，在每个线程的run的第一句wait、在所有线程start之后countdown
3.异步结果：子线程没有执行完一直wait、执行完后notifyAll，注意需要锁同一个对象
4.集合点(CyclicBarrier):
69.线程的中断
1.停止一个线程的主要机制是中断，中断并不是强迫终止一个线程，它是一种协作机制，是给线程传递一个取消信号，但是由线程来决定如何以及何时退出
public boolean isInterrupted()//返回对应线程的中断标志位是否为true
public static boolean interrupted()//返回当前线程的中断标志位是否为true并且清空标志位
public void interrupt()//中断对应的线程,分多种情况，与线程的状态和在进行的IO操作有关
对于线程的状态（没有执行IO操作）：
a. RUNNABLE：线程在运行或具备运行条件只是在等待操作系统调度
interrupt()只设置线程的中断标志位，没有任何其它作用，线程应在运行过程中检查中断标志位eg：
void run(){
while (!Thread.currentThread().isInterrupted()) {
//具体的操作
}
}
Thread.interrupt()
b.WAITING(join、wait)/TIMED_WAITING(wait(long time)、sleep(time)、join(time))
Thread t = new Thread (){
@Override
public void run() {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
System.out.println(isInterrupted());//输出false
}
}
};
t.start();
try {
Thread.sleep(100);
} catch (InterruptedException e) {
}
t.interrupt();
解决方法：在catch里面设置标志位，在run里面判断标志位
c. BLOCKED：等待锁
interrupt()只是会设置线程的中断标志位，线程依然会处于BLOCKED状态
d.NEW/TERMINATE
interrupt()没有任何效果，中断标志位也不会被设置
对于IO操作：
InputStream的read调用，该操作是不可中断的，如果流中没有数据，read会阻塞 (但线程状态依然是RUNNABLE)，且不响应interrupt()
解决方法：InputStream. close()方法
