1. 数据结构

1.1 概念

什么是程序？

Pascal之父——Nicklaus Wirth（尼克劳斯·威茨）他在自己1976年出的书《算法+数据结构=程序》对程序下了个定义，并因此让他获得图灵奖。

数据结构在编程中这么重要呢？
对非常重要，不仅开发时重要，而且是面试中的最爱，尤其大厂BAT的企业。

<mark>补充一点：个人理解现代的程序：算法+数据结构+框架+架构</mark>

• 算法+数据结构=单体项目
• 算法+数据结构+<mark>框架</mark>=企业级项目
• 算法+数据结构+<mark>框架+架构</mark>=分布式项目

那什么是数据结构？

数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的<mark>数据元素的集合</mark>。
精心选择的数据结构可以带来更高的运行或者存储效率。

数据结构的基本功能：

• 如何<mark>插入</mark>一条新的数据
• 如何<mark>寻找</mark>某一特定的数据
• 如何<mark>删除</mark>某一数据
• 如何<mark>迭代</mark>获取集合的所有数据

常用的数据结构有：

数组、链表、栈、队列、散列表、树、图。

树(Tree)和图很少使用，晦涩难懂，同时java也没有提供直接的代码实现，初学者暂时不用触碰。

2. 泛型

2.1 概念

public class LinkedList<E> 
	extends AbstractSequentialList<E>
		implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}

public interface Deque<E> extends Queue<E> {}

public interface Queue<E> extends Collection<E> {}

public interface Collection<E> extends Iterable<E> {}

我们上面的代码中出现的<?>是什么东西呢？它叫泛型，常用来和集合对象一同使用，所以我们在开始学习集合之前，必须先了解下什么是泛型。而且泛型概念非常重要，它是程序的增强器，它是目前主流的开发方式。

<mark>泛型是（Generics）JDK1.5 的一个新特性</mark>，其实就是一个『语法糖』，本质上就是编译器为了提供更好的可读性而提供的一种小手段，小技巧

注意：<mark>虚拟机层面是不存在所谓『泛型』的概念的</mark>。

是不有点神奇，不知所云，别着急等我讲完你就清楚了。

2.2 作用

• 通过泛型的语法定义，约束集合元素的类型，编译器可以在编译期提供一定的类型安全检查，避免运行时才暴***ug。
• 代码通用性更强，后面有案例
• 泛型可以提升程序代码的可读性，但<mark>它只是一个语法糖（编译后这样的东西就被删除，不出现在最终的源代码中）</mark>，对于JVM运行时的性能是没有任何影响的。

2.3 泛型示例

我们创建一个ArrayList，上面看到eclipse提示有个黄线，什么意思呢？

ArrayList is a raw type. References to generic type ArrayList should be parameterized.

ArrayList使用了泛型，在声明时需指定具体的类型。

那我们把这个<>里的方式就称为泛型。上面的泛型有什么作用呢？就是在编译阶段就检查我们传入的参数类型是否正确。

有了泛型，我们可以看到人家要求存放String，而我故意存放的整数100，所以eclipse提示我们错误：

The method add(int, String) in the type List is not applicable for the arguments (int)。

类型List的add方法要求增加的类型为String类型，不正确不能存入。

2.4 泛型声明

泛型可以在接口、方法、返回值上使用：

java.util.List泛型接口：

public interface List<E> extends Collection<E> {}

泛型方法的声明：

public static <E> void print(E[] arr) {}

在方法返回值前声明了一个表示后面出现的E是泛型，而不是普通的java变量。

public <T> T getBean(String beanName);

定义泛型方法，标识后面出现的T是泛型的意思，后面的T标识是返回值通用。

2.5 $常用名称$常用名称

• E - Element (在集合中使用，因为集合中存放的是元素)
• T - Type（Java 类）
• K - Key（键）
• V - Value（值）
• N - Number（数值类型）
• ? - 表示不确定的java类型

2.6 用途：编译时类型检查

可以在编译期间检查一定的业务逻辑

注意：List在eclipse也会直接提示，黄色波浪线

我们业务本意是字符串，但100显然是整数，这种业务逻辑错误只有在运行时才会报错，非常隐秘。

我们加上泛型后，类型如果错误，我们在编译前就会检查出来，从而避免错误发生。

	List<String> list = new ArrayList<String>();

    list.add("tony");

    list.add("100");

2.7 用途：代码通用性更强

传统方式通过重载多态实现，方法同名，参数类型不同。

package javase.base.gennarics;

 

public class TestOldStyle {

    public static void print(Integer[] dArray) {

       for( Integer d : dArray) {

           System.out.println(d);

       }

    }

   

    public static void print( String[] sArray) {

       for( String s : sArray) {

           System.out.println(s);

       }

    }

   

    public static void main(String[] args) {

       Integer[] scores = new Integer[]{100,98,80};

       String[] names = new String[]{"语文","数学","英语"};

      

       TestOldStyle.print(scores);

       TestOldStyle.print(names);

    }

}

泛型方式

package javase.base.gennarics;

 

public class TestGenarics {

    public static <E> void print(E[] arr) {

       for(E e : arr) {

           System.out.println(e);

       }

    }

   

    public static void main(String[] args) {

       Integer[] scores = new Integer[]{ 100,98,80 };

       String[] names = new String[]{ "语文","数学","英语" };

       Double[] moneys = new Double[] { 10.1,20.2,30.3 };

      

       TestGenarics.print(scores);

       TestGenarics.print(names);

       TestGenarics.print(moneys);

    }

}

可以看到泛型简洁清晰明了，其实清爽一个字聊得。又写了一个moneys自适应一句代码都没写，传统方式就傻了，得去改代码增加实现。

2.8 $类型擦除$类型擦除

泛型只是在编译期间生存，编译后就***掉了，真正运行时，大多情况下取而代之的是Object。

下面的代码利用了jdk提供的强大的反射功能，后续会专门详细讲解，今天先初体验下其强大的功能。

package cn.edut.com.tarena;

public class Demo_genericity {
	public static void main(String[] args) {
		// 创建类
		System.out.println("创建类:");
		Wapper<String> w1 = new Wapper();
		Wapper<Integer> w2 = new Wapper();
		// 赋值
		System.out.println("赋值：");
		w1.setValue("aaa");
		w2.setValue(123);

		System.out.println(w1.getValue());
		System.out.println(w2.getValue());
		/* * 调用类型擦除了的函数 */
		System.out.println("调用类型查出方法");
		f(w1);
		f(w2);
		System.out.println("取值（报错）");
		String s1 = w1.getValue();
		Integer s2 = w2.getValue();

	}

	/** * 类型擦除的例子 * * @param w */
	public static void f(Wapper w) {
		Object o = w.getValue();
		System.out.println(o);

		w.setValue("g");
	}
}

class Wapper<T> {
	private T value;

	public T getValue() {
		return value;
	}

	public void setValue(T value) {
		this.value = value;
	}

}

3. 线程、Thread

精简版：https://blog.csdn.net/LawssssCat/article/details/103121799

3.1 进程

3.1.1 什么是进程

几乎所有操作系统都支持同时运行多个任务，听歌，看文档，聊QQ，一个都不耽误。一个任务通常就是一个程序，每个运行中的程序就是一个进程（Process）。当一个程序运行时，内部可能包含了多个顺序执行流，每个顺序执行流就是一个线程。

3.1.2 进程特点

l 独立性：进程是系统中独立存在的实体，它可以拥有自己的独立的资源，每一个进程都拥有自己私有的地址空间。在没有经过进程本身允许的情况下，一个用户进程不可以直接访问其他进程的地址空间。

l 动态性：进程与程序的区别在于，程序只是一个静态的指令集合，而进程是一个正在系统中活动的指令集合。在进程中加入了时间的概念，进程具有自己的生命周期和各种不同的状态，这些概念在程序中都是不具备的。

l 并发性：多个进程可以在单个处理器上并发执行，多个进程之间不会互相影响。

3.1.3 并发存在吗？

我们一边听歌，一边看文档，除此之外，电脑还运行着其他很多程序，杀毒软件、QQ、微信、eclipse等等，这些进程看上去是同时工作。

但事实真相是，对于一个CPU而言，它在某个时间点只能执行一个程序，也就是说，只能运行一个进程，CPU不断地在这些进程之间轮换执行。那为什么我们感觉不到呢？这是因为CPU的执行速度惊人（如果启动的程序过多，我们还是能感受到速度变慢），所以虽然CPU在多个进程中切换执行，但我们感觉是多个程序同时在执行。

3.1.4 CPU分时调度

时间片即CPU分配给各个程序的时间，每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间，使各个程序从表面上看是同时进行的。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程，将当前进程挂起。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换，而不会造成CPU资源浪费。当又切换到之前执行的进程，把现场恢复，继续执行。

注意：进程在切换时有挂起和现场恢复，这些操作都是额外的，单进程就没有这个问题。进程如此线程亦如此，所以有时我们会发现开启多个线程，感觉会很快，可实际发现多线程有时不一定快，反而还慢，就是这个原因造成的。

在宏观上：我们可以同时打开多个应用程序，每个程序并行，同时运行。但在微观上：由于只有一个CPU，一次只能处理程序要求的一部分，如何处理公平，一种方法就是引入时间片，每个程序轮流执行。多核提高了并发能力，但本质不变。

3.2 线程

3.2.1 概念

线程（thread）是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一个进程可以开启多个线程。多线程扩展了多进程的概念，使得同一个进程可以同时并发处理多个任务。

简而言之，一个程序运行后至少一个进程，一个进程里包含多个线程。

3.2.2 守护线程

守护线程是特殊的线程，一般用于在后台为其他线程提供服务。

例如：我们启动一个杀毒软件360，它会同时启动一个守护进程，监控360杀毒程序。如果这个程序被关闭，则自动重新启动这个程序。我们为何关不掉它，现在知道原因了吧。

3.2.3 进程和线程的关系

一个进程可以分成多个线程，线程是最小执行单元。

进程有自己的私有内存，这块内存会在主存中有一段映射，而所有的线程共享JVM中的内存。在现代的操作系统中，线程的调度通常都是集成在操作系统中的，操作系统能通过分析更多的信息来决定如何更高效地进行线程的调度，这也是为什么Java中会一直强调，线程的执行顺序是不会得到保证的，因为JVM自己管不了这个，所以只能认为它是完全无序的。

另外，类java.lang.Thread中的很多属性也会直接映射为操作系统中线程的一些属性。Java的Thread中提供的一些方法如sleep和yield其实依赖于操作系统中线程的调度算法。

从上图中可以看出一个操作系统中可以有多个进程，一个进程中可以有多个线程，每个进程有自己独立的内存，每个线程共享一个进程中的内存，每个线程又有自己独立的内存。（记清这个关系，非常重要！）

3.2.4 查看线程

Windows10中查询查看线程：选中线程，默认不展示。

可以看到chrome.exe的多个进程中，每个进程又启动了多个线程。

3.3 多线程并发编程

3.3.1 并发编程三要素

l 原子性：指的是一个或者多个操作，要么全部执行并且在执行的过程中不被其他操作打断，要么就全部都不执行。原子性是数据一致性的保障。

l 可见性：指多个线程操作一个共享变量时，其中一个线程对变量进行修改后，其他线程可以立即看到修改的结果。

l 有序性：程序的执行顺序按照代码的先后顺序来执行。单线程简单的事，多线程并发就不容易保障了。

3.3.2 死锁

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁。

3.3.3 状态

线程生命周期，总共有五种状态：

1. 新建状态（New）：当线程对象对创建后，即进入了新建状态，如：Thread t = new MyThread()；

2. 就绪状态（Runnable）：当调用线程对象的start()方法（t.start();），线程即进入就绪状态。处于就绪状态的线程，只是说明此线程已经做好了准备，随时等待CPU调度执行，并不是说执行了t.start()此线程立即就会执行；

3. 运行状态（Running）：当CPU开始调度处于就绪状态的线程时，此时线程才得以真正执行，即进入到运行状态。注：就绪状态是进入到运行状态的唯一入口，也就是说，线程要想进入运行状态执行，首先必须处于就绪状态中；

4. 阻塞状态（Blocked）：处于运行状态中的线程由于某种原因，暂时放弃对CPU的使用权，停止执行，此时进入阻塞状态，直到其进入到就绪状态，才有机会再次被CPU调用以进入到运行状态；

5. 根据阻塞产生的原因不同，阻塞状态又可以分为三种：

a) 等待阻塞：运行状态中的线程执行wait()方法，使本线程进入到等待阻塞状态；

b) 同步阻塞：线程在获取synchronized同步锁失败(因为锁被其它线程所占用)，它会进入同步阻塞状态；

c) 其他阻塞：通过调用线程的sleep()或join()或发出了I/O请求时，线程会进入到阻塞状态。当sleep()状态超时、join()等待线程终止或者超时、或者I/O处理完毕时，线程重新转入就绪状态。

6. 死亡状态（Dead）：线程执行完了或者因异常退出了run()方法，该线程结束生命周期。

l 启动线程不要自己调用run()方法，那样就成普通方法了，只能等待OS操作系统自己去调用

l 如果start()一个线程后想其立即执行，技巧：Thread.sleep(1)

l 一个多处理器的机器上，将会有多个线程并行（Parallel）执行，当线程数大于处理器数时，才会出现多个线程并发（Concurrent），在一个CPU上轮换执行

l 并行和并发的差异，一个是同时执行，一个是交替执行

l 线程在运行中，一般会被中断，目的是给其他线程执行机会，雨露均沾

l 线程调用sleep()方法主动放弃所占用的CPU资源

l 调用yield()方法可以让运行状态的线程转入就绪状态

l join()方法是一个线程等待另外一个线程

3.3.4 优先级

值越小优先级越低，值越大优先级越高

package javapro.thread;

 

public class TestPriority {

    public static void main(String[] args) {

       Thread t = new Thread();

       System.out.println(t.MAX_PRIORITY);     //10

       System.out.println(t.NORM_PRIORITY);    //默认5

       System.out.println(t.MIN_PRIORITY);     //1

    }

}

3.3.5 线程B怎么知道线程A修改了变量 ？？？ 还没讲

3.4 单线程

3.4.1 单线程

单线程，顺序执行，不会变异

package javapro.thread;

 

public class TestSingleThread {

    public static void main(String[] args) {

       exec();

    }

   

    public static void exec() {

       System.out.println( “exec start” );

       fn1();

       fn2();

       System.out.println( “exec end” );

    }

   

    public static void fn1() {

       System.out.println( “fn1” );

    }

   

    public static void fn2() {

       System.out.println( “fn2” );

    }

}

执行结果

exec start

fn1

fn2

exec end

3.4.2 执行过程

日常大多程序都是按单线程过程执行的。

3.5 创建多线程的两种方式

l 继承Thread

l 实现Runnable

2.5.1 继承Thread

Thread类本质上是实现了Runnable接口的一个实例，代表一个线程的实例。启动线程的唯一方法就是通过Thread类的start()实例方法。Start()方法是一个native方法，它将通知底层操作系统，最终由操作系统启动一个新线程，操作系统将执行run()方法。这种方式实现多线程很简单，通过自己的类直接extend Thread，并复写run()方法，就可以启动新线程并执行自己定义的run()方法。

模拟开启多个线程，每个线程调用run()方法

package day13;

 

public class Test1 {

    public static void main(String[] args) {

       T1 t1 = new T1();

       T1 t2 = new T1();

       t1.start();

       t2.start();

       System.out.println("------");

    }

 

    static class T1 extends Thread {

       @Override

       public void run() {

           // 获得线程名

           String n = getName();

           // 打印1到100

           for (int i = 1; i <= 100; i++) {

              System.out.println(n + " - " + i);

           }

       }

    }

}

3.5.2 实现Runnable

如果自己的类已经extends另一个类，就无法直接extends Thread，此时，可以实现一个Runnable接口。

package day13;

 

public class Test2 {

    public static void main(String[] args) {

       //封装代码的对象

       R1 r1 = new R1();

       //代码交给线程

       Thread t1 = new Thread(r1);

       Thread t2 = new Thread(r1);

       //两个线程启动后，

       //都执行 r1.run()

       t1.start();

       t2.start();   

 

       //获得main线程

       Thread t = Thread.currentThread();

       String n = t.getName();

       System.out.println(n);

 

    }

 

    /* * 用来封装代码 * run()方法代码要放入线程执行 */

    static class R1 implements Runnable {

       @Override

       public void run() {

           //获得正在执行的线程对象

           Thread t = Thread.currentThread();

           String n = t.getName();

           //打印1到100

           for(int i=1;i<=100;i++) {

              System.out.println(n+" - "+i);  

           }

       }

    }

 

}

2.5.3 $\ast \ast 比较\ast \ast$∗∗比较∗∗

3.5.4 评论

【了解】多线程是一个非常棘手的概念，即使多年工作经验的开发者，提到多线程也是一脑袋浆糊。这里我们只要记住多线程会引发怎样的问题，已经多线程问题基础的解决方案即可。

3.6 线程状态

3.7 线程的方法

l Thread.currentThread()

获取当前正在执行的线程实例

l Thread.sleep(毫秒值时长)

当前线程暂停指定的毫秒值时长

l Thread.yield()

让步，主动放弃 cpu 时间片，让给其他线程执行

l getName(), setName()

l start()

启动线程,线程启动后,并行执行run()方法中的代码

l interrupt()

打断另一个线程的暂停状态,被打断的线程,会出现InterruptedException

l join()

当前线程暂停,等待被调用的线程接收后,再继续执行

a线程 -------------------------

b线程 ---------| |------------

           a.join()

l setDaemon(true)

后台线程、守护线程

JVM虚拟机退出条件，是所有前台线程结束，当所有前台线程结束，虚拟机会自动退出

不会等待后台线程结束

  例如：垃圾回收器是一个后台线程

l getPriority(), setPriority()

优先级,1到10,默认是5

package day13;

 

import java.text.SimpleDateFormat;

import java.util.Date;

public class Test3 {

    public static void main(String[] args) {

       T1 t1 = new T1();

       t1.start();

    }

 

    static class T1 extends Thread {

       @Override

       public void run() {

           SimpleDateFormat f =

                  new SimpleDateFormat("HH:mm:ss");     

           while(true) {

              String s = f.format(new Date());

              System.out.println(s);

              try {

                  Thread.sleep(1000);

              } catch (InterruptedException e) {

              }

           }

       }

    }

 

}

package day13;

 

import java.text.SimpleDateFormat;

import java.util.Date;

import java.util.Scanner;

public class Test3_v2 {

    public static void main(String[] args) {

       T1 t1 = new T1();

       t1.start();

 

       Thread t2 = new Thread() {

           @Override

           public void run() {

              System.out.println("按回车捅醒 t1");

              new Scanner(System.in).nextLine();

              t1.interrupt();

           }

       };

       //虚拟机不会等待后代线程结束

       //所有前台线程结束时，虚拟机会自动退出

       t2.setDaemon(true);

       t2.start();

    }

 

    static class T1 extends Thread {

       @Override

       public void run() {

           SimpleDateFormat f =

                  new SimpleDateFormat("HH:mm:ss");     

           for(int i=0; i<10; i++) {

              String s = f.format(new Date());

              System.out.println(s);

              try {

                  Thread.sleep(1000);

              } catch (InterruptedException e) {

                  System.out.println("被打断");

                  break;

              }

           }

       }

    }

}

package day13;

 

import java.text.SimpleDateFormat;

import java.util.Date;

import java.util.Scanner;

 

public class Test3_v3 {

    public static void main(String[] args) {

       T1 t1 = new T1();

       t1.start();

 

       Thread t2 = new Thread() {

           @Override

           public void run() {

              System.out.println("按回车捅醒 t1");

              new Scanner(System.in).nextLine();

              t1.interrupt();

           }

       };

       //虚拟机不会等待后代线程结束

       //所有前台线程结束时，虚拟机会自动退出

       t2.setDaemon(true);

       t2.start();

    }

 

    static class T1 extends Thread {

       @Override

       public void run() {

           SimpleDateFormat f =

                  new SimpleDateFormat("HH:mm:ss");     

           for(int i=0; i<10; i++) {

              String s = f.format(new Date());

              System.out.println(s);

              try {

                  Thread.sleep(1000);

              } catch (InterruptedException e) {

                  System.out.println("被打断");

                  break;

              }

           }

       }

    }

 

}

package day13;

 

public class Test5 {

    public static void main(String[] args) throws InterruptedException {

       //1000万内，有多少个质数

       //2,3,5,7,11,13,17,19,23....

       System.out.println("\n--单线程-----------------");

       f1();

       System.out.println("\n--5个线程-----------------");

       f2();

    }

 

    private static void f1() throws InterruptedException {

       long t = System.currentTimeMillis();

 

       T1 t1 = new T1(0, 10000000);

       t1.start();

 

       //main线程暂停等待 t1 的执行结果

       t1.join();

       int c = t1.count;

 

       t = System.currentTimeMillis()-t;

       System.out.println("数量："+c);

       System.out.println("时间："+t);

    }

 

    private static void f2() throws InterruptedException {

       long t = System.currentTimeMillis();

       int n = 5;

       int m = 10000000/n;

       T1[] a = new T1[n];

       for (int i = 0; i < a.length; i++) {

           a[i] = new T1(m*i, m*(i+1));

           a[i].start();

       }

       int sum = 0;

       for (T1 t1 : a) {

           t1.join();

           sum += t1.count;

       }

       t = System.currentTimeMillis()-t;

       System.out.println("数量："+sum);

       System.out.println("时间："+t);

    }

    static class T1 extends Thread {

        int from;

       int to;

       int count;//计数变量

       public T1(int from, int to) {

           if(from<3) {

              from = 3;

              count = 1;

           }

           this.from = from;

           this.to = to;

       }

       @Override

       public void run() {

           for (int i = from; i < to; i++) {

              if (isPrime(i)) {//判断i是否是质数

                  count++;

              }

           }

       }

       private boolean isPrime(int i) {

           /* * 从2到 (i开方+1) * 找有能把i整除的，i不是质数 * 都不能吧i整除，i是质数 */

           double d = Math.sqrt(i) + 1;

           for (int j = 2; j < d; j++) {

              if (i%j == 0) {

                  return false;

              }

           }

           return true;

       }

 

    }

 

}

3.8 线程共享访问数据冲突

package day13;

 

import java.util.Arrays;

 

public class Test6 {

  static char[] a = {'-','-','-','-','-'};

  static char c = '*';

  public static void main(String[] args) {

      Thread t1 = new Thread() {

          @Override

          public void run() {

             while(true) {

                for (int i = 0; i < a.length; i++) {

                   a[i] = c;

                }

                

                c = (c=='*'?'-':'*');

             }

          }

      };

      Thread t2 = new Thread() {

          @Override

          public void run() {

             while(true) {

                System.out.println(Arrays.toString(a));

             }

          }

      };

    

      t1.start();

      t2.start();

  }

}

3.9 线程同步 ??? 还没讲