本系列出于AWeiLoveAndroid的分享，在此感谢，再结合自身经验查漏补缺，完善答案。以成系统。
Java基础
- java中==和equals和hashCode的区别
http://blog.csdn.net/dove_knowledge/article/details/71027170
- == 基本类型比较的是值 引用类型针对的是变量在堆内存的地址
- equals 针对引用类型 Object默认实现是 this==object，这个可以在子类中复写决定equals是否相等。示例 String a = new String("abc")
String b = new String("abc") a==b 返回false a.equals(b)返回true，原理是String的equals方法为:
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String) anObject;
int n = length();
if (n == anotherString.length()) {
int i = 0;
while (n-- != 0) {
if (charAt(i) != anotherString.charAt(i))
return false;
i++;
}
return true;
}
}
return false;
}
public int hashCode() {
int h = hash;
final int len = length();
if (h == 0 && len > 0) {
for (int i = 0; i < len; i++) {
h = 31 * h + charAt(i);
}
hash = h;
}
return h;
}
- hashCode Object中的hashCode返回的就是其内存地址的int值，对于两个对象如果没有重写hashCode方法，则两个对象的hashCode值不可能相等。hashCode方法一般不会交由用户来用，例如在hashmap中，由于key是不可以重复的，它在判断key是否重复时就判断了hashCode()方法，而且也用到了equals()方法。此处“不可以重复”指的是equals()和hashCode()只要有一个不等就可以了。所以一般equals和hashCode应该同时被重写。
- hashCode()方法的返回值和equals()方法的关系如下：x.equals(y)返回true，即两个对象根据equals()方法比较是相等的，那么调用这两个对象中任意一个对象的hashCode()方法都必须产生同样的整数结果。
- int、char、long各占多少字节数
- int与integer的区别
- Integer是int的包装类，int是基本类型
- Integer变量必须先实例化，int变量不需要
- Integer变量是一个对象的引用，int变量直接存储的值
- Integer默认值null ，int默认值0
https://www.cnblogs.com/guodongdidi/p/6953217.html
- java的Integer源码解析与自动拆箱与装箱
特别注意源码中IntegerCache所定义的-128到127的缓存，这点决定了一些判等问题的结果
http://blog.csdn.net/chenliguan/article/details/53888018
- Java中如何解决double和float精度不准的问题
BigDecimal解决精度不准问题
public static double add(double d1,double d2){
BigDecimal b1=new BigDecimal(Double.toString(d1));
BigDecimal b2=new BigDecimal(Double.toString(d2));
return b1.add(b2).doubleValue();
}
- 谈谈对java多态的理解
- java的三大特性(继承，封装，多态)之一
- 定义:允许不同类的对象对同一消息作出反应。即同一消息可以根据发送对象的不同而采用多种不同的行为方式(消息也就是函数调用)。
- 父类引用指向子类对象
- 具有 可替换性，可扩展性，接口性，灵活性，简化性的好处。
- String、StringBuffer、StringBuilder区别
- String 是字符串常量，StringBuffer和StringBuilder是字符串变量
- 对String的操作JVM，拷贝旧的再创建个新的，同名的String对象会在JVM中回收重建。
- StringBuffer和StringBuilder都继承自AbstractStringBuilder，这里面含有一个char[] value 成员，用来存储字符。append就是不断的改变value的容量以存储字符串的。
- 从源码角度看，StringBuffer的很多操作方法前面都有synchronized修饰符，而StringBuilder中并没有。也就是说StringBuffer的操作是线程安全的。
- 结论：
从操作速率上 StringBuilder>StringBuffer>String
从线程安全上 StringBuffer线程安全的，StringBuilder和String非线程安全
- 内部类？内部类的分类？内部类与闭包
https://www.cnblogs.com/dolphin0520/p/3811445.html
- 定义:定义在一个类或者方法内的类
- 类型: 成员内部类，局部内部类，匿名内部类，静态内部类
- 作用:
- 使得Java多继承的解决方案得到完善
- 有利于代码的独立于封装
- 每个内部类都能独立地继承一个（接口的）实现，所以无论外围类是否已经继承了某个（接口的）实现，对于内部类都没有影响。
- 静态内部类的设计意图
要从静态内部类和非静态内部类的特点来看。静态内部类对象的创建不依赖其所在外部类的实例，静态内部类可以有静态成员和方法，但是不能直接访问外部类的非静态成员和方法。从这些特点上来看更是为了不全内部类的设计。- 闭包和局部内部类的区别
- 比表的解释:闭包就是把函数以及变量包起来，使得变量的生存周期延长。
- Java中通过接口和内部类来实现闭包
- 注意:
- 非静态内部类会持有外部类的引用，从class文件可以看出，这也就是内部类能访问外部类成员的原因
- 内部类对象的创建:
外部类.内部类 a = 外部类对象.new 内部类();
静态内部类对象的创建
外部类.内部类 a = new 外部类.内部类();- 局部内部类，匿名内部类访问局部变量加final的原理:局部变量的生命周期是方法内，局部内部类要访问局部变量时可能该变量已经over了，为此在编译阶段jvm会将局部变量进行拷贝然后放到局部类的class文件中，为了保证这个拷贝的变量不会再发生变化，导致局部内部类里的值不是最终的，java语法规定局部内部类访问局部变量时必须用final修饰。
- 抽象类和接口区别
接口:行为规范
抽象类:事物抽象
区别点:默认方法实现，实现关键字，构造器，与普通类的区别，访问修饰符，main方法，多继承，速度，添加新方法九个区别点。
http://www.importnew.com/12399.html
- 抽象类的意义
- 为子类提供一个公共的类型；
- 封装子类中重复内容（成员变量和方法）；
- 定义有抽象方法，子类虽然有不同的实现，但该方法的定义是一致的
- 接口的意义
提供了行为规范。保证访问的统一性。利于程序的维护和扩展。
https://www.cnblogs.com/zhaoyanjun/archive/2016/03/25/5320034.html
- 泛型的理解
http://www.importnew.com/24029.html
- 泛型中extends和super的区别(PECS原则)
- T extends A : A及A的子类，返回型 例如 T get()类
- T super A : A及A的父类, 参数型 例如 add(T a)类
- 泛型擦除
- 现象就是编译后的泛型将变为 Object或者bound类型(例如 T extends Comparable 泛型擦除后会变为 Comparable)
- 带来的问题: 1. 不允许创建泛型数组; 2. Bridge method会导致与多态冲突; 3. E elem = new E()不行,这个问题可以通过反射解决; 4. 无法对泛型代码直接使用instanceof关键字
- 父类的静态方法/静态属性能否被子类重写？
因为静态方法在运行时就分配好内存，也就是固定好了，后面父类还是子类使用时都是使用同一块内存区域的代码，子类中有重名的，也会为其单独分配块内存。可见静态方法/静态属性的继承性质在，但是被隐藏了，但谈不上重写。
- 枚举的知识点
http://blog.csdn.net/javazejian/article/details/71333103
- 这个知识点关键是反编译枚举的.class文件。
- 特点:使用enum修饰，继承自Enum类而不是Object;非抽象枚举类默认会加上final修饰，不能再被继承；枚举类构造器默认private也只能用private修饰；枚举示例在第一行搞定，否则再也没法创建示例了。
- transient的作用
- 一旦变量被transient修饰，变量将不再是对象持久化的一部分，该变量内容在序列化后无法获得访问。
- transient关键字只能修饰变量，而不能修饰方法和类。注意，本地变量是不能被transient关键字修饰的。变量如果是用户自定义类变量，则该类需要实现Serializable接口。
- 被transient关键字修饰的变量不再能被序列化，一个静态变量不管是否被transient修饰，均不能被序列化。
- 只配合到Serializable，Parcelable则是自定义序列化的，与是否有transient修饰无关
- volatile关键字引发的并发编程知识
http://www.importnew.com/18126.html
- 内存模型基础概念：
cpu + 高速缓存 + 主存；
简单理解：cpu 将内存中的内容拿到高速缓存中，处理完后将结果放回主存，当多线程时就会出现缓存不一致问题；
解决这个有两个方案一个是总线锁，就是在操作变量内存空间时加上总线锁，其它线程要操作这块内存需要等其它线程释放锁后才行;
另一个方案是缓存一致协议，线程1操作时会将内存置为无效，线程2发现无效就去主存拿了。- 并发编程的三个概念:
原子性(转账一减一加必须一气呵成，不能终端)。
可见性(你拿走去处理了，处理好要告诉我，否则我再拿的时候还是旧的)。
有序性(指令重排序可能会让你写的代码不是自上而下执行，但是人家会保证结果如排序一样，所以当上下发生数据依赖时，人家不会乱执行的)；
由上可知，要想写好并发编程，必须要同时保证原子性，可见性和有序性，缺一不可！- JMM(Java内存模型)
Java内存模型并没有限制执行引擎使用处理器的寄存器或者高速缓存来提升指令执行速度，也没有限制编译器对指令进行重排序。
Java内存模型规定所有的变量都是存在主存当中（类似于前面说的物理内存），每个线程都有自己的工作内存（类似于前面的高速缓存）。线程对变量的所有操作都必须在工作内存中进行，而不能直接对主存进行操作。并且每个线程不能访问其他线程的工作内存。- Java对原子性，可见性，有序性的保障
原子性：只有读取和赋值是原子操作
可见性: 用volatitle关键字保证可见性；通过synchronized和Lock也能够保证可见性，synchronized和Lock能保证同一时刻只有一个线程获取锁然后执行同步代码，并且在释放锁之前会将对变量的修改刷新到主存当中。因此可以保证可见性。
有序性: volatile关键字来保证一定的“有序性;synchronized和Lock保证每个时刻是有一个线程执行同步代码，相当于是让线程顺序执行同步代码，自然就保证了有序性;happens-before原则保证了先天有序性。- volatile关键字
(1) 保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。（本质上用的是缓存一致协议的思路保证了可见性）
(2) 禁止进行指令重排序。(假如有 1 2 3 4 5条语句，3有volatile修饰 则执行顺序上 3可不能在 1 2 前 也不可能在 4 5后 ，并且到3时 1 2肯定是完事了，且对 3 4 5可见。但是这里不能保证 1 2 或者 4 5 是否会被重排序，故而说volatile能在一定程度上保证有序性)- volatile作用的祖坟级原理
volatile修饰的语句，在汇编时会在前面加一个Lock前缀指令，这个指令又称内存栅栏，volatile之所以能有如此作用，关键是靠这个内存栅栏：
- 内存栅栏能确保重排序时不越过此栅栏，前者不能其后，后者不可到其前;
- 强制对缓存的操作立即写入内存
- 如果是写操作，它会导致其它cpu中的缓存无效
- volatile应用场景
volatile主保可见性，难保原子性，所以不能完全替代synchronized所保的原子性和有序性。但在一些情况下用volatile效率要高于synchronized。常见场景如下:状态标记量 : 一个状态变量
double check: 例如单例双重锁写法中的静态instance可以用volatile修饰
- synchronized关键字
http://www.importnew.com/23511.html
synchronized可以保证方法或者代码块在运行时，同一时刻只有一个方法可以进入到临界区，同时它还可以保证共享变量的内存可见性
- 进程和线程的定义，关系与区别
https://www.cnblogs.com/lgk8023/p/6430592.html
- 进程：狭义上就是一段程序的执行过程，广义上为具有一定独立功能的程序在某个数据集合上的一次活动，进程是操作系统分配资源的基本单位
- 线程:是进程的组成部分，一个进程可以有多个线程，而一个线程必须有一个父进程。线程可以拥有自己的堆栈，自己的程序计数器和自己的局部变量，单不能拥有系统资源。它与父进程和其它线程共享其父进程的所有资源。
- 进程线程的关系:
- 一个进程可以有多个线程，但至少有一个线程，一个线程只能属于一个进程。
- 资源分配给的是进程，进程内的线程共享该进程的系统资源。
- 处理机分配个线程，即真正在处理机上运行的是线程
- 线程在执行过程中，需要协同同步。进程的同步需要通过消息机制。线程是进程中的一个执行单元，也是进程的可调度实体。
- 区别:
- 调度: 进程是拥有资源的基本单位，线程作为调度和分配的基本单位。
- 并发性: 进程可以并发，进程内的多个线程也可以并发
- 拥有资源:进程是拥有资源的独立单位，线程不拥有资源，但可以访问进程所拥有的资源。
- 系统开销:在创建和撤销进程时，由于系统要分配和回收系统资源，导致明显大于创建和销毁线程的开销。
- final，finally，finalize的区别
http://blog.csdn.net/stypace/article/details/42102181
- final : 修饰符，于类时类不可被继承，于变量时变量不可变，于方法时方法不可被重写。
- finally: try catch finally，finally标示程序总是会被执行。用于清楚或者释放资源等。这里注意一点:try 和 finally有return的执行情况。
- finalize: object中的方法，在垃圾回收器认为该对象无用，在清理前会调用此方法，子类重写该方法意在做一些回收前的清理工作。
- 序列化的方式Serializable 和Parcelable 的及区别
http://blog.csdn.net/Double2hao/article/details/70145747
- S简单，P效率高
这是Android中IPC的基础，详解IPC请参考https://www.jianshu.com/p/7a613ae4f83b
- string 转换成 integer的方式及原理
// 会抛出NumberFormatException异常
public static Integer valueOf(String s) throws NumberFormatException {
return Integer.valueOf(parseInt(s, 10));
}
public static Integer valueOf(int i) {
//如果 >-128 && < 127 则直接从缓存中获取
if (i >= IntegerCache.low && i <= IntegerCache.high)
return IntegerCache.cache[i + (-IntegerCache.low)];
return new Integer(i);
}
/**
* <p>Examples:
* <blockquote><pre>
* parseInt("0", 10) returns 0
* parseInt("473", 10) returns 473
* parseInt("+42", 10) returns 42
* parseInt("-0", 10) returns 0
* parseInt("-FF", 16) returns -255
* parseInt("1100110", 2) returns 102
* parseInt("2147483647", 10) returns 2147483647
* parseInt("-2147483648", 10) returns -2147483648
* parseInt("2147483648", 10) throws a NumberFormatException
* parseInt("99", 8) throws a NumberFormatException
* parseInt("Kona", 10) throws a NumberFormatException
* parseInt("Kona", 27) returns 411787
* </pre></blockquote>
*
* @param s 要转换的字符串
* @param radix 进制 2 8 10 16
* @return
* @exception NumberFormatException if the {@code String}
* does not contain a parsable {@code int}.
* 作用是把传入的字符串s解析单做radix机制的字串，解析成十进制int值。也就是在传值的时候要对应好例如不能10的radix传个里面有F的
*/
public static int parseInt(String s, int radix)
throws NumberFormatException
{
//这里有这个警告是因为valueOf方法使用了parseInt方法和IntegerCache对象，
//因为valueOf在IntegerCache初始化之前使用导致异常情况。后面会详细分析。
//抛空异常
if (s == null) {
throw new NumberFormatException("s == null");
}
//下面三个if用来判断参数是否合法。radix大小在2~36之间。
if (radix < Character.MIN_RADIX) {
throw new NumberFormatException("radix " + radix +
" less than Character.MIN_RADIX");
}
if (radix > Character.MAX_RADIX) {
throw new NumberFormatException("radix " + radix +
" greater than Character.MAX_RADIX");
}
int result = 0;//解析结果
boolean negative = false;//是否是负数
int i = 0, len = s.length();//索引变量和字符串长度
int limit = -Integer.MAX_VALUE;//最值限制
int multmin;//基数下的最小值
int digit; //记录每一位的数字
if (len > 0) {
//处理第一个字符
char firstChar = s.charAt(0);
if (firstChar < '0') { //非数字
if (firstChar == '-') {//开头为“-”
negative = true;//负数标志为true
limit = Integer.MIN_VALUE;//最值为Integer最小值
} else if (firstChar != '+')//不是“+”号，直接抛异常
throw NumberFormatException.forInputString(s);
if (len == 1) //非数字且只有一个符号也直接抛异常
throw NumberFormatException.forInputString(s);
i++;
}
multmin = limit / radix;
while (i < len) {
//利用了Character类中的digit非法，作用是解析一个字符。
digit = Character.digit(s.charAt(i++),radix);
//进行异常判断。
//这个解析字符串为数字的算法和平时想到的不太一样，是从字符串左边开始，初始化结果是0，
//其实是把结果算成负的，返回的时候再转回来。result -= digit;
if (digit < 0) {
throw NumberFormatException.forInputString(s);
}
if (result < multmin) {
throw NumberFormatException.forInputString(s);
}
//根据进制转为10进制数字
result *= radix;
if (result < limit + digit) {
throw NumberFormatException.forInputString(s);
}
result -= digit;
}
} else {
throw NumberFormatException.forInputString(s);
}
return negative ? result : -result;
}
java深入源码级的面试题（有难度）
- java虚拟机基础 GC回收算法
http://blog.csdn.net/tonytfjing/article/details/44278233
- JVM 结构: 类的加载器，运行时数据区[方法区、堆、Jvm栈，本地方法栈，程序计数器],执行引擎，本地接口。
- 内存分配:静态内存，动态内存。JVM机栈，本地方法，程序计数器随线程生灭，方法区和堆与运行有关。
- 垃圾检测: 引用计数法，可达性分析法
- 回收算法: 标记-清除(清除后又大量碎片)；复制(复制移动，需要额外的内存空间) ;标记整理(标记-清除-压缩移动);分代收集算法(不同生命周期的对象采用不同的回收算法-年轻代(复制)，年老代(标记-整理)，持久代(管不了))。
- 类的加载机制，双亲委托机制
- 类加载器和双亲委托机制
http://blog.csdn.net/zhangliangzi/article/details/51338291
- 类相等判定条件:统一个Class文件，同一个虚拟机，同一个类加载器
- Java“相等”判定相关方法：
- obj1.equals(obj2):引用是为同一个实例对象
- class.isInstance(obj)；obj是否为某个类，或者子类，子接口的实例。
- obj instanceof class；实例对象是否为某个类、接口的实例
- class1.isAssignableFrom(class2)；一个类是否为另一个类本身或其子类、子接口
- 类加载器分类:
- Bootstrap ClassLoader:启动类加载器，加载Java核心类库，注意这个类是C++实现，不继承者ClassLoader。加载目录为%JAVA_HOME%/lib)目录下的rt.jar
- Extension ClassLoader：扩展类加载器，加载目录为%JAVA_HOME%/jre/lib/ext)下的jar包
- System ClassLoader\APP ClassLoader：CLASSPATH,用户自定义的类
- 以组合关系复用父类加载器,非继承也
- 双亲委托模型：本质基于类的加载器的关系，组合成父子。定义上就是要找类先让父找，父没找到再自己找。
- 哪些情况下的对象会被垃圾回收机制处理掉？
- 引用计数法，可达性分析法决定引用计数为0，或根不可达
- 表现: 对象超出了使用空间，即没有用。对象=null时
- 讲一下常见编码方式？
https://www.cnblogs.com/yuan1164345228/p/6937958.html
ASCII---GBKXXX---Unicode---UTF-8---UTF-16
- utf-8编码中的中文占几个字节；int型几个字节？
*占2个字节的：带有附加符号的拉丁文、希腊文、西里尔字母、亚美尼亚语、希伯来文、阿拉伯文、叙利亚文及它拿字母则需要二个字节编码
- 占3个字节的：基本等同于GBK，含21000多个汉字
- 占4个字节的：中日韩超大字符集里面的汉字，有5万多个
- 一个utf8数字占1个字节
- 一个utf8英文字母占1个字节
- 少数是汉字每个占用3个字节，多数占用4个字节。
- 静态代理和动态代理的区别，什么场景使用？
- Java的异常体系
http://blog.csdn.net/htq__/article/details/51024881
Java异常体系.png
- 谈谈你对解析与分派的认识。
http://blog.csdn.net/u011080472/article/details/51334288
- 基本概念:
Person p = new Man(); Person是静态类型，Man是动态类型
java虚拟机中提供了5条方法调用字节码指令:
invokestatic:调用静态方法，解析阶段确定
invokeSpecial:调用实力构造器<init>方法，私有方法和父类方法,解析阶段可确定。
invokevirtual:调用虚方法
invokeinterface:调用接口方法
invokedynamic：先在运行时动态解析出调用点限定符所引用的方法，然后再执行该方法
Java中方法调用的目标方法在Class文件里面都是常量池中的符号引用，在类加载的解析阶段，会将其中的一部分符号引用转化为直接引用。- 解析:
“编译期可知，运行期不可变”的方法调用称为解析，解析的方法取决于两个指定 invokeStatic 、invokeSpecial- 分派：解析一定是静态的过程，分派可能是静态，也可能是动态。分派是多态性的体现。重载为静态分派，重写为动态分派
- 静态分派:所有依赖静态类型来定位方法执行版本的分派动作称为静态分派，只会涉及重载,静态分派的最直接的解释是在重载的时候是通过参数的静态类型作为判断依据。
- 动态分派:直接的例子是重写（Override），运行期根据方法接收者的实际类型来选择方法。当调用invokevirtual指令就会把运行时常量池中符号引用解析为不同的直接引用，这就是方法重写的本质。invokevirtual指令的工作过程是，优先寻找当前类中是否有该方法，如有直接选择该方法，若没有找到，则在父类中寻找，直到找到为止。
- 修改对象A的equals方法的签名，那么使用HashMap存放这个对象实例的时候，会调用哪个equals方法？
?
- Java中实现多态的机制是什么？
https://www.cnblogs.com/TalkWithWorld/p/5641169.html
靠的是父类或接口定义的引用变量可以指向子类或具体实现类的实例对象.
重载和重写
- 如何将一个Java对象序列化到文件里？
http://blog.csdn.net/leefengboy/article/details/52724019
ObjectOutputStream的writeObject
- 说说你对Java反射的理解
https://www.jianshu.com/p/5c67db64e192
java反射机制是在运行状态中，对于任意一个类，都能够知道这个类的所有属性和方法；对于任意一个对象，都能够调用它的任意一个方法和属性；这种动态获取的信息以及动态调用对象的方法的功能称为java语言的反射机制。
- 说说你对Java注解的理解
https://www.jianshu.com/p/5c67db64e192
注解（Annotation），也叫元数据。一种代码级别的说明。它是JDK1.5及以后版本引入的一个特性，与类、接口、枚举是在同一个层次。它可以声明在包、类、字段、方法、局部变量、方法参数等的前面，用来对这些元素进行说明，注释。
- 说说你对依赖注入的理解
- 依赖注入(Dependency Injection)和控制反转(Inversion of Control)是同一个概念。具体含义是:当某个角色(可能是一个Java实例，调用者)需要另一个角色(另一个Java实例，被调用者)的协助时，在 传统的程序设计过程中，通常由调用者来创建被调用者的实例。但在Spring里，创建被调用者的工作不再由调用者来完成，因此称为控制反转;创建被调用者 实例的工作通常由Spring容器来完成，然后注入调用者，因此也称为依赖注入。
- 我们的应用更加松耦合、增强扩展性以及可维护性。通过依赖注入我们可以降低从编译到运行时的依赖性。
- 说一下泛型原理，并举例说明
https://www.cnblogs.com/hq233/p/7227887.html
- 通过参数化的方式将数据处理与数据类型解耦的技术
- java泛型的实现原理是类型擦除。Java的泛型是伪泛型。在编译期间，所有的泛型信息都会被擦除掉。
Java中的泛型基本上都是在编译器这个层次来实现的。在生成的Java字节码中是不包含泛型中的类型信息的。使用泛型的时候加上的类型参数，会在编译器在编译的时候去掉。这个过程就称为类型擦除。
- 枚举的理解与注意事项
- Java中String的了解
https://www.cnblogs.com/xiaoxi/p/6036701.html
final类
char[]
String对象一旦被创建就是固定不变的了，对String对象的任何改变都不影响到原对象，相关的任何change操作都会生成新的对象
字符串常量池
- String为什么要设计成不可变的？
http://blog.csdn.net/renfufei/article/details/16808775
字符串常量池的需要
允许String对象缓存HashCode
安全性,String是很多系统类的参数
数据结构
- 常用数据结构简介
https://www.jianshu.com/p/230e6fde9c75
- 一、线性表（n个数据元素的有限序列）
1.数组实现(一组连续的存储单元,下标来访问或者修改元素，比较高效,插入和删除的花费开销较大)
2.链表(物理存储单元上非连续、非顺序的存储结构,添加或者删除时，只需要改变相关节点的Next的指向，效率很高,访问效率低)- 二、栈与队列
1.栈(插入删除只能在栈顶，LIFO(Last In First Out)表，即后进先出。)
2.队列(只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作,FIFO)- 三、树与二叉树
1.树（由n（n>=1）个有限节点组成一个具有层次关系的集合）
2.二叉树基本概念(每个节点最多有两棵子树的树结构,满二叉树，完全二叉树，非完全二叉树；根节点、左子树和右子树；先序遍历(ABC)、中序遍历(BAC)和后续遍历(BCA))
3.二叉查找树(左<根 右>根)
4.平衡二叉树(它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1)
5.红黑树- 四、图(复杂)
- 并发集合了解哪些？
- AtomicInteger, AtomicBoolean, AtomicLong, AtomicReference
sun.misc.Unsafe
boolean compareAndSet(expectedValue, updateValue);
public boolean compareAndSet(
V expectedReference,//预期引用
V newReference,//更新后的引用
int expectedStamp, //预期标志
int newStamp) //更新后的标志- ArrayBlockingQueue
一个由数组支持的有界阻塞队列。此队列按 FIFO（先进先出）原则对元素进行排序。有界缓存区,试图向已满队列中放入元素会导致操作受阻塞；试图从空队列中提取元素将导致类似阻塞。只使用了一个lock来控制互斥访问
public void put(E e) throws InterruptedException {
Objects.requireNonNull(e);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == items.length)
notFull.await();
enqueue(e);
} finally {
lock.unlock();
}
}
- LinkedBlockingQueue
一个基于已链接节点的、范围任意的blocking queue。
LinkedBlockingQueue使用了2个lock，一个takelock和一个putlock，读和写用不同的lock来控制，这样并发效率更高。- ConcurrentLinkedQueue
使用CAS来实现，是非阻塞式的“lock-free”实现- ConcurrentHashMap
jdk1.6采用了Segment分段技术，容器里有多把锁，每把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率。
由Segment数组结构和HashEntry数组结构组成
jdk1.8采用CAS+数组，链表，红黑树- CopyOnWriteArrayList
写时复制的容器.一种读写分离的思想，读和写不同的容器。写时加锁，读时读的是之前的，不需要加锁
public boolean add(T e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
// 复制出新数组
Object[] newElements = Arrays.copyOf(elements, len + 1);
// 把新元素添加到新数组里
newElements[len] = e;
// 把原数组引用指向新数组
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
- AbstractQueuedSynchronizer
为实现依赖于先进先出 (FIFO) 等待队列的阻塞锁和相关同步器（信号量、事件，等等）提供一个框架。
- 列举java的集合以及集合之间的继承关系
http://alexyyek.github.io/2015/04/06/Collection/
- Collection
public interface Collection<E> extends Iterable<E> {}- List
public interface List<E> extends Collection<E> {}
List是有序的队列，List中的每一个元素都有一个索引;允许重复
实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。- ArrayList
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
private static final int DEFAULT_CAPACITY = 10;//初始容量，随着容器中的元素不断增加，容器的大小也会随着增加
transient Object[] elementData;//数组
RandomAccess 用来表明其支持快速（通常是固定时间）随机访问，适合for循环而不适合迭代器方法
ArrayList的操作是固定时间- LinkedList
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
transient Node<E> first;//LinkedList是一个双向链表
transient Node<E> last;- Vector
和ArrayList类似，只是线程安全的，提供的是synchronized方法- Stack
public class Stack<E> extends Vector<E> {}
Stack继承自Vector，实现一个后进先出的堆栈- Set
public interface Set<E> extends Collection<E> {}
是一种不包括重复元素的Collection,
该接口定义了 boolean equals(Object o);方法
实现类：HashSet、TreeSet、LinkedHashSet、EnumSet。- HashSet
public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
查询速度最快的集合,内部是以HashCode来实现的
内部 private transient HashMap<E,Object> map;
可以放null，因为hash方法null时会为0。
add方法:
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}- TreeSet
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
private transient NavigableMap<E,Object> m;
public TreeSet() {//默认是TreeMap实现
this(new TreeMap<E,Object>());
}
二叉树实现的，生成一个总是处于排序状态的set
不允许放入null
提供的 Comparator 进行排序- LinkedHashSet
public class LinkedHashSet<E> extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable
同时使用链表维护元素的次序
//基于的是LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}- EnumSet
final Enum<?>[] universe;
所有值都必须是指定枚举类型的值
枚举类的定义顺序来决定集合元素的顺序
通过它提供的static方法来创建EnumSet对象- Map
说一个key对应一个value，所以它不能存在相同的key值
HashMap、HashTable、TreeMap、WeakHashMap等实现类- HashMap
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
查找对象时通过哈希函数计算其位置
transient Node<K,V>[] table; hash表数组
如果有冲突，则使用散列链表- HashTable
public class Hashtable<K,V> extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
Dictionary类是任何可将键映射到相应值的类（如 Hashtable）的抽象父类
“拉链法”比HashMap性能低
synchronized方法 线程安全- TreeMap
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
有序散列表，实现SortedMap接口，底层通过红黑树实现。- WeakHashMap
public class WeakHashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>
null值和null键都被支持
弱键可被终止- Iterator
Iterator遍历Collection时，是fail-fast机制的。抛出ConcurrentModificationException异常
- Arrays和Collections
http://blog.csdn.net/excellentyuxiao/article/details/52344594
- Collections:一个工具类。它包含各种有关集合操作的静态多态方法
- 空集合:返回只读空集合
Collections.emptyList();emptyMap();emptySet()- 单元素集合（只读）
Collections.singletonList();singletonMap();singleton();- 只读集合,硬改抛UnsupportedOperationException
unmodifiableXXX(XXX s)- Checked集合，具有检查插入集合元素类型的特性
checkedXXX(XXX<E> s, Class<E> type)- 同步集合,内部通过synchronized (mutex)实现
synchnorizedXXX(XXX s)- 替换:把所有内容替换为obj
fill(List<? super T> list, T obj)- 查找
- frequency(Collection<?> c, Object o)返回指定 collection 中等于指定对象的元素数,为null的时候用==判断，否则用equals(Object中equals也是用的==判断)
- indexOfSubList(List<?> source, List<?> target)/lastIndexOfSubList:返回指定源列表中第一次（最后一次）出现指定目标列表的起始位置，如果没有出现这样的列表，则返回 -1。
- max/min(Collection<? extends T> coll, Comparator<? super T> comp):返回给定 collection 的最大/小元素
- replaceAll(List<T> list, T oldVal, T newVal)：使用另一个值替换列表中出现的所有某一指定值。
- 排序
- reverse(List<?> list)：对List中的元素倒序排列
- shuffle：基于Random的随机排序
- sort:java8中List接口使用default关键字实现了sort方法
- swap(List<?> list, int i, int j)：交换List中某两个指定下标位元素在集合中的位置
- rotate(List<?> list, int distance)：循环滚动，[t, a, b, k, s] --->rotate(list,1)==>[s，t，a，b，k]
- Arrays
- fill:给数组赋值
- sort:排序
- copyOf——复制数组：其实理解为集合扩容即可
- equals
- binarySearch：核心binarySearch0(byte[] a, int fromIndex, int toIndex,byte key)，二分查找算法
- List,Set,Map的区别
https://www.cnblogs.com/grayworm/p/6235657.html
- List的特征是其元素以线性方式存储，集合中可以存放重复对象
- 集合中的对象不按特定的方式排序，并且没有重复对象
- Map 是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。 Map没有继承于Collection接口 从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。
- HashMap理解
http://www.importnew.com/7099.html
实现原理
1520949407329.jpg
基于哈希表的Map接口的非同步实现
- 数据结构
链表散列的数据结构即链表(或红黑树(jdk>1.8时))+数组transient Entry[] table; static class Node<K,V> implements Map.Entry<K,V> { final int hash;//用于定位数组索引的位置 final K key; V value; Node<K,V> next;//链表的下一个Node …… }- 基本参数
int threshold;// 所能容纳的key-value对极限，超过要resize(扩容) final float loadFactor; // 负载因子 默认0.75 int modCount; //结构变化的次数 int size; // 实际存在的键值对数量，和length不一样 threshold = length * loadFactor //table的长度length大小必须为2的n次方,为了好高位运算- 确定哈希桶数组索引位置(速度快，效率高的算法)
static final int hash(Object key) { int h; //取hashCode值 + 高位运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } //取模 tab[i = (n - 1) & hash])---i = (n-1)&hash- 存储
对key的hashCode()做hash，然后再计算index;
如果没碰撞直接放到bucket里；
如果碰撞了，以链表的形式存在buckets后；
如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
如果节点已经存在就替换old value(保证key的唯一性)
如果bucket满了(超过load factor*current capacity)，就要resizefinal V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //判断table是否为空， if ((tab = table) == null || (n = tab.length) == 0) //创建一个新的table数组，并且获取该数组的长度 n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null)//取模得tab索引 tab[i] = newNode(hash, key, value, null);//放入 else {//table不为空 Node<K,V> e; K k; //如果key完全相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;//替换Value,保证了完全相等的key不存在重复值 else if (p instanceof TreeNode)//如果是红黑树，链表长>8 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, > key, value);//直接放入 else {//是链表 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st长度>8转为红黑树 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))//完全相等，不管 break; p = e; } } //写入 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold)//插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold resize();//扩容 afterNodeInsertion(evict); return null; }- 获取
- bucket里的第一个节点，直接命中；
- 如果有冲突，则通过key.equals(k)去查找对应的entry
若为树，则在树中通过key.equals(k)查找，O(logn)；
若为链表，则在链表中通过key.equals(k)查找，O(n)。final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {//目标索引直接找到也就是该桶的第一个节点 if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))//完全相等 return first; if ((e = first.next) != null) {//找下一个节点 if (first instanceof TreeNode)//如果是红黑树 return ((TreeNode<K,V>)first).getTreeNode(hash, key);//在树中找 do {//在链表中找 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }- 扩容
JKD1.7 扩容后会倒置，JDK1.8不会，JDK1.8源码如下final Node<K,V>[] resize() { Node<K,V>[] oldTab = table;//老Table引用 int oldCap = (oldTab == null) ? 0 : oldTab.length;//原length int oldThr = threshold;//原容量 int newCap, newThr = 0;//定义新长度和容量 if (oldCap > 0) {//原来长度大于0 if (oldCap >= MAXIMUM_CAPACITY) {//如果原容量>2的30次方 threshold = Integer.MAX_VALUE; return oldTab;//不扩了 } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)//扩两倍长度 newThr = oldThr << 1; //扩两倍容量 } else if (oldThr > 0) //如果原长度==0且原容量大于0 newCap = oldThr;//新长度等于原容量 else {// 如果原来长度和容量全是0 newCap = DEFAULT_INITIAL_CAPACITY;//默认值长度16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//默认容量=0.75*16=12 } if (newThr == 0) {//新容量还是0 float ft = (float)newCap * loadFactor;//计算长度 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);//不超过2^30容量为新计算的长度 } threshold = newThr;//更新当前的容量 @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建新长度的table数组 table = newTab;//更新当前的数组为新数组 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) {//遍历老数组 Node<K,V> e; if ((e = oldTab[j]) != null) {//老的Node先拿出来 oldTab[j] = null;//将老数组此处的引用清除 if (e.next == null)//链表只有一个值，即没有碰撞 //没有重新计算HashCode,且位置不变 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode)//如果是红黑树则split ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // 普通链表的时候 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do {//遍历此桶下的链表 next = e.next; if ((e.hash & oldCap) == 0) {//原索引 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else {//新索引 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) {//放到原索引位置 loTail.next = null; newTab[j] = loHead; } if (hiTail != null) {//放到原索引+oldCap的位置 hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
- CAS
http://blog.csdn.net/ls5718/article/details/52563959
- 锁之不足:
- 频繁获取释放锁，开销大，有延时，性能低
- 得不到锁的现成会挂起，浪费
- 低优先级拥有锁，高优先级也白费，优先级错乱
- CAS理解
- compare and swap 比较替换；核心方法compareAndSwapXXX
- 三大元素V的地址，预期原值A，新值B
- V地址的值=预期原值，在V地址更新为B值
- 是一种乐观锁机制，synchnorized是悲观锁
- 基于Cpu的CAS指令，借助JNI完成一种非阻塞算法
- CAS 的指令允许算法执行读-修改-写操作，而无需害怕其他线程同时 修改变量，因为如果其他线程修改变量，那么 CAS 会检测它（并失败），算法 可以对该操作重新计算。
- CAS问题
- ABA问题--1A2B3A
- 循环开销大--pause指令
- 只能保证一个共享变量--多变量合并成一个
- CAS应用
- atomic包 AtomicReference组合原子变量
- concurrent包: volatile + CAS
- ConcurrentHashMap的实现原理
http://blog.csdn.net/fjse51/article/details/55260493
- 来源因素
- HashMap 非同步，put扩容由于竞争可能会导致死链
- HashTable虽同步，但是用的是synchronized属于悲观锁，性能较差
- jdk1.6采用锁分段技术，但是jdk1.8已经放弃，采用CAS加数组，链表，红黑树，性能更好
- jdk1.6实现核心
分段锁的机制,Segment数组和HashEntry数组组成,Segment继承ReentrantLock用来充当锁的角色,个 Segment 对象守护每个散列映射表的若干个桶.- jdk1.8实现核心
- 采用volatile变量保证可见性，通过CAS维护这些变量重要属性如下
transient volatile Node<K,V>[] table;//桶数组 private transient volatile Node<K,V>[] nextTable; private transient volatile long baseCount;//Updated via CAS private transient volatile int sizeCtl; static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; volatile Node<K,V> next; ... } static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) { return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v); }- 存储时以桶为锁，进一步提高并发行
// 针对首个节点进行加锁操作，而不是segment，进一步减少线程冲突 synchronized (f) { }- 读取时通过CAS读取
e = tabAt(tab, (n - 1) & h)) != null static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE); }
- SparseArray
http://blog.csdn.net/abcdef314159/article/details/51679494
private static final Object DELETED = new Object(); private int[] mKeys;//Key以数组存储，key为int private Object[] mValues;//Value以数组存储 public void put(int key, E value) { //二分法查找key的位置，这就决定mKeys数组是有序递增的 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) {//如果该位置有值，直接替换 mValues[i] = value; } else { i = ~i;//如果没有二分法会返回key的大临界值的位置的取反，这里再取反就是小临界值的位置，如-4取反是3 if (i < mSize && mValues[i] == DELETED) {//如果这个值被删了，则将key放到该位置 mKeys[i] = key; mValues[i] = value; return; } if (mGarbage && mSize >= mKeys.length) { gc();//重排，把删除了的去掉，然后其后面的前移 // 位置变化重新二分法查找 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } //放入 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); //大小加1 mSize++; } } private void gc() { // Log.e("SparseArray", "gc start with " + mSize); int n = mSize; int o = 0; int[] keys = mKeys; Object[] values = mValues; for (int i = 0; i < n; i++) { Object val = values[i]; if (val != DELETED) {//该位置已经被删除的话就释放 if (i != o) { keys[o] = keys[i]; values[o] = val; values[i] = null; } o++; } } mGarbage = false; mSize = o;//回收后的大小 // Log.e("SparseArray", "gc end with " + mSize); } public E get(int key, E valueIfKeyNotFound) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//二分法找位置 if (i < 0 || mValues[i] == DELETED) { return valueIfKeyNotFound; } else { return (E) mValues[i]; } } public void delete(int key) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { if (mValues[i] != DELETED) { mValues[i] = DELETED; mGarbage = true; } } }
- ArrayMap
http://blog.csdn.net/abcdef314159/article/details/51683093
一个数组存储的是Hash值另一个数组存储的是key和value，其中key和value是成对出现的，key存储在数组的偶数位上，value存储在数组的奇数位上mHashes[index] = hash; mArray[index<<1] = key; mArray[(index<<1)+1] = value;只有hash值相同并且key也相同才会返回所在的位置
- HashTable实现原理
http://blog.csdn.net/jinhuoxingkong/article/details/52022999
线程安全的，key和value是不允许为空的
- Hashtable和HashMap区别
（1）基类不同：HashTable基于Dictionary类，而HashMap是基于AbstractMap。Dictionary是什么？它是任何可将键映射到相应值的类的抽象父类，而AbstractMap是基于Map接口的骨干实现，它以最大限度地减少实现此接口所需的工作。
（2）null不同：HashMap可以允许存在一个为null的key和任意个为null的value，但是HashTable中的key和value都不允许为null。
（3）线程安全：HashMap时单线程安全的，Hashtable是多线程安全的。
（4）遍历不同：HashMap仅支持Iterator的遍历方式，Hashtable支持Iterator和Enumeration两种遍历方式。
- TreeMap具体实现
http://blog.csdn.net/qq_32166627/article/details/72773293
基于红黑树（Red-Black tree）的 NavigableMap实现
可排序（自然排序，Comparator-(实现Comparable接口的实体或自定义实现Comparator接口的类)）public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
- HashMap与HashSet的区别
hashmap与hashset区别.jpg
- HashSet与HashMap怎么判断集合元素重复？
f (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;
- 集合Set实现Hash怎么防止碰撞
如果hash码值不相同，说明是一个新元素，存；
如果hash码值相同，且equles判断相等，说明元素已经存在，替换
如果hash码值相同，且equles判断不相等，说明元素不存在，存；
- ArrayList和LinkedList的区别，以及应用场景
- 数组--双链表
- 数组结构在通过索引进行查询数据时效率比较高
- 保证数据插入和删除，不会影响其他数据的移动，保证线性开销
- 二叉树的深度优先遍历和广度优先遍历的具体实现
package gjg.com.fundemo.javatest;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
/**
* @author : gaojigong
* @date : 2018/3/15
* @description:
*/
public class TreeNodeDemo {
public static class TreeNode{
String value;
TreeNode left;
TreeNode right;
public TreeNode(String value) {
this.value = value;
}
}
public static class TreeNodeMethod{
/**
* 递归方式创建二叉树
* @param array 中序数组
* @param index
* @return
*/
public static TreeNode makeTreeNodeRootByArray(String[] array,int index){
if(array == null || array.length == 0){
return null;
}
if(index < array.length){
//获取索引出的数组值
String value = array[index];
if(null != value){
TreeNode t = new TreeNode(value);
//清除数组次位置的引用
array[index] = null;
//创建左子树
t.left = makeTreeNodeRootByArray(array,index * 2);
t.right = makeTreeNodeRootByArray(array,index * 2 + 1);
return t;
}
}
return null;
}
/**
* 深度优先遍历
* 非递归
* 借助栈 先进后出
* @param root
*/
public static List<String> depthOrderTraversal(TreeNode root){
if(root == null){
return null;
}
List<String> result = new ArrayList<>();
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);//入栈
while (!stack.isEmpty()){
//出栈
TreeNode t = stack.pop();
result.add(t.value);
if(t.right != null){
stack.push(t.right);
}
if(t.left != null){
stack.push(t.left);
}
}
return result;
}
/**
* 广度优先遍历
* 利用队列 先进先出
* @param root
* @return
*/
public static List<String> levelOrderTraversal(TreeNode root){
if (root == null){
return null;
}
List<String> result = new ArrayList<>();
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()){
TreeNode t = queue.remove();
result.add(t.value);
if(t.left != null){
queue.add(t.left);
}
if(t.right != null){
queue.add(t.right);
}
}
return result;
}
/**
* 递归获取最大深度
* @param root
* @return
*/
public static int getMaxDepth(TreeNode root){
if(root == null){
return 0;
}
int left = getMaxDepth(root.left);
int right = getMaxDepth(root.right);
return 1 + Math.max(left,right);
}
/**
* 获取最大宽度
* 基于队列
* @param root
* @return
*/
public static int getMaxWidth(TreeNode root){
if(root == null){
return 0;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
int maxWidth = 1;//最大宽度
while (true){
int len = queue.size();
if(len == 0){
//队列处理完
break;
}
while (len > 0){
//当层节点还有子节点
TreeNode t = queue.poll();
len--;//处理了一个节点
//当前的子节点加入队列
if(t.left != null){
queue.add(t.left);
}
if(t.right != null){
queue.add(t.right);
}
}
maxWidth = Math.max(maxWidth,queue.size());
}
return maxWidth;
}
}
}
- 堆的结构
堆是一种经过排序的树形数据结构，每个节点都有一个值
根结点的值最小（或最大）,且根结点的两个子树也是一个堆
- 堆和栈在内存中的区别是什么(解答提示：可以从数据结构方面以及实际实现方面两个方面去回答)？
http://blog.csdn.net/Fiorna0314/article/details/49757195
申请方式和回收方式不同(栈自动分收，堆自己申放)
栈想去饭店吃饭，只点菜自会上菜，堆想自己下厨自己做
- 什么是深拷贝和浅拷贝
http://blog.csdn.net/lcg910978041/article/details/51992614
复制对象(深)，复制引用(浅)
clone Clonable
- 手写链表逆序代码
public class NodeReverse {
public static class Node{
String value;
Node next;
}
public static Node reverse(Node head){
//如果链表中只有一个直接返回原来的
if(head == null || head.next == null || head.next.next == null){
return head;
}
Node p = head.next;//拿出引用
Node q = head.next.next;//拿出引用
Node t = null;//辅助移动
while (q != null){
t = q.next;//先存一下q.next
q.next = p;
p = q;
q = t;
}
head.next.next = null;//设置链伟
head.next = p;
return head;
}
}
- 讲一下对树，B+树的理解
- 讲一下对图的理解
- 判断单链表成环与否？
定义两个指针p, q，其中p每次向前移动一步，q每次向前移动两步，所以就成p为慢指针，q为快指针。
那么如果单链表存在环，则p和q进入环后一定会在某一点相遇，因为进入环后就会一直循环下去，否则q将首先遇到null，就说明不存在环。
- 合并多个单有序链表（假设都是递增的）
public ListNode getResult(ListNode result, ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) {
return null;
}
if (l1 == null) {
result = l2;
//result.next = getResult(result.next, l1, l2.next);
return result;
}
if (l2 == null) {
result = l1;
//result.next = getResult(result.next, l1.next, l2);
return result;
}
if (l1.val > l2.val) {
result = l2;
l2 = l2.next;
} else {
result = l1;
l1 = l1.next;
}
result.next = getResult(result.next, l1, l2);
return result;
线程、多线程和线程池
- 开启线程的三种方式？
http://blog.csdn.net/longshengguoji/article/details/41126119
- MyThread extends Thread
new MyThread().start()- MyRunable implements Runable
Thread thread = new Thread(new MyRunable()).start();- Target implements Callable<T>
- FutureTask task = new FutureTask(new Target());
- Thread thread = new Thread(task).start();
- 为什么要有线程，而不是仅仅用进程？
线程增加的进程的并发度，线程能更有效的利用多处理器和多内核
- run()和start()方法区别
http://www.jb51.net/article/98433.htm
- start与run方法的主要区别在于当程序调用start方法一个新线程将会被创建，并且在run方法中的代码将会在新线程上运行，然而在你直接调用run方法的时候，程序并不会创建新线程，run方法内部的代码将在当前线程上运行。
- 另外一个区别在于，一但一个线程被启动，你不能重复调用该thread对象的start方法，调用已经启动线程的start方法将会报IllegalStateException异常， 而你却可以重复调用run方法
- 如何控制某个方法允许并发访问线程的个数？
https://www.cnblogs.com/androidsuperman/p/6349586.html
Semaphore semaphore = new Semaphore(5);//线程run中只有5个线程可并发访问 semaphore.acquire();//申请一个信号 semaphore.release();//释放一个信号
- 线程的状态
http://blog.csdn.net/pange1991/article/details/53860651
image
- 在Java中wait和sleep方法的不同；
http://blog.csdn.net/liuguangqiang/article/details/49180319
wait 释放对象锁 sleep与对象锁无关
当前线程必须拥有此对象的monitor，才能调用对象的wait
- 谈谈wait/notify关键字的理解
都是本地final方法,调用之前持有对象锁
wait ，线程进入挂起状态，释放对象锁
notify, 通知唤醒wait队列中的线程(某个)
- 什么导致线程阻塞？
Thread.sleep t.join 等待输入
- 线程如何关闭？
- 讲一下java中的同步的方法
run方法结束 stop(相当危险) interrput()
- 数据一致性如何保证/如何保证线程安全/如何实现线程同步？
http://blog.csdn.net/wenwen091100304/article/details/48318699
- 同步方法 synchronized
- 同步代码块 synchronize(obj)
- volatile
- 重入锁 ReentrantLock
- 使用局部变量 ThreadLocal<Integer> local
- CAS非阻塞同步
- 两个进程同时要求写或者读，能不能实现？如何防止进程的同步？(读者写者问题)
- 线程间操作List
- Java中对象的生命周期
http://blog.csdn.net/sodino/article/details/38387049
创建--应用-不可见-不可达-收集-终结-重分配
- Synchronized用法
https://www.cnblogs.com/wl0000-03/p/5973039.html
内置锁，不影响没有锁，或者没有该锁的方法执行
类锁只是一个抽象出来的概念，只是为了区别静态方法的特点
同步代码块优于同步方法(大房子小房间)
- synchronize的原理
http://www.importnew.com/23511.html
- 实现基础（java对象头和monitor是实现synchronized的基础！）
- 普通同步方法，锁是当前实例对象
- 静态同步方法，锁是当前类的class对象
- 同步方法块，锁是括号里面的对象
- 同步代码块-看class文件信息
monitorenter monitorexit- 同步方法
access_flags字段中的synchronized标志位置1- java对象头
- MarkWord 标记字段 存储对象自身运行的数据，如哈希码（HashCode）、GC分代年龄、锁状态标志、线程持有的锁、偏向线程 ID、偏向时间戳等等
- Klass Poniter 类型指针 哪个类型实例
- Monitor
一个同步工具,线程私有的数据结构,一些字段标示了相关意义(Owner, EntryQ, RcThis, Nest, HashCode, Candidate)- 锁优化
- 自旋锁:频繁的阻塞和唤醒对CPU来说不值故而因数自旋，让该线程等待一段时间，不会被立即挂起,执行一段无意义的循环即可（自旋）。
- 适应自旋锁：固定次数自旋，有可能造成占着茅坑不拉屎，所以有了自适应，自适应就是自选成功下次还会自旋(次数+1)，不成功就不自旋了。
- 锁消除,有些时候不需要锁，但是一些系统类StringBuffer,Vector,HashTable自带synchronize方法，当确实不需要的时候，JVM会对这些进行锁消除
- 锁粗化: 锁住的代码块越小越好，但是连续锁几个小的就不好了，连续锁较多时，合并成一个锁，就是锁粗化
- 轻量级锁:主要目的是在多没有多线程竞争的前提下，减少传统的重量级锁使用操作系统互斥量产生的性能消耗。原理是多次通过CAS去改Mark Word字段。
- 偏向锁：为了在无多线程竞争的情况下尽量减少不必要的轻量级锁执行路径。原理是检查是否为偏向锁、锁标识为以及ThreadID。
- 重量级锁:重量级锁通过对象内部的监视器（monitor）实现，其中monitor的本质是依赖于底层操作系统的Mutex Lock实现，操作系统实现线程之间的切换需要从用户态到内核态的切换，切换成本非常高。
- static synchronized 方法的多线程访问和作用
静态同步方法，锁为Class对象
- 同一个类里面两个synchronized方法，两个线程同时访问的问题
普通synchronized时，不能同时访问，因为两个方法的锁是示例对象，是一个。
- volatile的原理
http://www.importnew.com/18126.html
lock前缀指令,即内存栅栏：重排序不跨栏，强制缓存立即更新主存，如果是写会让其它cpu中的对应缓存无效
- 谈谈volatile关键字的用法
http://www.importnew.com/18126.html
状态标记量 ，double check时
- 谈谈volatile关键字的作用
http://www.importnew.com/18126.html
可见，一定程度的有序
- synchronized 和volatile 关键字的区别
- synchronized与Lock的区别
http://blog.csdn.net/u012403290/article/details/64910926?locationNum=11&fps=1
- lock ReentrantLock
http://blog.csdn.net/yanyan19880509/article/details/52345422
http://blog.csdn.net/endlu/article/details/51249156
- 死锁的四个必要条件？
http://blog.csdn.net/jyy305/article/details/70077042
互斥条件
不可剥夺条件
请求和保持条件
循环等待条件
- 怎么避免死锁？
http://blog.csdn.net/ls5718/article/details/51896159
加锁顺讯
锁加时限
锁检查
- 对象锁和类锁是否会互相影响？
http://blog.csdn.net/codeharvest/article/details/70649375
http://blog.csdn.net/codeharvest/article/details/70649375
- 什么是线程池，如何使用?
http://www.importnew.com/19011.html
关注如何缩短或调整T1,T3时间的技术,调整线程池中工作线线程的数目以达到最优
Executors ---- ThreadPoolExecutor
newSingleThreadExecutor
newFixedThreadExecutor(n)
newCacheThreadExecutor（推荐使用）
newScheduleThreadExecutor/** * corePoolSize 核心池的大小(正式职工数)，这个参数跟后面讲述的线程池的>实现原理有非常大的关系。 在创建了线程池后，默认情况下，线程池中并没有任何线程，而是等待有任务到来才创建线程去执行任务， 除非调用了prestartAllCoreThreads()或者prestartCoreThread()方法，从这2个方法的名字就可以看出，是预创建线程的意思，即在没有任务到来之前就创建corePoolSize个线程或者一个线程。 默认情况下，在创建了线程池后，线程池中的线程数为0，当有任务来之后，就会创建一个线程去执行任务，当线程池中的线程数目达到corePoolSize后，就会把到达的任务放到缓存队列当中； * maximumPoolSize 线程池最大线程数（正式职工数+临时工数），这个参数也是一个非常重要的参数，它表示在线程池中最多能创建多少个线程； * keepAliveTime 表示线程没有任务执行时最多保持多久时间会终止。 默认情况下，只有当线程池中的线程数大于corePoolSize时，keepAliveTime才会起作用，即当线程池中的线程数大于corePoolSize时，如果一个线程空闲的时间达到keepAliveTime，则会终止，直到线程池中的线程数不超过corePoolSize。 但是如果调用了allowCoreThreadTimeOut(boolean)方法，在线程池中的线程数不大于corePoolSize时，keepAliveTime参数也会起作用，直到线程池中的线程数为0； * unit keepAliveTime的时间单位 * workQueue 一个阻塞队列，用来存储等待执行的任务，这个参数的选择也很重要，会对线程池的运行过程产生重大影响，一般来说，这里的阻塞队列有以下几种选择： ArrayBlockingQueue;LinkedBlockingQueue;SynchronousQueue; * threadFactory 线程工厂，主要用来创建线程； * handler 表示当拒绝处理任务时的策略 ThreadPoolExecutor.AbortPolicy:丢弃任务并抛出RejectedExecutionException异常。 ThreadPoolExecutor.DiscardPolicy：也是丢弃任务，但是不抛出异常。 ThreadPoolExecutor.DiscardOldestPolicy：丢弃队列最前面的任务，然后重新尝试执行任务（重复此过程） ThreadPoolExecutor.CallerRunsPolicy：由调用线程处理该任务 */ public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<Runnable> workQueue, ThreadFactory threadFactory, RejectedExecutionHandler handler) { ..................... }
- execute()方法实际上是Executor中声明的方法，在ThreadPoolExecutor进行了具体的实现，这个方法是ThreadPoolExecutor的核心方法，通过这个方法可以向线程池提交一个任务，交由线程池去执行。
- submit()方法是在ExecutorService中声明的方法，在AbstractExecutorService就已经有了具体的实现，在ThreadPoolExecutor中并没有对其进行重写，这个方法也是用来向线程池提交任务的，但是它和execute()方法不同，它能够返回任务执行的结果，去看submit()方法的实现，会发现它实际上还是调用的execute()方法，只不过它利用了Future来获取任务执行结果
- shutdown()和shutdownNow()是用来关闭线程池的。
- 线程池状态
volatile int runState;//表示当前线程池的状态，线程之间可见
static final int RUNNING = 0;//初始时
static final int SHUTDOWN = 1;//shutdown()后，不接新任务，等待所有任务执行完毕
static final int STOP = 2;//shutdownNow()后，不接新任务，当前任务尝试结束
static final int TERMINATED = 3;//工作线程已经销毁,任务队列无任务- 任务执行
public void execute(Runnable command) { if (command == null) throw new NullPointerException(); int c = ctl.get(); if (workerCountOf(c) < corePoolSize) { if (addWorker(command, true)) return; c = ctl.get(); } if (isRunning(c) && workQueue.offer(command)) { int recheck = ctl.get(); if (! isRunning(recheck) && remove(command)) reject(command); else if (workerCountOf(recheck) == 0) addWorker(null, false); } else if (!addWorker(command, false)) reject(command); }
- 线程池中的线程初始化
prestartCoreThread()：初始化一个核心线程；
prestartAllCoreThreads()：初始化所有核心线程- 任务缓存队列及排队策略
1）ArrayBlockingQueue：基于数组的先进先出队列，此队列创建时必须指定大小；
2）LinkedBlockingQueue：基于链表的先进先出队列，如果创建时没有指定此队列大小，则默认为Integer.MAX_VALUE；
3）synchronousQueue：这个队列比较特殊，它不会保存提交的任务，而是将直接新建一个线程来执行新来的任务。- 任务拒绝策略
- 线程池的关闭
shutdown()：不会立即终止线程池，而是要等所有任务缓存队列中的任务都执行完后才终止，但再也不会接受新的任务
shutdownNow()：立即终止线程池，并尝试打断正在执行的任务，并且清空任务缓存队列，返回尚未执行的任务- 线程池容量的动态调整
- Java的并发、多线程、线程模型
https://www.cnblogs.com/EasonJim/p/7011747.html?utm_source=itdadao&utm_medium=referral
?
- 谈谈对多线程的理解
- 多线程有什么要注意的问题？
- 谈谈你对并发编程的理解并举例说明
- 谈谈你对多线程同步机制的理解？
?
- 如何保证多线程读写文件的安全？
- 多线程断点续传原理与实现
https://www.cnblogs.com/amosli/p/3821474.html
RandomAccessFile
- 谈谈NIO的理解
http://blog.csdn.net/suifeng3051/article/details/48160753
NIO主要用到的是块
所有的数据都是用Buffer处理的，它是NIO读写数据的中转池。Buffer实质上是一个数组
Channel是一个对象，可以通过它读取和写入数据
- 读
- 第一步：获取通道
FileInputStream fin = new FileInputStream( "readandshow.txt" );
FileChannel fc = fin.getChannel();- 第二步：创建缓冲区
ByteBuffer buffer = ByteBuffer.allocate( 1024 );- 第三步：将数据从通道读到缓冲区
fc.read( buffer );- 写
- 第一步：获取一个通道
FileOutputStream fout = new FileOutputStream( "writesomebytes.txt" );
FileChannel fc = fout.getChannel();- 第二步：创建缓冲区，将数据放入缓冲区
ByteBuffer buffer = ByteBuffer.allocate( 1024 );
for (int i=0; i<message.length; ++i) {
buffer.put( message[i] );
}
buffer.flip();- 第三步：把缓冲区数据写入通道中
fc.write( buffer );
并发编程有关知识点
- java线程安全总结
- 深入理解java内存模型
- 一张图让你看懂JAVA线程间的状态转换
- 锁机制：synchronized、Lock、Condition
- Java 中的锁
http://wiki.jikexueyuan.com/project/java-concurrent/locks-in-java.html
- Java并发编程：Thread类的使用
- Java多线程编程总结
- Java并发编程实战-----synchronized
