Java常问问题
部分算法概念
分治算法：将大问题分割成规模比较小的相同问题，以便各个击破，比如快速排序，归并排序
贪心算法：总是做出当前看来是最优的解，而不是整体上加以考虑，只是局部最优解，比如最小生成树。
动态规划算法：思想也是把大问题分解成若干子问题，然后分别去解子问题，与分治算法不同的是，动态规划分解的子问题一般不是相互独立的，并且一般都是分阶段的，动态规划算法中不会重复求解一些子问题，而会把子问题的结果保存下来，这样可以降低时间复杂性。斐波那契数列
回溯算法：首先会有一个解空间，状态空间树，显示约束用于筛选可行解，即显示约束决定了状态空间树的规模，约束函数来源于隐式约束，可以避免搜索无用结点，也就是不含答案状态的结点，剪枝函数可以避免搜索不含最优解的结点。
分支限界和回溯算法类似，但不同的是，分支限界通过广度优先来找满足约束函数的解，而回溯算法使用深度优先找满足约束函数的解。
和Vector
ArrayList 只进行初始化时而不添加元素时，数组大小为0，当添加元素时直接初始化size为10（若指定了初始化容量则直接进行初始化），之后扩容按1.5倍扩，无加载因子，放满之后才进行扩容。数组实现，线程不安全，对于不要求并发情况时，速度优于vector。
Vector 初始化时不添加元素就会申请size为10的数组，之后扩容按2倍扩，无加载因子，放满进行扩容。数组实现，线程安全，支持线程同步。
LinkedList底层双向链表
初始化时不申请空间，添加元素时才真正初始化空间，初始容量为16，加载因子为0.75，即添加第13个元素的时候会进行扩容，直接扩为原来容量的2倍，线程不安全
当某一个哈希值对应的元素超过8个时，也会进行扩容，扩容两次之后直接进行树化
LinkedHashMap底层还是使用HashMap，但是它维护了一个双向链表，所以输出的顺序可以和输入的顺序是一致的，LinkedHashMap同理。
初始化不需要添加即可直接分配空间，初始化容量为11，加载因子为0.75，扩容为2*原容量+1。线程安全，键和值都不可以为空。不会树化
底层是红黑树，保存的对象需要能比较，即对象自己实现comparable接口或者新建TreeMap时传入一个comparator实现类用来比较对象。
5.集合去重机制
HashSet去重依赖于hashcode()和equals方法，hashcode相同时映射到同一个哈希表的同一个地址，然后使用equals()方法与这个地址上的其他对象逐一进行比较，若equals()方法判断为true时，则认为两个对象相同，不进行加入。
TreeSet则使用新建时传入的comparator实现类的compare方法，或对象自己实现comparable接口的compareTo()方法进行比较，判定相同则不进行加入。
接口
-
Serializable接口是一个标志性接口，没有任何方法，只是当类实现了这个接口之后，虚拟机会把这个类进行序列化。
-
Java存储对象或在网络间进行传输对象时都是以二进制流的形式，所以这个时候就需要对对象进行序列化。
-
同时虚拟机对象进行序列化以后，会给这个类分配一个序列号来标识这个类，也可以手动给这个类指定一个序列号，这样当版本更新，类进行了代码修改时，虚拟机依然会认为这是同一个类，保证兼容以前的版本。
-
需要保证当前属性也是可序列化的，当不希望类中某个属性进行序列化时，可以给这个类加上transient关键字。
7.锁机制
四种状态
悲观锁：想法比较悲观，每次操作数据前都会假设其他线程也可能会操作这个数据，所以每次操作都会上锁。适用于竞争比较激烈的场景，当竞争激烈时，使用乐观锁还会导致线程不断重试，降低性能。
乐观锁：想法比较乐观，认为资源竞争不是很激烈，乐观锁操作数据时不会上锁，只是在更新的时候判断一下有没有其他线程更新过这个数据。使用CAS(compare and swap)算法实现，适用于竞争不是很激烈的场景，不用上锁，释放锁，省去了锁的开销，提升了吞吐量。
独占锁：指锁一次只能被一个线程所持有，如果一个线程对数据加排他锁后，其他线程不能对数据加任意类型的锁，获得独占锁的线程既能读数据又能写数据。
共享锁：当一个线程对数据加共享锁之后，其他线程也只能对数据加共享锁，不能加独占锁，持有共享锁的线程仅能读数据，不能写数据。
公平锁：各个线程获取锁的顺序按申请的顺序来获取锁，类似排队买票。
非公平锁：各个线程获取锁的顺序并不是按照申请锁的顺序，有可能后申请的线程先获取锁，可能导致饥饿。
可重入锁：指同一个线程在外层方法获取了锁，进入内层方法会自动获取锁。在外层方法获取了锁，调用内层就不需要再次获取锁了，如一个被synchronized修饰的方法调用另一个被synchronized修饰的方法。ReentrantLock
自旋锁：线程没有获取锁时不是被直接挂起，而是一直处于忙等的状态。
无锁：未对资源进行锁定，不会出现在多线程下或即使出现在多线程环境下也不会出现竞争
偏向锁：锁对象会偏向于第一个访问锁的线程，如果只有一个线程访问加锁的资源时，不存在多线程的情况，那么线程不需要获取锁，这时候仅仅给线程加一个偏向锁，实现依靠对象头中存储的标志位和线程ID
轻量级锁：线程竞争变得激烈时，偏向锁升级成为轻量级锁，轻量级锁认为虽然竞争存在，但程度很低，可以通过自旋方式等待上一个线程释放锁。
重量级锁：多个线程并发访问资源，竞争激烈。
ReentrantLock：可重入锁，这个锁的实现是一种自旋锁，通过循环调用CAS操作来实现加锁，因为不需要使线程进入内核态的阻塞状态，所以性能较好。
synchronized：可修饰方法，代码块，用的是Java的锁升级机制，偏向锁->轻量级锁->重量级锁。
修饰的对象锁和类锁
实现对象锁的两种方式
- 代码块方式
synchronized(this){}
synchronized(lock){}
-
修饰run()方法
在run()方法上直接加synchronized，相当于把当前对象作为锁
实现类锁的两种方式
- 代码块方式
synchronized(){}
-
修饰静态方法
在静态方法上修饰的synchronized默认以当前类作为锁对象。
的性质
- 同步机制底层实现
synchronized底层实现是基于指令monitorenter和monitorexit，进入同步代码块执行monitorenter获取锁，退出同步去代码块执行monitorexit释放锁。
- 可重入原理
对象头中存放了一个线程ID和锁状态标志，当线程第一次访问时，检查锁状态，如果锁状态等于0，则代表该锁没有被占用，则使用CAS操作获取锁；若锁状态不等于0，则说明该锁已经被占有。当线程第二次获取锁时，先对象头中检查线程ID是与当前线程相匹配，若匹配则锁状态直接加一，线程退出同步代码块时，锁状态标志位减一，当锁状态标志减为0时则释放锁。
- 可见性
线程A在synchronized修饰的代码块中执行的结果可以被线程B及时看见，因为在synchronized内执行类似一次事务，在一系列操作并保存结果后才会退出，只有为实现线程同步的方法才会有不可见性问题。
- synchronized和lock选择
synchronized释放锁的情况单一，只有当正常结束或抛出异常时才会释放锁，不够灵活。
lock锁可以选择加锁和释放锁的时机，更灵活，但如果忘记释放锁很危险。
10.实现多线程的方式
两种：继承Thread类和实现Runnable接口
两种方法本质是一样的，都是执行了Thread类的run()方法，但是继承Thread类的方式是重写了run方法，而实现了Runnable接口的方式是，在Thread类的run方法里调用传进去的实现了Runnable接口的类的run方法。
实现Runnable接口的方式更好
1.线程的任务，即run()方法里面的内容应该和线程的生命周期函数是解耦的，实现Runnable接口的类应该指明线程执行的任务，Thread类里应该都是线程的生命周期函数和线程相关的操作。
2.用Thread类每次想新建一个任务都需要去新建一个独立的线程，这样损耗较大，使用Runnable就可以使用线程池，可以节省创建，销毁线程所消耗的资源。
3.继承了Thread类以后，由于java是单继承机制，这样就不能继承其他类了，大大限制了可扩展性。
线程池：不是一种新的实现多线程的方法，线程池跟进源码中可以看出来是由ThreadFactory来创建的线程，类似工厂模式，这个TheadFactory最终创建线程也是通过新建一个Thread类把Runnable传进去来实现的，还有一些像是callable，定时器什么的其实都是对实现Runnable接口进行了封装，所以本质上并不算一个新的实现多线程的方法。
11.启动线程
()和()都可以执行run方法中内容，但是直接调用run方法的方式属于普通调用，不会开设一个新的线程，start方法才会真正启动一个新的线程。
12.停止线程
()这个方法可以把线程的中断位置为1，但是不会立即中断线程，当线程执行到一定阶段完成了一系列保存工作后自行检查中断位，再自行抉择要不要中断。这样会把中断线程的权利交给线程本身，而不是其他线程，因为只有需要中断的线程本身才更清楚自己的执行状况。
当线程阻塞时中断位置为1会抛异常，但是在抛异常之后中断位会被清除，如果在方法中处理不了异常应该向上层抛出异常或恢复中断位。
()已经被弃用（直接中断线程），suspend()方法也被弃用（带锁中断）
volatile修饰的标记位看似可行，但是遇到阻塞队列是不可行，因为当生产者生产的对象放满阻塞队列时就不会去检查中断，而只有每次生产过程中会检查中断，而消费者把标记位置为1时，生产者并不会检查，所以生产者进程将会永久阻塞，只有当生产速度比消费速度慢时这种方法才是可行的。
线程的状态
- new，只要新建一个线程而未启动，则处于这个状态
- runnable，线程执行start()方法以后，无论有没有上机执行，只要不是阻塞，都是这个状态，对应操作系统的就绪态和运行态
- blocked，进入synchronized修饰的相关方法而没有获取到锁
- waiting，线程执行了wait()，join()等方法，不计时等待
- timed_waiting，线程执行了sleep(time)，wait(time)，join(time)方法以后，进入计时等待状态
- terminated，终止态
14.线程重要方法
-
wait()是锁级别的阻塞方法，任何对象都可以在线程内调用wait()，意思是以这个对象为锁，释放锁并阻塞，即便没有线程要使用该锁，也会停等，仅当其他线程调用这一对象的notify()方法或notifyAll()方法时，会唤醒。
-
wait(time)，意思是释放锁阻塞对应的时间之后，如果该锁空闲就会重新获取该锁执行，若该锁被占用，则继续等待。与sleep(time)区别在于，这个方法是带锁阻塞。
-
sleep()是Thread类的静态方法，线程可任意调用这个方法，仅仅是线程级别的方法，对于一个线程而言的，不涉及多个线程，所以不用放在同步代码块中。wait()是Obejct类的方法，即任意对象都可以成为一把锁，并且必须放在同步代码块中，因为必须保证代码按顺序执行，如果不放在同步代码块里，在多线程的场景下可能会出现先唤醒再阻塞的代码顺序。
-
join()也可以响应中断，在中断之后就不能再等待其他线程了。其原理相当于把等待的线程作为锁，执行线程的wait()方法，因为线程作为锁的话，当线程生命周期结束会自动唤醒以这个线程作为作为锁的线程。即A、B是2个线程，B线程执行了()方法，A线程执行结束后会自动唤醒B线程。
-
yield()方法，释放时间片，但不释放锁，且状态不会成为阻塞状态，还是runnable状态。
15.守护线程
由JVM启动的为用户线程提供服务的线程。守护线程并不影响JVM的退出，即当用户线程运行完毕后，即便还有守护线程存在，JVM也会退出。
16.单例模式
单例模式的实现有两种方式：饿汉式和懒汉式
饿汉式：设置静态属性，声明的时候直接创建实例，简单，可能出现资源浪费问题。
懒汉式：在需要的时候创建，有线程安全问题。单检查方式每次获取对象都需要获取锁，并发性能非常差，双检查可以解决并发安全和性能低效的问题。
懒汉式 单检查
public static Singleton getInstance() {
if (singleton == null) {
singleton = new Singleton();
}
return singleton;
}
懒汉式 双检查
public static Singleton getInstance() {
if (singleton == null) {
synchronized(Singleton.class) {
if (singleton == null) {
singleton = new Singleton();
}
}
}
return singleton;
}
本地线程
ThreadLocalMap其实是Thread线程的一个属性值，而ThreadLocal是维护 ThreadLocalMap这个属性指的一个工具类。也就是每一个线程内部都有一个map类型的数组，但并不是真正的map，而是一个Entry数组，value值存在Entry数组中，而key正是ThreadLocal的弱引用，这里设置成为弱引用的意思就是，若这个ThreadLocal对象在栈中的引用已经没了，或者说这个这个ThreadLocal对象已经使用完毕了，那就只剩下Entry中的弱引用了，下次垃圾回收就可以把这个对象回收了，而不会造成内存泄漏的问题。如果这个引用是强引用，则只要这个线程存在，那这个ThreadLocal对象就不会被回收，会导致内存泄漏。如果这个Threadlocal对象被回收，那这个map中就是key为null，而value不为null，这样只要在调用get，set和remove都会把这个value置空，垃圾回收时也会被这个对象清除。
这个ThreadLocal管理的变量是每个线程独享的变量，而synchronized主要是多个线程共享的变量。
这个ThreadLocal管理的变量父子线程是不可继承的，InheritableThreadLocal类主要用于父子线程继承的。
锁
是可重入锁，底层基于CAS操作，默认使用非公平锁，也可以实现公平锁。
底层基于数组+链表+红黑树，并发安全，使用到了分段锁，锁的粒度是哈希数组的每一个元素，也就是哈希映射到的每一个值。
20.权限修饰符
private 只能在同一个类中进行访问
protected 不同包下的子类可以访问
默认 同一个包下
public 所有
instanceof 判断某对象是否属于某种类型
封装：把类的细节隐藏起来，让外界通过特定的接口来访问类。
继承：使用已有的类的定义作为基础建立新类，子类可以继承父类非private属性和方法，也可以进行扩展。
多态：多态是同一个行为具有多个不同表现形式或形态的能力
线程私有（虚拟机栈，本地方法栈，程序计数器），线程共用（方法区，堆）
判断是否是垃圾使用可达性分析算法，也就是根搜索算法
标记清除：分为两个阶段，一个是标记阶段，
编译时多态：重载都是编译时多态。
运行时多态：子类对象赋给父类的引用。