《Java程序员面试笔试宝典》学习笔记（持续更新……）
本文是我自己在秋招复习时的读书笔记，整理的知识点，也是为了防止忘记，尊重劳动成果，转载注明出处哦！如果你也喜欢，那就点个小心心，文末赞赏一杯豆奶吧，嘻嘻。 让我们共同成长吧……
一、Java基础知识
基本概念
1、Java语言特点
面向对象、平台无关、很多内置库、对web应用开发的支持、较好的安全性和健壮性、出去C++中的指针多继承等特性
2、Java与C++的异同
同：都是面向对象语言，都有继承、封装和多态的面向对象思想
异：Java为解释型语言，C++是编译型，Java执行速度比C++慢；
Java可以跨平台，但是C++不行;
Java为纯面向对象语言，Java中没有指针概念；
Java不支持多继承；
Java不需要开发人员进行内存的分配和释放；
Java不支持运算符重载；
3、为什么需要 public static void main（String[] args）这个方法
该方法是程序的入口，JVM运行程序时会查找该方法。其中，字符串数组args为开发人员在命令行下与程序交互提供了一种手段。
public与static没有先后关系；可以用final修饰该方法；也可以用synchronized修饰该方法；只要保证main的返回值为void并且有static和public修饰，不能用abstract修饰。
虽然每个类都可以定义main()方法，但是只有与文件名相同的用public修饰的类中的main()方法才能作文整个程序的入口。
4、如何在main()方法执行前输出内容？
用静态代码块
5、Java程序初始化顺序
（1）静态对象（变量）>非静态对象（变量）。其中，静态对象（变量）初始化1次
非静态对象（变量）可初始化多次
（2）父类 > 子类初始化
（3）按照成员变量定义顺序初始化
执行顺序：父类静态变量、父类静态代码块、子类静态变量、子类静态代码块、父类非静态变量、父类非静态代码块、父类构造函数、子类非静态变量、子类非静态代码块、子类构造函数。
6、Java中的作用域
成员变量的4种作用域：
当前类 同一包 子类(其他包) 其他包
public √ √ √ √
protected √ √ √
default √ √
private √
上述4种只能修饰成员变量，不能修饰局部变量！！！private、protected不能修饰类。
7、一个Java文件是否可以定义多个类
可以，但是最多只能1个类被public修饰，并且该类名与文件名必须相同。如没有public类，则文件名随意。
8、what is 构造函数？
构造函数：对对象实例化时初始化对象的成员变量
特点：
构造函数与类同名，不能有返回值，不能为void
每个类可有多个构造函数（重载），没有会提供默认构造函数
构造函数可有0个以上参数
构造函数伴随着new操作一起调用，完成初始化工作
子类通过super来显示调用父类的构造，当父类没有无参构造，子类构造函数必须显式调用父类构造函数；如果父类提供了无参构造，则子类可以不用显式调用父类构造。
9、为什么Java有些接口没有任何方法？
接口：是抽象方法的集合，是一种特殊的抽象类。接口成员的修饰符为public，常量的修饰符public static final
标识接口：你没有任何方法声明，实现该接口不用实现任何方法。如Cloneable和Serializable
10、Java中clone方法的作用？
Object类中有clone()方法，使用步骤：
实现克隆的类先实现Cloneable 接口
在类中重写clone()方法
在clone()方法中调用super.clone()。
把浅赋值的引用指向原型对象新的克隆体
11、what is 反射？
反射提供的功能：得到对象所属的类获得一个类的所有成员变量和方法；在运行时创建对象；在运行时调用对象的方法
获取Class类的方法：
Class.forName(''类的路径名');
类名.Class;
实例.getClass();
Java对象创建有4种方式：new；反射；clone（）;反序列化方法
12、 package作用？
提供层次命名空间，解决命名冲突；对类按功能划分，是项目组织更加清晰
13、如何实现类似于C语言中的函数指针的功能？
利用接口和类来实现。具体而言，先定义一个接口，然后在接口中声明要调用的方法，接着实现这个接口，最后把这个实现类的一个对象作为参数传给调用程序，调用程序通过这个参数来调用指定的函数。
面向对象技术
1、面向对象与面向过程的区别？
出发点不同。面向对象将问题域的直接要领直接映射到对象以及对象之间的接口上；面向过程强调过程的抽象化与模块化
层次逻辑不同。
数据处理方式与控制程序不同
2、面向对象有哪些特征？
抽象、继承、封装、多态
3、面向对象开发方式特点？
较高的开发效率；保证软件的鲁棒性（健壮性）；保证软件的高可维护性
4、what is 继承？
继承使得子类可以使用父类的一些成员变量和方法，提高代码复用性，提高开发效率。
特征：单继承；子类只能继承父类非私有的（public protected）成员变量和方法；当子类方法和父类相同，子类方法覆盖父类方法；子类成员变量与父类相同，子类会覆盖父类的成员变量
5、组合和继承的区别？
是代码复用的两种方式。
组合：指在新类中创建原来类的对象，重复已有类的功能，…has …
继承：通过继承来复用父类的功能,… is a …
6、多态实现机制
Java中多态表现形式：
方法的重载（overload）：同类中多个同名的方法，但这些方法有不同的参数，在编译时就知道调用哪个方法，这是编译时多态，可看成一个类中的方法多态性。
方法的覆盖（override）：子类覆盖父类的方法。java中父类引用可以指向本身和子类的对象，接口引用也可指向其实现类的对象。这样调用方法时，在运行时才动态绑定到具体的方法，这是运行时多态。
成员变量是无法实现多态的，成员变量的取值取决于所定义变量的类型，这是在编译期间确定的。
7、重载和覆盖的区别
重载：在同一个类中，通过方法参数区别（不同参数个数，不同参数类型。参数顺序），不能通过访问权限，返回值类型，抛出的异常区分。
覆盖：子类和父类之间，方法的函数名和参数相同，返回值相同，抛出异常一致；对于父类的private方法是无法实现覆盖的
8、抽象类和接口的区别
有抽象方法的类一定是抽象类，抽象类可以没有抽象方法，用abstract修饰；接口中的所有方法都是抽象的和default修饰的默认方法，用interface修饰。二者都是支持抽象类定义的两种机制。
同： 都不能实例化；接口和抽象类的子类只有全部实现接口或者抽象类中的方法才能实例化；
异：接口中只有方法的定义，而抽象类中有方法的定义和实现；接口被实现，抽象类被继承，接口可以多实现，抽象类只能单继承；接口是 has a关系，抽象类是is a关系；接口中的成员变量修饰符是public static final ，成员方法是public abstract 的
9、内部类有哪些？
内部类：静态内部类、成员内部类、局部内部类、匿名内部类
静态内部类：static修饰，不能与外部内同名，不能访问外部类的普通成员
成员内部类：可以访问静态和非静态的成员，但不可定义静态的属性和方法，没有静态成员
局部内部类：在代码块、方法中的类，不能被public、protected 、private、static 修饰，只能访问方法中定义为final的局部变量。
匿名内部类：不能有构造，不能有静态成员、方法和类；不能是public、protected、private、static；只能创建一个匿名内部类实例；是局部内部类的一种
10、获取父类类名
this.getClass().getName();和super.getClass().getName();返回的都是运行时类的名字。getClass返回的是运行时的类。
获取父类的名称：使用java的反射机制，getClass().getSuperclass().getName()
11、this和super的区别
this：指向当前实例对象，主要用来区分成员变量和方法的形参。
super：可以用来访问父类的方法或者成员变量。
this()和super()在构造中必须位于第一行。
关键字
1、变量的命名规则
标识符：只能有字母、数字、下划线、$组成，首字母不能为数字。不能为关键字，不能有空白字符，区分大小写
2、break、continue、return的区别
break:直接强行跳出循环，不在执行剩余代码，程序从循环之后的代码开始执行。
continue：停止当次循环，执行下一次循环。
return：结束方法
3、final、finally、finalize有什么区别
final：用来声明属性、方法、类。分别为属性不可修改、方法不可覆盖、类不可被继承
finally：异常处理的一部分，在try/cathch语句中，并且附带一个语句块，表示这段语句最终一定会被执行
finalize：是Object类的一个方法，
JDK中哪些类不能被继承：final修饰的类不能被继承，如：String、StringBuffer等
4、assert作用
断言（assert）:软件调试的一种方法，主要是对一个boolean表达式进行检查，主要用来保证程序的正确性。
断言表达式：
assert expression1
assert expression1 ：expression2
其中，expression1为boolean表达式，expression2表示基本类型或者对象
5、static关键的作用
为特定的数据类型或者对象分配单一的存储空间；实现某个属性或者方法与类在一起而不是与对象在一起
static主要的4中使用情况：成员变量、成员方法、代码块、内部类
6、使用switch时需要注意什么？
switch（expr）,expr为基本类型，枚举、字符串；在case语句结尾要有break。
7、volatile作用
volatile是一个类型修饰符，用来修饰被不同线程访问和修改的变量。被改关键修饰的变量，当系统用到改变量时直接从内存中提取，而不是在缓存中提取变量值。使得任何线程在任何时候考到的值都是相同的。但是volatile不是原子操作，只能保证可见性。
8、instanceof作用
判断一个对象是否是一个类（或者接口、抽象类、父类）的实例，返回结果是boolean.
9、strictfp作用
strictfp是strict float point的缩写，指的是精确浮点数，用来确保浮点数运算的精确性。JVM执行浮点数运算时，没有指定strictfp,结算结果可能不精确。用strictfp修饰的类、接口、方法，在其声明范围内计算结果是精确的。
基本类型与运算
1、Java中的基本数据类型
8中基本数据类型：byte（1字节=8位）、short（2字节）、int（4字节、默认）、long（8字节）、float（4字节）、double（8字节、默认）、char（2字节）、boolean（1字节）
基本数据类型被声明之后立刻在栈上分配空间。
java还提供了对基本数据类型的封装类。
java还提供了void基本类型，其封装类是java.lang.void
2、不可变类
不可变类：指的是当创建这个类的实例之后，就不允许修改它的值了。
在Java类库中。所有的基本类型包装类都是不可变类，String也是不可变类。
创建不可变类的
创建不可变类的5个基本原则：
类中所有成员变量被private修饰
类中没有修改成员变量的方法，只提供构造函数一次生成，永不改变
确保类中的所有方法不会被子类覆盖，用final修饰类或者修饰方法来达到目的
如果类成员不是不可变变量，那么在初始化或者get时获取该成员时，需要通过clone（）确保类的不可变性
如有必要，可以覆盖Object类的equal和hashCode方法
3、值传递和引用传递的区别
Java中参数传递的方式：
值传递
在方法的调用中，实参将值传递给形参，形参用这个实参的值初始化一个临时的存储单元，对形参值的操作不影响实参的值。
引用传递
在方法的调用中，传递的是对象（就是对象的地址），这时形参和实参对象都指向同一块存储单元。
java中基本数据类型都是按照值传递；其他按照引用传递
4、不同数据类型转换规则
自动数据类型转换：byte -> short -> char -> int -> long -> float -> double
注：char转换为高级类型（int long）会转换为其对应的ASCII码
byte short char 在进行运算时会自动转换为int，但使用“+=”运算不会自动转换
基本类型与boolean不会自动转换
强制数据类型转换
强制转换会损失精度
5、强制类型转换注意事项
对于“+=”Java语言对其进行特殊处理，因此，short s1=1; s1+=1能编译通过
6、运算符优先级
运算符优先级助记口诀：单目乘除位关系，逻辑三目后赋值。
单目：单目运算符+ –(负数) ++ -- 等
乘除：算数单目运算符* / % + -
位：位移单目运算符<< >>
关系：关系单目运算符> < >= <= == !=
逻辑：逻辑单目运算符&& || & | ^
三目：三目单目运算符A > B ? X : Y
后：无意义，仅仅为了凑字数
赋值：赋值=
7、Math类中round、ceil、floor方法的功能
round：四舍五入
ceil：向上取整
floor：向下取整
8、++i和i++区别
9、如何实现无符号数的右移操作
>> :有符号右移，整数最高位补0，负数最高位补1
>>>:无符号右移，无论正负，最高位补0
对于byte short char会自动转换为int类型，然后进行以为操作
<< ：有符号左移
10、char是否可以存储一个中文汉字？
可以。
字符串与数组
1、字符串创建于存储的机制是什么？
String实现采用了Flyweight(享元)设计模式。
字符串声明和初始化主要有以下两种情况：
对于String s1 = new String("abc");和String s2 = new String("abc"); 存在2个内容相同的引用对象，但是内存地址不同
String s1 = "abc";和String s2 = "abc";在JVM中存在字符串常量池，当创建一个字符串常量时，会先使用String类的equals(Object o)方法检查字符串常量池是否有相同的字符串被定义。
2、“==”、equals和hashCode()有什么区别
1、==用来比较两个变量的值是否相等(比较对应内存所存储的数值是否相同)
(1)、比较两个基本类型的数值是否相等
(2)、比较两个引用变量是否相等。即判断两个对象是否指向同一块存储空间
2、equals是Object类中提供的方法
(1)、比较两个基本类型的数据是否相等
(2)、比较两个实例对象的内容是否相等。(equals方法被覆盖之后的功能，没有覆盖和“==”一样)
如String类中的equals方法
(1)、String类中的equals首先比较地址，如果是同一个对象的引用，可知对象相等，返回true。
(2)、若不是同一个对象，equals方法挨个比较两个字符串对象内的字符，只有完全相等才返回true，否则返回false。
3、hashCode
(1)、判断两个对象是否相等。即判断两个对象是否指向同一块存储空间
(2)、默认情况下，Object类中的hashCode()方法返回对象在内存中地址转换成的一个int值。也就是说，若对象不重写该方法，则返回相应对象的内存地址。
(3)、若没有重写hashCode()方法，任何对象的hashCode()方法是不相等的。
4、equals()方法与hashCode()方法
(1)、x.equals(y)为true，则这两个对象中任一个的hashCode()方法产生的结果相同
(2)、x.equals(y)为false，则x和y的hashCode()返回值有两种情况：相等、不相等。
3、String、StringBuffer、StringBuilder和StringTokenizer区别
是否可变类实例化的方法是否线程安全速度
String不可变类两种：赋值、构造函数
StringBuffer可变类一种：构造函数线程安全速度慢
StringBuilder可变类一种：构造函数线程不安全速度快
1、String
(1)、String是不可变类，一旦创建一个对象，该对象的值不能修改。
(2)、对于已经存在的String对象的修改都是重新创建一个新的对象，然后把新的值保
存进去。
(3)、String是final类，即不能被继承。
2、StringBuffer
(1)、是一个可变对象，当对他进行修改的时候不会像String那样重新建立对象。只能
通过构造函数来建立。
(2)、只能通过构造函数来建立，不能通过赋值符号初始化对象
3、StringTokenizer
StringTokenizer是用来分割字符串的工具类（java.util.StringTokenizer）
4、Java中的数组是不是对象？
是对象。
5、数组的初始化方式？
一维数组声明：
type aaryName[ ]或type[ ] arrayName
一维数组创建：
arrayName = new type[arraySize];
二维数组：
type aaryName[ ][ ]
type[ ][ ] aaryName;
type[ ]aaryName[ ] ;
6、length属性和length（）方法的区别？
数组中有length属性获取数组的长度。
字符串是length（）方法获取字符串长度
对于集合是size（）方法查看元素个数
异常处理
1、finally块中的代码什么时候被执行
finally块的作用是保证该块不论什么情况下都会执行。
由于return代表当前函数的结束，，因此任何代码都只能在return前执行，因此finally代码块也是在return前执行。
此外，如果try-finally或者catch-finally中都有return，那么finally中的return会覆盖其他的return语句。
当程序进入try语句之前出现异常，或者在try块中强制退出都不会执行finally块中的代码。
2、异常处理的原理是？
异常处理的目的是：提高程序的安全性和鲁棒性（健壮性）。
基类java.lang.THrowable作为所有异常的父类，异常分为Error和Exception两大类。
3、运行时异常和普通异常有什么区别？
检查异常：IO异常和SQL异常，发生在编译阶段，强制处理，放在try中或者抛出
运行时异常：编译期不要求强制处理，若没处理，出现异常会有JVm处理。常见异常有：NullPointerException（空指针异常）、ClassCastException（类型转换异常）、ArrayIndexOutOfBoundsException（数组越界异常）、ArrayStoreException（数组存储异常）、BufferOverflowException(缓冲区溢出异常)、ArithmeticException（算术异常）
输入输出流
1、Java IO流的实现机制
Java IO类采用了Decorator(装饰者）设计模式
2、管理文件和目录的类
File常用方法：
boolean canRead() //检查能否读取指定文件
boolean canWrite() //检查能否写入指定文件
boolean equals(Object obj) //将指定对象与调用函数的对象进行比较
boolean exists() //测试文件是否存在
String getAbsolutePath() //返回此对象表示的文件的绝对路径名
String getName() //返回此对象表示的文件的名称
String getParent() //返回此File对象的路径名的上一级，如果路径名没有上一级，
则返回null
boolean isAbsolute() //测试此File对象表示的文件是否是绝对路径名
boolean isDirectory() //测试此File对象表示的文件是否是目录
boolean isFile() //测试此File对象表示的文件是否是普通文件
boolean delete() //删除此对象指定的文件
boolean createNewFile() //创建空文件
boolean mkdir() //创建由该File对象表示的目录
boolean mkdirs() //创建包括父目录的目录
3、Java Socket
Socket成为套接字，分为两种类型：面向连接的Socket通信协议（TCP）、面向无连接的Socket通信（UDP）
Socket的生命周期：打开Socket、使用Socket收发数据、关闭Socket
4、Java NIO
NIO就是非阻塞IO.采用了Reactor(反应器)设计模式
NIO通过Selector、Channel、Buffer来实现非阻塞的IO操作，实现原理如下：
5、Java 序列化
Java提供了2中对象序列化的方式：序列化、外部序列化
序列化
实现Serializable接口，再使用输出流（如FileOutputStream）构造ObjectOutputStream对象，调用该对象的writeObject（）将对象写出，恢复时使用对应的输入流。
特点：
若一个类能被序列化，那么它的子类也能被序列化。
static修饰的类成员和transient修饰的临时数据不会被序列化。
Java中实现序列化的接口：ObjectOutput、ObjectInput、ObjectOutputStream等。
当需要网络发送对象或者存储到数据库中使用序列化；序列化可以实现对象深复制，即可以复制引用的对象。
外部序列化
Java平台与内存管理
1、Java平台独立性原理
字节码和JVM
2、JVM加载class文件的原理机制
类加载方式有：显式加载、隐式加载
隐式加载：指程序使用 new创建对象时，会隐式的调用类加载器把对应的类加载到JVM中。
显式加载：指通过class.forName()把所需要的类加载到JVM中。
类加载器：BootStrapLoader ExtClassLoader（SystemClassLoader） APPClassLoader
类加载步骤：
加载：根据路径查找对应的class文件，然后导入
连接
检查：检查待加载的class文件的正确性
准备：给类中的静态变量分配存储空间
解析：将符号引用转换成直接引用
初始化：对静态变量和静态代码块执行初始化工作。
3、what is GC
判断对象是否有用的方法：
引用计数器法
可达性分析法
垃圾回收算法
标记-整理算法
标记-清除算法
复制算法
分代收集算法
4、Java是否存在内存泄漏问题
内存泄漏：指一个不再被程序使用的对象或者变量还在内存中占有存储空间。
内存泄漏主要有2种情况：（1）堆中申请的空间没有释放；（1）对象不再使用但在内存中保留着。
java垃圾回收可以解决（1）。java中的内存泄漏指第二种情况。
引起内存泄漏的原因：静态集合类、各种连接、监听器、变量不合理的作用域、单例模式可能造成内存泄漏
5、Java中的队和栈的区别
栈：基本数据类型变量、引用变量
堆：对象 string
容器
1、Java Collections框架
Collection是一个集合接口，提供了对集合对象进行基本操作（排序、查找、反转、替换、复制等）的通用接口，实现该接口的类有：List、Set、Queue、Stack。
Collections是针对集合类的一个包装类，提供了一系列静态方法以实现对各种集合的搜索、排序、线程安全化等操作，其中大多数方法都是用来处理线性表。Collections类不能实例化，服务于Collection框架。
Set：元素无序、不重复，HashSet、TreeSet
List: 有序、可重复 LinkedList、ArrayList Vector
Map: HashMap、TreeMap、LinkedHashMap
2、迭代器
迭代器（Iterator）
使用容器的iterator()方法返回一个Iterator对象，然后通过Iterator的next()方法返回第一个元素；使用Iterator的hasNext判断是否有元素；可以使用remove（）删除迭代器返回的元素
3、ArrayList、Vector、LinkedList
三者均为可伸缩数组，即可以动态改变长度的数组。三者都实现了List接口，主要区别在于实现方式的不同，所以对不同的操作具有不同的效率。ArrayList和Vector都是基于Object[ ] array来实现，当需要扩充时Vector为原来的2倍，ArrayList为原来的1.5倍。
1、ArrayList
是一个可改变大小的数组(本质上是一个数组)，当更多的元素加入到ArrayList中时，其大小将会动态的增长，内部的元素可以直接通过get与set方法进行访问。
2、LinkedList-非线程安全
是一个双向链表，在添加、删除时具有较好的性能，但是不能进行随机存取。
3、Vector
和ArrayList类似，但是属于线程安全的。
(1)、Vector是一个用synchronize修饰的线程安全的动态数组。
(2)、扩容方法
计算新容量的大小newsize=oldsize+(increment>0)?increment:oldsize。
若增长因子小于0，每次扩容大小为增长前的一倍；若增长因子大于0，每次扩容大小为增长因子的大小。
4、ArrayList和Vector
(1)、相同点
A、都是基于存储元素的Object[] array来实现
B、使用连续的空间存储，支持用下标来访问元素
C、插入元素时，需要移动容器中的元素，动态地扩充存储空间
(2)、区别
ArrayList数组非同步非线程安全
Vector数组同步线程安全
LinkedList双向链表非同步非线程安全
4、HashMap、HashTable、TreeMap和WeakHashMap区别
1、HashMap
(1)、实现原理
HashMap采用链地址法，即底层是一个数组实现，数组的每一项(即一个Entry)又是一个链表。
(2)、HashMap的存储机制
根据key计算出该key对应的Entry在数组中的位置index=hashcode%length；判断该Entry是否在该位置对应的链表中，不在：插入链表的头部，在：更新该链表中对应Entry的value。
(3)、HashMap的扩容
每当初始化一个HashMap，默认的数组大小为16，默认的增长因子为0.75；当元素个数超过数组大小的增长因子时，就会对数组进行扩容；HashMap采用的扩容方法，每次把数组大小扩大一倍，然后重新计算HashMap中每个元素在数组中的位置。
(4)、HashMap迭代器Iterator
Iterator迭代器采用fail-fast机制，由于HashMap不是线程安全的，因此如果在使用迭代器的过程中，有其他线程修改了map，则抛出ConcurrentModificationException，这就是fail-fast策略。
(5)、实现HashMap的同步
Map m=Collections.synchronizedMap(new HashMap())
2、ConcurrentHashMap
ConcurrentHashMap和HashTable的主要区别就是围绕着锁的粒度以及如何锁。HashTable的实现方式-锁整个hash表，ConcurrentHashMap的实现方式-锁桶(或段)。ConcurrentHashMap将hash表默认分为16个桶，get,put,remove等常用操作只锁当前需要用到的桶，其他线程依然可以使用其他桶，因此提高了并发性。
3、HashTable
HashTable实现了Map接口,HashTable通过synchronize实现线程安全。
(1)、实现原理
原理与HashMap相同，采用数组+链表的结构实现
(2)、HashTable的扩容
HashTable的默认大小为11；数组位置的计算方法不同，index=(hashcode&MAX_VALUE)；扩容的方法为newlength=oldlength*2+1；HashTable不允许key值为null，也不允许value为null。
线程安全性是否空值同步迭代器速度
HashMap非线程安全允许空键值非同步Iterator(fail-fast迭代器)快
HashTable线程安全不允许空键值同步Enumerator(不是fail-fast)慢
多线程
1、什么是线程？与进程的区别？为什么使用多线程？
线程：指程序正在执行过程中，能够执行程序代码的一个执行单元。
进程：指正在执行的程序。
2、同步和异步的区别
1、 同步
指一个进程在执行某个请求的时候，若该请求需要一段时间才能返回信息，则该进程将会一直等待下去，直到收到返回信息才继续执行下去。
2、 异步
指进程不需要一直等下去，而是继续执行下面的操作，不管其他进程的状态，当有消息返回时，系统会通知进程进行处理，这样可以提高执行的效率。
3、 实现同步的机制
(1)、临界区 通过对多线程的串行化来访问公共资源或一段代码
(2)、互斥 只有拥有互斥对象的线程才有访问公共资源的权限
(3)、信号量 允许多个线程在同一时刻访问同一资源，但限制最大线程数目
(4)、事件 通过通知操作的方式来保持线程的同步
3、如何实现多线程
方法有3：
继承Thread类，重写run()方法
实现Runnable接口，并实现run方法
实现Callable接口，重写call()方法
4、run()和start()方法的区别
start方法是线程启动方法，此时线程处于就绪状态。run 方法是需要线程执行任务的地方，当线程启动后，JVM调用线程就会执行run方法。直接调用run方法和执行普通方法没什么区别
5、多线程同步实现的方法
Java提供实现同步的3种方法：
synchronized关键字
wait()和notify() notifyAll()
Lock
6、sleep()方法与wait()方法
1、 原理不同
(1)、sleep()方法是Thread类的静态方法
(2)、wait()方法是Object类的方法，用于线程间的通信
2、 对锁的处理机制不同
(1)、调用sleep()方法不会释放锁，容易导致死锁问题
(2)、调用wait()方法，线程会释放其所占用的锁，需要借助notify()方法苏醒
3、 使用区域不同
(1)、sleep()方法可以放在任何地方使用
(2)、wait()方法必须放在同步方法或同步块中使用
4、 sleep()方法必须捕获异常
wait()、notify()、notifyAll()不需要捕获异常
引申：
sleep给其他线程运行机会不考虑优先级，而yield只会给相同或者更高优先级的线程运行机会
sleep使得线程进入阻塞状态，而yield使得线程重新回到就绪状态
sleep抛出InterruptedException，而yiel没有
sleep比yield具有更好的可移植性
7、线程终止的方法
使用stop()方法与suspend()方法终止线程的执行
1、Thread.stop()
终止线程时，释放已经锁定的所有监视资源
2、suspend()
终止线程时，该方法不会释放锁，容易产生死锁。
3、让线程自行结束进入Dead状态（建议）
通过设置一个flag标识来控制循环是否执行，通过这种方法来让线程离开run()方法，从而终止线程。
8、Synchronized和lock的区别
类别SynchronizedLock
存在层次Java的关键字，在JVM层面上是一个类
锁的释放1、 以获取锁的线程执行完同步代码，释放锁。
2、 线程执行发生异常，JVM会让线程释放锁。
在finally中必须释放锁，不然容易造成线程死锁。
锁的获取若A线程获得锁，B线程等待；若A线程阻塞，B线程会一直等待。分情况而定，Lock有多个获取锁的方式。
锁状态无法判断可以判断
锁类型可重入锁、不可中断锁、非公平锁、公平锁可重入、可判断、可公平(两者皆可)
性能少量同步大量同步
1、synchronized关键字
synchronized使用Object对象本身的notify、wait、notifyAll调度机制
2、Lock
提供了Lock接口以及它的一个实现类ReentrantLock(重入锁)，Lock使用Condition进行线程之间的调度。
(1)、lock() 以阻塞的方式获取锁
(2)、tryLock() 以非阻塞的方式获取锁
(3)、tryLock(long timeout,TimeUnit unit)
(4)、lockInterruptibly()
3、两者的主要区别
(1)、用法不一样
Synchronized用于同步方法、同步代码块中，托管给JVM执行。
Lock显示地指定起始位置和终止位置，通过代码实现。
(2)、性能不一样
资源竞争不激烈的情况下，synchronized的性能好。
资源竞争激烈的情况下，ReetrantLock的性能好(Lock接口的实现类)
(3)、锁机制不一样
Synchronized在块结构中获得锁和释放锁，自动解锁。
Lock在finnally块中释放，由开发人员手动去释放。
9、守护线程
10、join()方法作用
join（）方法是让调用该方法的线程在执行完run()方法之后，再执行join方法后面的代码。
Java数据库操作
1、如何通过JDBC访问数据库
2、JDBC处理事务采用什么方法
commit()、rollback()
JDBC事务隔离级别：
不支持事务
读未提交
读已提交
可重复读
可序列化
3、Class.forName()的作用
将类加载到JVM中。
4、getString（）与getObject()之间的区别
二、JavaWeb
Servlet与JSP
1、页面请求的工作流程
2、HTTP中get和post方法有什么区别
HTTP请求的方法：get、post、head、trace、option等
get上传数据是在URL后面加上？然后是 属性名=属性值&属性名=属性值……上传的数据量小，1024字节左右；而post传递数据通过HTTP请求的附件进行的，上传的数据量更大，一般不受限制
get方式上传数据不安全；而post方法向服务器提交的内容不会在URL中明文显示，更加安全
3、什么是Servlet
动态页面生成技术：公共网关接口（CGI,Common Gateway Interface）和Servlet
Servlet是java语言编写的服务器端程序，运行在Web容器中的Servlet容器中，主要的功能是提供请求/响应的web服务模式，可以动态生成web内容。
优点：较好的移植性，执行效率高，功能强大，使用方便，扩展性强
Servlet处理客户端请求的流程：
1、 用户通过单击一个链接来向Servlet发起请求。
2、 Web服务器接收到该请求后，把该请求交给相应的容器处理。当容器发现这是对Servlet发起的请求后，容器此时会创建两个对象：HttpServletResponse、HttpServletRequest。
3、 容器根据请求消息中的URL消息找到对应的Servlet，针对该请求创建一个单独的线程，同时把HttpServletResponse和HttpServletRequest两个对象以参数的形式传递到新创建的线程中。
4、 容器调用Servlet的service（）方法来完成对用户的请求响应，service（）方法会调用doPost()或者doGet()方法来完成具体的响应任务，同时把生成的动态内容返回给容器。
5、 容器把响应消息组装成HTTP格式返回给客户端。并删除HttpServletResponse、HttpServletRequest。
4、Servlet生命周期
Servlet生命周期只有两种状态：未创建状态和初始化状态。这两种状态转换由init()、service()、destroy()来控制。
Servlet的生命周期：加载、创建、初始化、处理客户请求、卸载。
5、JSP
JSP(Java Server Pages) = Java代码片段+HTML
让Servlet负责业务逻辑处理，JSP负责页面展示
6、JSP与Servlet的异同
同：JSP是一种特殊的Servlet，jsp最终装换为Servlet来运行，都是Servlet。
异：
Servlet是在Java中嵌入HTMl代码，JSP是在HTML嵌入java代码
Servlet没有内置对象，JSP中的内置对象必须通过HttpServletRequest对象、HttpServletResponse对象、HttpServlet对象得到
7、如何使用JSP和Servlet实现MVC模型
Model： JavaBean
View:JSP
Controller：Servlet
8、Servlet中forward和redirect之间的区别
Servlet之间跳转的方式
forward：服务器内部的重定向，客户端不知道，客户端浏览器的地址不会变化。
redirect：客户端的重定向，完全跳转，浏览器地址栏发生变化，比forward多了一次网络请求，效率相对较低。
9、JSP内置对象
9个内置对象：request、response、pageContext、session、application、out、config、page、exception
10、request对象主要方法
setAttribute(String name,Object)：设置名字为name的request 的参数值
getAttribute(String name)：返回由name指定的属性值
getAttributeNames()：返回request 对象所有属性名字集合，结果是一个枚举的实例
getCookies()：返回客户端的所有 Cookie 对象，结果是一个Cookie 数组
getCharacterEncoding() ：返回请求中的字符编码方式
getContentLength() ：返回请求的 Body的长度
getHeader(String name) ：获得HTTP协议定义的文件头信息
getHeaders(String name) ：返回指定名字的request Header 的所有值，结果是一个枚举的实例
getHeaderNames() ：返回所以request Header 的名字，结果是一个枚举的实例
getInputStream() ：返回请求的输入流，用于获得请求中的数据
getMethod() ：获得客户端向服务器端传送数据的方法
getParameter(String name) ：获得客户端传送给服务器端的有 name指定的参数值
getParameterNames() ：获得客户端传送给服务器端的所有参数的名字，结果是一个枚举的实例
getParameterValues(String name)：获得有name指定的参数的所有值
getProtocol()：获取客户端向服务器端传送数据所依据的协议名称
getQueryString() ：获得查询字符串
getRequestURI() ：获取发出请求字符串的客户端地址
getRemoteAddr()：获取客户端的 IP 地址
getRemoteHost() ：获取客户端的名字
getSession([Boolean create]) ：返回和请求相关 Session
getServerName() ：获取服务器的名字
getServletPath()：获取客户端所请求的脚本文件的路径
getServerPort()：获取服务器的端口号
removeAttribute(String name)：删除请求中的一个属性
11、JSP的动作
6个基本动作：
jsp：include、jsp：useBean、jsp：setProperty、jsp：getProperty、jsp:forward、jsp：plugin
12、JSP中include指令和include动作之间的区别
include指令是编译阶段指令。
13、会话跟踪技术
page、request、session、application
14、cookie和session的区别
cookie是在客户端浏览器中保存数据，session是在服务器端保存数据
cookie安全性不如session好
cookie性能更好些
单个cookie保存数据不能超过4KB，每个浏览器最多保存20个cookie。session不存在此问题
框架
1、HTTP请求方法
1、 GET 通过请求URI得到资源
2、 POST 添加新的内容
3、 PUT 修改某个内容
4、 DELETE 删除某个内容
2、HTTP请求报文
HTTP请求报文由请求行(request line)、请求头部(header)、空行和请求数据4个部分组成。
(1)、请求行
请求行由请求方法字段、URL字段和HTTP协议版本字段3个字段组成，他们用空格分隔。如：GET /index.html HTTP/1.1
请求方法有：GET(通过请求URI得到资源)、POST(用于添加新的内容)、PUT(用于修改某个内容)、DELETE(删除某个内容)
(2)请求头部
请求头部由关键字/值对组成，每行一对，关键字和值用英文冒号”:”分隔。请求头部通知服务器有关于客户端请求的信息。
(3)空行
最后一个请求头之后是一个空行，发送回车符和换行符，通知服务器以下不再有请求头。
(4)请求数据
请求数据不在GET方法中使用，而是在POST方法中使用。POST方法适用于需要客户填写表单的场合。与请求数据相关的最长使用的请求头是Content-Type和Content-Length。
3、Http和Https
1、 Http 超文本传输协议，传输的数据是未加密的，不安全
是一个客户端和服务器端请求和应答的标准TCP，用于从WWW服务器传输超文本到本地浏览器的传输协议，可以使浏览器更加高效，使网络传输减少。
2、 Https
由SSL+Http协议构建的可进行加密传输，身份认证的网络协议。是以安全为目标的Http通道，是Http的安全版。即Http下加入SSl层。
3、SSL Secure Sockets Layer协议
用于对HTTP协议传输的数据进行加密，从而诞生了Https
4、Http和Https的区别
(1)、Https协议需要到CA申请证书，一般免费证书较少，因而需要一定费用。
(2)、Http是超文本传输协议，信息是明文传输， Https是具有安全性的SSL加密传输协议
(3)、Http和Https使用的是完全不同的连接方式，使用的端口也不同 Http(80端口)、Https(443端口)
(4)、Http的连接很简单，是无状态的
Https协议是由SSL+Http协议构建的可进行加密传输、身份认证的网络协议，比Http安全。
4、HTTP状态码
常见的状态码：
HTTP:Status 200 服务器成功返回网页
HTTP:Status 404 请求的网页不存在
HTTP:Status 503 服务不可用
HTTP:Status 1xx临时响应表示临时响应并需要请求者继续执行操作的状态代码。
100继续请求者应当继续提出请求。
服务器返回此代码表示已收到请求的第一部分，正在等待其余部分。
101切换协议请求者已要求服务器切换协议，服务器已确认并准备切换。
HTTP:Status 2xx成功表示成功处理了请求的状态代码
200成功服务器成功返回网页，服务器已成功处理了请求。
201已创建请求成功并且服务器创建了新的资源。
202已接受服务器已接受请求，但尚未处理。
203非授权信息服务器已成功处理了请求，但返回的信息可能来自另一来源。
204无内容服务器成功处理了请求，但没有返回任何内容。
205重置内容服务器成功处理了请求，但没有返回任何内容。
206部分内容服务器成功处理了部分GET请求。
HTTP:Status 4xx请求错误表示请求可能出错，妨碍了服务器的处理
400错误请求
401未授权
403禁止
404未找到请求的网页不存在，服务器找不到请求的网页。
405方法禁用
406不接受
407需要代理授权
408请求超时
409冲突
410已删除
411需要有效长度
412为满足前提条件
413请求实体过大
414请求的URI过长
415不支持的媒体类型
416请求范围不符合要求
417为满足期望值
HTTP:Status 5xx服务器错误表示服务器在尝试处理请求时发生内部错误，这些错误可能是服务器本身的错误，而不是请求出错。
500服务器内部错误
501尚未实施
502错误网关
503服务不可用
504网关超时
505HTTP版本不受支持
5、连接和长连接
1、 短连接 连接->传输数据->关闭连接
(1)、HTTP是无状态的，浏览器和服务器每进行一次HTTP操作，就建立一次连接，但任务结束就中断连接。
(2)、短连接是指Socket连接后，发送，接收完数据后马上断开连接。
2、 长连接 连接->传输数据->保持连接->传输数据->…->关闭连接
(1)、长连接是指Socket连接后，不管是否使用都保持连接，但安全性较差。
3、HTTP协议的长连接和短连接，实际上是TCP协议的长连接和短连接。
4、TCP短连接
(1)、TCP短连接的情况
A、Client向Server发起连接请求，Server接到连接请求，双方建立连接
B、Client向Server发送消息，Server回应Client，一次读写完成
C、Client发起Close操作。
(2)、短连接的优点
管理简单、存在的连接都是有用的连接、不需要额外的控制手段
(3)、短连接的缺点
若客户请求频繁，将在TCP的建立和关闭操作上浪费时间和带宽。
5、TCP长连接
(1)、长连接的情况
A、Client向Server发起连接，Server接受Client连接，双方建立连接。
B、Client与Server完成一次读写操作后，它们之间的连接不会主动关闭，后续的读写操作会继续使用这个连接。
(2)、若一个给定的连接在2小时内没有任何动作，则服务器就会向客户端发送一个探测报文段，客户主机必须处于一下4个状态之一：
A、客户主机依然正常运行，并从服务器可达。
B、客户主机已经崩溃，并且关闭或者正在重新启动。
C、客户主机奔溃并已经重新启动
D、客户主机正常，但是服务器不可达。
(3)、长连接的优点
省去较多的TCP建立和关闭的操作、减少浪费、节约时间。
(4)、长连接的缺点
存活功能的探测周期太长、在长连接时，Client端一般不会主动关闭连接，若Client与Server之间的连接一直不关闭，当客户端越老越多时，消耗Server的资源。
6、Spring框架
Spring是一个J2EE的框架，这个框架提供了对轻量级IoC的良好支持，同时也提供了对AOP技术非常好的封装。Spring框架的设计更加模块化，框架内的每个模块都能完成特定的工作，而且各个模块可以独立地运行，不会相互牵制。
Spring框架的好处：
1、Spring有效地管理了中间层的代码，采用了IoC控制反转和AOP面向切面编程的思想，易进行单独测试。
2、使用面向接口编程而不是面向类编程，有更好的可扩展性。
3、Spring对数据的存取提供了一个一致的框架。
Spring框架主要由7个模块组成：
Spring AOPSpring ORMSpring WebSpring Web MVC
Spring DAOSpring Context
Spring Core
1、Spring AOP 面向切面
采用了面向切面编程的思想，使Spring框架管理的对象支持AOP，同时这个模块也提供了事物管理，可以不依赖具体的EJB组件，就可以将事物管理集成到应用程序中。
2、Spring ORM 对象关系映射 (对象关系映射，对象模型->关系模型)
提供了对现有ORM框架的支持，例如Hibernate、JDO等。
3、Spring DAO 数据访问对象
(1)、提供了对数据访问对象(Data Access Object，DAO)模式和JDBC的支持。
(2)、DAO可以实现把业务逻辑与数据库访问的代码实现分离，从而降低代码的耦合度。
(3)、通过对JDBC的抽象，简化了开发工作，同时简化了对异常的处理。
4、Spring Web
提供了Servlet监听器的Context和Web应用的上下文。
5、Spring Context
扩展核心容器，提供了Spring上下文环境。
6、Spring Web MVC
提供了一个构建Web应用程序的MVC的实现。
7、Spring Core
(1)、Spring框架的核心容器，提供了Spring框架的基本功能。
(2)、该模块中最主要的一个组件为：BeanFactory
7、Spring的IoC
1、IoC控制反转
是一种降低对象之间耦合关系的设计思想。通过读取XML文件的方式来实例化对象。
2、分层体系结构与IoC方式的区别
(1)、分层体系结构
上层调用下层的接口，上层依赖于下层的执行，即调用者依赖于被调用者。
(2)、IoC方式
上层不再依赖下层的接口。即通过采用一定的机制选择不同的下层实现，完成控制反转，使得由调用者来决定被调用者。
3、IoC的优点
(1)、采用Ioc机制能够提高系统的可扩展性
(2)、通过IoC容器(如Spring)，开发人员不需要关注对象如何被创建
方便增加新类、只需修改配置文件即可实现对象的“热插拔”。
(3)、IoC容器可通过配置文件来确定需要注入的实例化对象，便于单元测试。
4、IoC的缺点
(1)、对象是通过反射机制实例化出来的，对系统有一定的影响。
(2)、创建对象的流程变得比较复杂。
5、IoC的应用
抽象工厂模式
8、Spring动态代理
AOP面向切面编程
面向对象的特点是继承、多态和封装。而封装就要求将功能分散到不同的对象中去(职责分配)，即让不同的类设计不同的方法。好处是：降低了代码的重复程度，使类可重用。缺点：在分散代码的同时，增加了代码的重复性。如：在两个类中，可能都需要在每个方法中做日志，根据面向对象的方法，必须在两个类的方法中都加入日志的内容。虽然内容相同，但是因为面向对象的设计让类与类之间无法联系，导致不能将这些重复的代码统一起来。
可以在运行时，动态地将代码切入到类的指定方法、指定位置上的编程思想就是面向切面的编程。
1、AOP面向切面编程:Aspect-Oriented Programming
允许开发人员在不改变原来模型的基础上动态的修改模型以满足新的要求。如：在不改变原来业务逻辑模型的基础上，可动态地增加日志，安全或异常处理的功能。
1、过滤器
Filter使用户可以改变一个request并且修改一个response。Filter不是一个Servlet，不能产生一个response，但它能够在一个request到达Servlet之前预处理request，也可以在离开Servlet时处理response。Filter其实是一个”Servlet Chainning”(Servlet链)
一个filter的作用包括以下几个方面：
(1)、在Servlet被调用之前截获
(2)、在Servlet被调用之前检查Servlet Request。
(3)、根据需要修改Request头和Request数据。
(4)、根据需要修改Response头和Response数据。
(5)、在Servlet被调用之后截获。
2、优点和缺点：
过滤器可以对几乎所有请求进行过滤，缺点是一个过滤器实例只能在容器初始化时调用一次。
3、使用过滤器的目的
用来做一些过滤操作，获取我们想要获取的数据。如：在过滤器中修改字符编码；在过滤器中修改HttpServletRequest的一些参数，包括：过滤低俗文字、危险字符等。
10、拦截器Interceptor
拦截器不依赖于Servlet容器，依赖于Web框架，在SpringMVC中就是依赖于SpringMVC框架。在实现上基于Java的反射机制，属于面向切面编程(AOP)的一种应用。
由于拦截器是基于web框架的调用，因此可以使用Spring的控制反转获取容器中的各个bean，进行一些业务操作，同时一个拦截器实例在一个controller生命周期之内可以多次调用。缺点：只能对controller请求进行拦截，对其他的一些(如直接访问静态资源的请求)则没办法拦截处理，拦截器在堆请求权限鉴定方面有很大用处。
Spring过滤器和拦截器的区别
1、联系
(1)、Spring中拦截器与Servlet的过滤器，二者都是AOP编程思想的体现。
(2)、都能实现权限检查、日志记录等。
2、区别
(1)、使用范围不同
Filter过滤器是Servlet规定的，只能用于web程序；
Interceptor拦截器既可以用于Web程序，也可用于Apllication，Swing程序中。
(2)、规范不同
Filter过滤器是Servlet规范定义的，是Servlet容器支持的；
Interceptor拦截器是在Spring容器内的，Spring框架所支持的。
(3)、使用资源不同
同其他代码块一样，拦截器是一个Spring的组件，由Spring管理。配置在Spring中，因此能使用Spring中的任何资源、对象，例如Service对象、数据源、事务管理等。该实现可以通过IoC(控制反转)注入到拦截器即可，而filter过滤器则不能。
(4)、深度不同
Filter只在Servlet前后起作用，而拦截器能深入到方法前后，异常抛出前后因为拦截器的使用具有更大的弹性，所以在spring中优先使用拦截器。
数据库原理
1、SQL语言的功能
SQL结构化查询语言，其功能有：数据查询、数据操纵、数据定义、数据控制
delete和truncate命令的区别
同：都可以用来删除表中的数据
不同：
truncate是数据定义语言，会被隐式的提交，一旦执行不可回滚；delete是一次删除一行数据，删除操作保存在日志中，可以回滚
delete后，被删除的数据存储空间还在，可以恢复；truncate删除后空间释放，数据不可恢复
truncate执行速度比delete快
2、内连接与外连接
1、 内连接(自然连接)
只有两个表相匹配的行才能在结果集中出现，返回的结果集选取了两个表中所有相匹配的数据，舍弃了不匹配的数据。
select fieldlist from table1 [inner] join table2 on table1.column=table2.column
2、 外连接
外连接不仅包含符合连接条件的行，而且还包括左表(左外连接)、右表(右外连接)、两个边接表(全外连接)的所有数据行。
SQL的外连接共有3种类型：
(1)、左外连接 left outer join
select * from A left outer join B on A.column=B.column
(2)、右外连接 right outer join
select * from B right outer join B on A.column=B.column
(3)、全外连接 full outer join
select * from A full outer join B on A.column=B.column
3、事务
事务:是由一条或多条对数据库操作的SQL语句所组成的一个不可分割的工作单元。
结束事务的方法:
(1)、commit()方法：完成对事务的提交
(2)、rollback()方法：完成事务回滚，用于在处理事务的过程中出现了异常的情况
3.设置禁止自动提交
setAutoCommit(false)
4、事务的4个属性(ACID)
(1)、原子性 Atomicity
事务是一个不可分割的整体，为了保证事务的总体目标，事务必须具有原子性，即当数据修改时，要么全执行，要么全不执行，不允许事务部分地完成。
(2)、一致性 Consistency
一个事务执行之前和执行之后，数据库数据必须保持一致性状态。
由于并发操作带来的数据不一致性包括：读脏数据、不可重复读、虚读
(3)、隔离性 Isolation
当两个或多个事务并发执行时，为了保证数据的安全性，将一个事务内部的操作与事务的操作隔离起来，不被其他正在进行的事务看到，即一个事务的执行不能被其他事务干扰。对任何一对事务T1和T2，对T1而言，T2要么在T1开始之前已经结束，要么在T1完成之后再开始执行。
4种类型的事务隔离级别：不提交读、提交读、可重复读、可序列化。
因为隔离性使得每个事务的更新在它被提交之前，对其他事务都是不可见的，所以，实现隔离性是解决临时更新与消除级联回滚的一种方式。
(4)、持久性 Durability
事务完成以后，DBMS保证它对数据库中的数据的修改是永久性的，当系统或介质发生故障时，该修改也永久保持。
持久性一般通过数据库备份与恢复来保证。
4、五种事务隔离级别
(1)、transaction_none jdb 不支持事务
(2)、transaction_read_uncommitted 未提交读
在提交前，一个事务可以看到另一个事务的变化。
允许读脏数据、不可重复读、虚读
(3)、transaction_read_committed 已提交读
不允许读取未提交的数据
允许不可重复读、虚读
(4)、transaction_repeatable_read 可重复读
事务能够保证再次读取相同的数据而不会失败
允许虚读
(5)、transaction_seriabizable 可序列化(串行化)
事务的最高级别
防止读脏数据、不可重复读、虚读
5、设置事务的隔离级别
通过Connection对象的conn.setTransactionLevel()方法
6、确定当前事务的隔离级别
通过Connextion对象的conn.getTransactionIsolation()方法
4、数据库范式
按照“数据库规范化”对表进行设计，其目的是减少数据库中的数据冗余，以增加数据的一致性
1、 第一范式1NF
强调列的原子性，即列不能再分成其他几列。
2、 第二范式2NF
首先是1NF，另外包含两部分内容：
(1)、表必须有一个主键
(2)、没有包含在主键中的列必须完全依赖于主键，而不能只依赖主键的一部分。
3、 第三范式3NF
首先是2NF，且非主键列必须直接依赖于主键，不能存在传递依赖。
即，不能存在非主键列A依赖于非主键列B，非主键列B依赖于主键的情况。
4、2NF和3NF的区分
(1)、2NF，非主键列是否完全依赖于主键，不能依赖于主键的一部分。
(2)、3NF，非主键列直接依赖于主键，不能直接依赖于非主键列。
5、BCNF
首先是3NF，每个属性都不传递依赖于主键
5、视图
1、 视图是由数据库的基本表中选取出来的数据组成的逻辑窗口，是一个虚表。
2、 在数据库中，存放的只是视图的定义，视图包含的数据项仍然存放在原来的基本表结构中。
3、 视图的作用
(1)、可以简化数据查询语句
(2)、使用户能从多角度看待同一数据
(3)、通过引入视图，可以提高数据的安全性
(4)、视图提供了一定程度的逻辑独立性。
6、乐观锁、悲观锁，介绍乐观锁在项目中怎么使用的
1、 悲观锁(悲观并发控制)
(1)、假定其他用户企图访问或者修改你正在访问，更改的对象概率极高。若一个事务执行的操作读某行数据应用了锁，只有当该事务把锁释放，其他事务才能够执行与该锁冲突的操作。
(2)、悲观锁的缺陷
加锁的时间较长，长时间的限制其他用户的访问；悲观锁的并发性不好。
(3)、悲观锁的使用
select * from A where name=’李四’ for update
2、 乐观锁(乐观并发控制)
(1)、假设多用户并发的事务在处理时不会互相影响，各事务能在不产生锁的情况下处理各自影响的那部分数据。在提交数据更新之前，每个事务会先检查在该事务读取数据后，有没有其他事务修改了该数据。若其他事务有更新的话，正在提交的事务会进行回滚。
(2)、乐观锁的使用
start transaction
select * from A where name=’李四’
update A set sex=’男’ where name=’李四’ and updatetime=上面查出值
commit id,name,sex updatename
7、并发控制的主要技术
1、 封锁Locking
在事务T对某个数据对象(表、记录)等操作之前，先向系统发出请求，对其加锁，在事务T释放它的锁之前，其他事务不能更新此数据对象。
基本的锁有两种：排它锁(X锁)、共享锁(S锁)
(1)、排它锁(X锁、写锁)
排它锁又称为写锁。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放A上的锁。这就保证了其他事务在T释放A上的锁之前不能再读取和修改A。
(2)、共享锁(S锁、读锁)
共享锁又被称为读锁。当事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。这就保证了其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。
2、 时间戳Timestamp
3、 乐观控制法
8、死锁和活锁
1、活锁
T1T2T3T4
Lock(R)
Lock(R)
等待Lock(R)
Unlock(R)等待Lock(R)Lock(R)
等待Unlock(R)等待
等待 Lock(R)
(1)、形成活锁的原因
A、若事务T1封锁了数据R，事务T2又请求封锁R，则T2等待。
B、T3也请求封锁R，当T1释放了R上的封锁后，系统首先批准了T3的请求，T2仍等待。
C、T4又请求封锁R，当T3释放了R上的封锁之后，系统又批准了T4的请求。
D、T2可能永远等待，形成了活锁。
(2)、避免活锁的方法
采用先来先服务的策略
2、死锁
T1T2
Lock(R1)
Lock(R2)
Lock(R2)
等待Lock(R1)
等待等待
(1)、形成死锁的原因
A、事务T1封锁了数据R1，事务T2封锁了数据R2
B、T1请求封锁R2，于是T1等待T2释放R2上的锁
C、T2请求封锁R1，于是T2等待T1释放R1上的锁
D、这种互相等待对方的资源，形成死锁。
(2)、解决死锁的方法
A、破坏产生死锁的条件，采取一定措施预防死锁的发生：一次封锁法、顺序封锁法
B、允许发生死锁，采用一定手段定期诊断系统中有无死锁，若有，则解除。
9、数据库是怎么实现隔离级别的
数据库有4种隔离级别：
1、 read_uncommited 未提交读
(1)、原理
事物对当前被读取的数据不加锁；事物在更新某数据的瞬间(发生更新的瞬间)，必须先对其加“行级共享锁”，直到事物结束才释放。
(2)、表现
在提交前，一个事物可以看到另一个事物的变化；允许读脏数据、不可重复读、虚读
2、 read_commited 已提交读
(1)、原理
事物对当前被读取的数据加“航级共享锁”(当读到时才加锁)，一旦读完该行，立即释放该行级共享锁
(2)、表现
不允许读取未提交的数据；允许不可重复读、虚读。
3、 repeatable read 可重复读
(1)、原理
事物在读取某数据的瞬间(开始读取的瞬间)，必须先对其加“行级共享锁”，直到事物结束后才释放；事物在更新某数据的瞬间(发生更新的瞬间)，必须先对其加“行级排他锁”，直到事物结束才释放。
(2)、表现
数据能够保证在此读取相同的数据而不会失败；允许虚读。
4、 serializable 可序列化
(1)、原理
事务在读取数据时，必须先对其叫“表级共享锁”，直到事物结束才释放；事务在更新数据时，必须先对其加“表级排他锁”，直到事务结束才释放。
(2)、表现
事物的最高级别；防止读脏数据、不可重复读、虚读。
10、读脏数据、不可重复读、虚读
1、读脏数据
一个事务读取了另一个事务尚未提交的数据。当事务A与事务B并发执行时，当事务A更新后，事务B查询读取到A尚未提交的数据，此时事务A回滚，则事务B读到的数据是无效的脏数据。
事务A事务B
R(C)=100
C <- C*2
W(C)=200
R(C)=200
ROLLBACK
C恢复为100
2、不可重复读
一个事务的操作导致另一个事务前后两次读取到不同的数据。
当事务A与事务B并发执行时，事务A读取数据后，事务B执行更新操作，使A无法再现前一次读取结果。
事务A事务B
R(A)=50
R(B)=100
求和=150
R(B)=100
B <- B*2
W(B)=200
R(A)=50
R(B)=200
求和=250
验算不对
3、虚读
一个事务的操作导致另一个事务前后两次查询的结果数量不同。
当事务B查询读取数据后，事务A新增或删除了一条满足B的查询条件的记录，此时，事务B再次查询，发现查询到前次不存在的记录。
11、索引
索引是一种结构，加快检索表中数据。索引允许数据库迅速地找到表中的数据，而不必扫描整个数据库。
1、 create index语句用于在表中创建索引。
2、 在不读取整个表的情况下，索引使数据库应用程序可以更快地查找数据。用户无法看到索引，只能被用来加速搜索/查询。
3、 更新一个包含索引的表比更新一个没有索引的表需要更多的时间，因为索引本身也需要更新。
4、 索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。
5、 索引的特点
(1)、索引可以加快数据库的检索速度
(2)、索引降低了数据库插入、修改、删除等维护任务的速度
(3)、索引创建在表上，不能创建在视图上。(视图是一个虚表)
(4)、使用查询处理器执行SQL语句，在一个表上，一次只能使用一个索引。
6、索引的缺点
(1)、创建索引和维护索引需要消耗时间，随着数据量的增加而增加。
(2)、索引需要占物理空间，除了数据表占数据空间外，每一个索引还要占一定的物理空间，若简历聚集索引，则需要的空间就会更大。
(3)、对表中的数据进行增加、删除和修改时，索引要动态的维护，降低了数据的维护速度。
12、聚集索引和非聚集索引的区别
两者的区别：表记录的排序顺序与索引的排列顺序是否一致。
1、 聚集索引(一个表中只能有一个聚集索引)
(1)、聚集索引的定义
为提高某个属性(或属性组)的查询速度，把这个或这些属性上具有相同值的元组几种存放在连续的物理块称为聚集。
(2)、聚集的作用
将某一列(或是多列)在磁盘中的物理顺序改变，为和在SQL SERVER表中的逻辑顺序一致。
(3)、聚集索引
在SQL SERVER中，聚集索引的存储是以B树存储，B树的叶子直接存储聚集索引的数据。由于聚集索引改变的是其所在表的物理存储顺序，因此，每个表只能有一个聚集索引。
2、 非聚集索引
(1)、非聚集索引并不改变其所在表的物理结构，而是额外生成一个聚集索引的B树结构。
(2)、叶子节点是对于其所在表的引用。若其所在表上没有聚集索引，引用行号；若其所在表上有聚集索引，引用聚集索引的页。
(3)、若其所在表的物理结构改变后(加上或是删除聚集索引)，则所有非聚集索引都需要被重建。
3、聚集索引和非聚集索引的区别
(1)、根本区别：表记录的排列顺序和索引的排列顺序是否一致。
聚集索引表记录的排列顺序和索引的排列顺序一致；非聚集索引表记录的排列顺序和索引的排列顺序不一致。
(2)、聚集索引查询速度快
使用聚集索引找到包含第一个值的行后，便可以确保包含后续索引值的行在物理相邻，从而减少了磁盘扫描。
(3)、聚集索引的缺点：对表进行修改速度较慢
为了保持记录表中的记录的物理顺序和索引顺序一致，把记录插入到数据页的相应位置时，必须在数据页中进行数据重排，降低了执行速度。
(4)、聚集索引和非聚集索引都采用B+树的结构，聚集索引的叶节点是数据节点，非聚集索引的叶节点是索引节点。
设计模式
1、设计模式的六大原则
1、开闭原则（Open Close Principle）
开闭原则的意思是：对扩展开放，对修改关闭。
2、里氏代换原则（Liskov Substitution Principle）
里氏代换原则是面向对象设计的基本原则之一。 里氏代换原则中说，任何基类可以出现的地方，子类一定可以出现。
3、依赖倒转原则（Dependence Inversion Principle）
这个原则是开闭原则的基础，具体内容：针对接口编程，依赖于抽象而不依赖于具体。
4、接口隔离原则（Interface Segregation Principle）
使用多个隔离的接口，比使用单个接口要好。降低类之间的耦合度。
5、迪米特法则，又称最少知道原则（Demeter Principle）
一个实体应当尽量少地与其他实体发生相互作用，使得系统功能模块相对立。
6、合成复用原则（Composite Reuse Principle）
合成复用原则是指：尽量使用合成/聚合的方式，而不是使用继承
2、单例模式
分为单线程和多线程2中情况
3、工厂模式
包括：
简单工厂模式：根据提供的参数动态的穿件某一类型的对象。
工厂方法模式：定义一个用于创建产品对象的工厂接口，将实际创建工作推迟到工厂接口的子类中。
抽象工厂模式：
4、适配器模式
5、观察者模式（发布/订阅模式）
数据结构与算法
1、链表
单链表的增删操作
可定义如下链表类来存储结点信息
public class Node {
int data;
Node next = null;
public Node(int data) {
this.data = data;
}
}
链表的基本操作：
public class MyLinkedList { Node head = null; //链表头结点 /**
* 向链表中添加一个元素
* @param data:添加的元素
*/ public void addNode(int data){
Node newNode = new Node(data);
if(head == null){
head = newNode;
return;
}
Node temp = head;
while(temp.next != null){
temp = temp.next;
}
temp.next = newNode;
}
/**
* 删除第index个基点
* @param index:待删除结点索引
* @return 成功返回true，失败返回false
*/ public boolean deleteNode(int index){
//如果删除元素位置不合理 if(index<1 || index>length()){
return false;
}
//删除第index个结点的元素 if(index == 1){
head = head.next;
return true;
}
int i = 2;
Node preNode = head;
Node curNode = head.next;
while(curNode != null){
if(i == index){
preNode.next = curNode.next;
return true;
}
preNode = curNode;
curNode = curNode.next;
i++;
}
return true;
}
/**
* @return 返回链表的长度
*/ public int length(){
int length = 0;
Node temp = head;
while(temp != null){
length++;
temp = temp.next;
}
return length;
}
/**
* 对链表进行排序
* @return 返回排序后链表的头结点
*/ public Node orderList(){
int temp = 0;
Node curNode = head;
Node nextNode = null;
while(curNode.next != null){
nextNode = curNode.next;
while(nextNode != null){
if(curNode.data > nextNode.data){
temp = curNode.data;
curNode.data = nextNode.data;
nextNode.data = temp;
}
nextNode = nextNode.next;
}
curNode = curNode.next;
}
return head;
}
/**
* 打印链表
*/ public void printList(){
Node temp = head;
while(temp != null){
System.out.print(temp.data);
temp = temp.next;
}
}
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList();
list.addNode(2);
list.addNode(1);
list.addNode(2);
list.addNode(3);
list.addNode(5);
System.out.println("before order:");
list.printList();
list.orderList();
System.out.println();
System.out.println("after order:");
list.printList();
list.deleteNode(2);
System.out.println();
System.out.println("删除第二个节点后:");
list.printList();
}
}
2.如何从链表中删除重复数据
方法1：（最容易想到）
遍历链表，将遍历到的值存储到HashTable中，若当前遍历的值在HashTable中
存在，则说明当前数据是重复的，因此删除。
public void deleteDuplecate(Node head){
HashTable table=new HashTable<>();
Node tmp=head;
Node pre=null;
while(tmp!=null){
if(table.containsKey(tmp.data)){
pre.next=tmp.next;
}else{
table.put(tmp.data,1);
pre=tmp;
}
}
}
优点：时间复杂度低
缺点：需要额外的存储空间
方法2：
对链表进行双重循环遍历，外循环正常遍历链表，假设外循环当前遍历的节点为
cur,内循环从cur开始遍历，若遇到与cur相同的值，则删除这个重复的节点。
public void deleteDuplecate(Node head){
Node p=head;
while(p!=null){
Node q=p;
while(q.next!=null){
if(p.data==q.next.data){
q.next=q.next.next;
}else{
q=q.next;
}
}
p=p.next;
}
}
优点：不需要额外存储空间
缺点：时间复杂度高
3、如何找出单链表中的倒数第K个元素
方法1：
先遍历一遍链表计算出链表长度n,要求出倒数第k个元素，转化为正数第n-k个元素，然后在遍历一遍链表，得到倒数第k个元素。
缺点：要遍历2遍链表
方法2：
设置2个指针，让其中一个比另外一个先前移k-1步，然后两个指针同时往前移动。循环直到现行的指针值为null,另一个指针所在的位置就是所要查找的位置。
public Node findElem(Node head,int k){
if(k<1 || head == null){
return null;
}
Node p1 = head;
Node p2 = head;
for (int i = 0; i < k - 1; i++) { //前移k-1步 if(p2.next != null){
p2 = p2.next;
}else {
return null;
}
while (p2 != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
4、如何实现链表的反转
反转前：a->b->c->d
反转后：a<-b<-c<-d
public void ReverseIteratively(Node head){
Node pReversedHead = NULL;
Node pNode = head;
Node pPrev = NULL;
while(pNode != NULL){
Node pNext = pNode.next;
if(pNext == NULL)
pReversedHead = pNode;
pNode.next = pPrev;
pPrev = pNode;
pNode = pNext;
}
return this.head= pReversedHead;
}
5、如何从尾到头输出单链表
方法1：
将链表反转，然后遍历输出
缺点：需要额外的操作
方法2：
从头到尾遍历链表，将每个节点值放入栈中，遍历完链表后，从栈顶输出元素
缺点：需要额外的栈空间
方法3：
递归的本质是栈结构
要反转输出链表，每访问一个节点，先递归输出它后面的节点，再输出该节点自
身，这样链表就反过来输出了。
public void printListReversely(Node pListHead) {
if(pListHead != null){
printListReversely(pListHead.next); }
System.out.println(pListHead.data);
}
6、如何寻找单链表的中间结点
方法1：
遍历链表求出链表长度length，然后再遍历length/2的距离，即可查到中间结点。
缺点：2次遍历链表
方法2：
若是双向链表，可以首尾同时并行，当2个指针相遇，就找到了中间元素。
若是单链表，也采用双指针的方法，具体而言：(1)有两个指针同时从头开始遍历；
（2）一个快指针每次走2步，一个慢指针一次走1步；（3）快指针先到链表尾部，而慢指针刚好到达链表中部（当快指针到达尾部，若是奇数个元素，则慢指针指向的就是中间元素；若是偶数个元素，则慢指针指向的结点和慢指针的下一个结点都是中间结点。）
public Node SearchMid(Node head){
Node p=this.head;
Node q=this.head;
while(p!=null&&q.next!=null&&p.next.next!=null){
p=p.next.next;
q=q.next;
}
return q;
}
7、如何检测一个链表中是否有环
定义两个指针fast和slow，初始都指向链表头，fast每次前进两步，slow每次走一步，两个指针同时向前移动，快指针每次移动都要和慢指针进行比较，直到快指针等于慢指针，就证明这个链表是带环的单向链表，否则，证明是循环链表（fast先行到达尾部为null，则链表为无环链表）。
public boolean IsLoop(Node head) {
Node fast = head;
Node slow = head;
if(fast==null){
return false;
}
while( fast != null&& fast->next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return !(fast ==null || fast.next==null);
}
检测环的入口：
public Node FindLoopPort(Node head) {
Node fast = head;
Node slow = head;
while( fast != null&& fast->next != null) {
fast = fast.next.next;
slow = slow.next; if(fast == slow) {
break;
}
}
if(fast == null|| fast.next == null)
return null;
slow = head;
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
8、如何在不知道头指针的情况下删除指定结点
分2种情况谈论：
若待删除的结点为链表尾结点，则无法删除，因为删除后无法使其前驱结点的next指针置为空；
若待删除的结点不为尾结点，则可以通过交换这个结点与其后继结点的值，然后删除后继结点
public boolean deleteNode(Node n){
if(n==null || n.next==null)
return fasle;
int tmp=n.data;
n.data=n.next.data;
n.next=n.next.next;
return trun;
}
9、如何判断两个链表是否相交
如果两个链表相交，那么他们一定有相同的尾结点。
public boolean isIntersect(Node h1,Node h2){
if(h1==null || h2==null)
return false;
Node tail1=h1;
while(tail1.next!=null){
tail1=tail1.next;
}
Node tail2=h2;
while(tail2.next!=null){
tail2=tail2.next;
}
return tail1==tail2;
}
时间复杂度：O(len1+len2)
引申：如果两个链表相交，如何找到它们相交的第一个结点？
首先，分别计算两个链表head1、head2的长度len1、len2（假设len1>len2），接着先对链表head1遍历（len1-len2）个结点到结点p，此时结点p和head2到它们相交的结点的距离相同，此时同时遍历两个链表，直到遇到相同的结点为止，这个结点就是相交的第一个结点。
public static Node getFirstMeetNode(Node h1,Mode h2){
if(h1==null || h2 ==null){
return null;
}
Node tail1=h1;
int len1=1;
while(tail1.next!=null){
tail1=tail1.next;
len1++;
}
Node tail2=h2;
int len2=1;
while(tail2.next!=null){
tail2=tail2.next;
len1++;
}
if(tail1 !=tail2)
return null;
Node t1=h1;
NOde t2=h2;
if(len1>len2){
int d=len1-len2;
while(d!=0){
t1=t1.next;
d--;
}
}else{
int d=len2-len1;
while(d!=0){
t2=t2.next;
d--;
}
}
while(t1!=t2){
t1=t1.next;
t2=t2.next;
}
return t1;
}
缺点：需要遍历2遍
O(len1+len2)
2、栈与队列
1、站与队列的区别
栈：先进后出
队列：先进先出
2、如何实现栈
可以采用数组和链表两种方式实现栈。
3、如何用O(1)的时间复杂度求栈中最小元素
一个栈存储数据，另一个栈存储最小元素。
实现思路如下：
（1）使用 elem 和 min 两个栈结构，elem 用来存储数据，min 用来存储 elem 栈的最小元素。
（2）在入栈时，如果当前入栈的元素比原来栈中的最小值还小，则把这个值压入 min 栈中；
（3）在出栈时，如果当前出栈的元素巧好为当前栈中的最小值，则 min 栈的栈顶元素也出栈，是的当前最小值变为其入栈之前的那个最小值。
public class GetStackMinEle {
MyStack elem;
MyStack min;
public GetStackMinEle() {
elem = new MyStack();
min = new MyStack();
}
// 入栈时需要考虑当前元素是否是当前栈最小元素，是的话当前元素也要压入 min 栈中 public void push(int data) {
elem.push(data);
if(min.isEmpty())
min.push(data);
else {
if(data < min.peek())
min.push(data);
}
}
//出栈时，需要判断 elem 栈顶元素是否为当前栈的最小值，是的话，min 栈顶元素也要出栈 public int pop() {
int topData = elem.peek();
elem.pop();
if(topData == this.min())
min.pop();
return topData;
}
public int min() {
if(min.isEmpty())
return Integer.MAX_VALUE;
else return min.peek();
}
}
4、如何实现队列
队列实现:数组和链表
5、如何使用两个栈模拟队列操作
3、排序
1、选择排序
原理：给定一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录位置交换；接着将不包括第一个记录的其他记录记性第二轮比较，得到最小记录并于第二个记录位置交换；以此类推。
public static void selectSort(int[] a){
int temp=0;
int flag=0;
for(int i=0;i
temp=a[i];
flag=i;
for(int j=i+1;j
if(a[j]
temp=a[j];
flag=j;
}
}
if(flag!=i){
a[flag]=a[i];
a[i]=temp;
}
}
}
2、插入排序
原理：给定一组记录，初始时假设第一个记录是有序的，其余的为无序的。从第二个记录开始，将记录插入到之前有序的序列中，直到最后一个记录插入到有序序列中。
public static void insertSort(int[] a){
for(int i=1;i
int temp=a[i],j=i;
if(temp
while(j>=1&&temp
a[j]=a[j-1];
j--;
}
}
a[j]=temp;
}
}
3、冒泡排序
原理：对于给定的一组记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的大于后面的记录时，交换位置，进行一轮比较和交换之后，n个记录最大的位于第n位置上；然后对前n-1个记录进行类似操作。
public static void BubbleSort(int[] a){
for(int i=a.length-1;i>=0;i--){
for(j=0;j
if(a[j]>a[j+1]){
int tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
}
4、归并排序
原理：对于给定的记录，现将每两个相邻长度为1的子序列进行递归，得到n/2个长度为2或者1的有序子序列，再将其两两归并，如此反复
public static void MergeSort(int[] array, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左边
sort(array, low, mid);
// 右边
sort(array, mid + 1, high);
// 左右归并
merge(array, low, mid, high);
}
}
public static void merge(int[] array, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (array[i] < array[j]) {
temp[k++] = array[i++];
} else {
temp[k++] = array[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = array[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = array[j++];
}
// 把新数组中的数覆盖array数组
for (int k2 = 0; k2 < temp.length; k2++) {
array[k2 + low] = temp[k2];
}
}
5、快速排序
原理：
public static void quickSort(int a[], int low, int hight) {
int i, j, index;
if (low > hight) {
return;
}
i = low;
j = hight;
index = a[i]; // 用子表的第一个记录做基准
while (i < j) { // 从表的两端交替向中间扫描
while (i < j && a[j] >= index)
j--;
if (i < j)
a[i++] = a[j];// 用比基准小的记录替换低位记录
while (i < j && a[i] < index)
i++;
if (i < j) // 用比基准大的记录替换高位记录
a[j--] = a[i];
}
a[i] = index;// 将基准数值替换回 a[i]
sort(a, low, i - 1); // 对低子表进行递归排序
sort(a, i + 1, hight); // 对高子表进行递归排序
}
6、希尔排序（缩小增量排序）
原理：先讲待排序数组分为多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序
public static void shellSort(int array[ ]){
if(arrays == null || arrays.length <= 1){
return;
}
//增量
int incrementNum = arrays.length/2;
while(incrementNum >=1){
for(int i=0;i
//进行插入排序
for(int j=i;j
if(arrays[j]>arrays[j+incrementNum]){
int temple = arrays[j];
arrays[j] = arrays[j+incrementNum];
arrays[j+incrementNum] = temple;
}
}
}
//设置新的增量
incrementNum = incrementNum/2;
}
}
7、堆排序
public void HeapAdjust(int[] array, int parent, int length) {
int temp = array[parent]; // temp保存当前父节点
int child = 2 * parent + 1; // 先获得左孩子
while (child < length) {
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
if (child + 1 < length && array[child] < array[child + 1]) {
}
// 如果父结点的值已经大于孩子结点的值，则直接结束
if (temp >= array[child])
break;
// 把孩子结点的值赋给父结点
array[parent] = array[child];
// 选取孩子结点的左孩子结点,继续向下筛选
parent = child;
child = 2 * child + 1;
}
array[parent] = temp;
}
public void heapSort(int[] list) {
// 循环建立初始堆
for (int i = list.length / 2; i >= 0; i--) {
HeapAdjust(list, i, list.length - 1);
}
// 进行n-1次循环，完成排序
for (int i = list.length - 1; i > 0; i--) {
// 最后一个元素和第一元素进行交换
int temp = list[i];
list[i] = list[0];
list[0] = temp;
// 筛选 R[0] 结点，得到i-1个结点的堆
HeapAdjust(list, 0, i);
System.out.format("第 %d 趟: \t", list.length - i);
printPart(list, 0, list.length - 1);
}
}
8、各种排序算法优劣
4、位运算
1、如何用移位操作实现乘法运算
左移n位相当于把一个数乘以2的n次方；右移是除以2的n次方
2、如何判断一个数是否为2的n次方
方法1：
用1做移位操作，然后判断移位后的值是否与给定的值相等。
方法2：
将待判断的数减1然后再和待判断的数进行与操作
3、求二进制中1的个数
判断这个数最后一位是否为1，如果为1，则计数器加1，然后将这个数右移1位丢弃掉最后一位。循环至这个数为0.判断二进制最后一位是否为1时，可以采用与1与运算达到目的。
5、数组
1、如何寻找数组中的最小值与最大值
方法1：问题分解法。每次没别找出最大值和最小值。一共需要遍历2次数组。O(2n)
方法2：取单元素法。维持两个变量min和max,每次取出一个元素先个最小值比较，再与最大值比较。只需遍历一次数组。O(n)
方法3：取双元素法。O(1.5n)
2、如何找出数组中第二大的数
方法：定义两个变量，一个用于存储数组的最大数，初始值为数组首元素，另一个变量存储数组元素的第二大数，初始值为最小负整数，然后遍历数组元素，如果数组元素值比最大数变量的值大，则将第二大数值更新为最大数变量的值，最大数变量的值更新为该数组的值，若该数组元素的值比最大数的值小，则判断是否比第二大数值大，如数组元素的值比第二大数值大，则第二大数更新为该元素值。
public static int FindSecMax(int data[ ]){
int count=data.length;
int maxnumber=data[0];
int sec_max=Integer.MIN_VALUE;
for(int i=0;i
if(data[i]>maxnumber){
sec_max=maxnumber;
maxnumber=data[i];
}else{
if(data[i]>sec_max)
sec_max=data[i];
}
}
return sec_max;
}
3、如何求最大子数组之和
方法1：蛮力法。O(n^3)
public static int maxSubArray(int arr[ ]){
int ThisSum=0,MaxSum=0;
for(int i=0;i
for(int j=i;j
ThisSum=0;
for(int k=i;k
ThisSum += arr[k];
if(ThisSum>MaxSum){
MaxSum=ThisSum;
}
}
}
}
return MaxSum;
}
方法2：O(n^2)
public static int maxSubArray(int arr[ ]){
int size=arr.length;
int maxSum=Integer.MIN_VALUE;
for(int i=0;i
int sum=0;
for(int j=i;j
sum += arr[j];
if(sum >maxSum){
maxSum=sum;
}
}
}
}
return MaxSum;
}
方法3：动态规划法。O(n)
public static int maxSubArray(int arr[ ]){
int End[]=new int [n];
int All[]=new int [n];
End[n-1]=arr[n-1];
All[n-1]=arr[n-1];
End[0]=All[0]=arr[0];
for(int i=1;i
End[i]=max(End[i-1]+arr[i],arr[i]);
All[i]=max(End[i],All[i-1]);
}
return All[n-1];
}
4、如何找出数组中重复元素最多的数
方法1：空间换时间（不推荐）
方法2：使用Map表
public staticintfindMostFrequentInArray(int[] a){
int result=0;
int size=a.length;
if(size==0)
return Integer.MAX_VALUE;
Map m=new hashMap<>();
for(int i=0;i
if(m.containsKey(a[i])){
m.put(a[i],m.get(a[i])+1);
}else{
m.put(a[i],1);
}
}
int most=0;
Iterator iter=m.entrySet().iterator();
while(iter.hasNext()){
Map.Entry entry=(Map.Entry )iter.next();
int key=(Integer)entry.getkey();
int val=(Integer)entry.getVlaue();
if(val>most){
result=key;
most=val;
}
}
return result;
}
5、如何求数组中两两相加等于20的组合种数
方法1：蛮力法O(n^2)
public static void findSum(int[] a,int sum){
for(int i=0;i
for(int j=i;j
if(a[i]+a[j]==sum){
system.out.println(a[i]+","+a[j]);
}
}
}
}
方法2：排序法
先对数组元素进行排序，采用堆或者快速排序，时间复杂度O（nlogn），然后对排序后的数组分别从前到后和从后到前遍历，假设从前往后遍历下标为begin，从后往前遍历下标为end,那么满足arr[begin]+arr[end]<20时，如果存在两个数和为20，那么这两个数一定在[begin+1,end]之间；当满足arr[begin]+arr[end]>20,如果存在两个数和为20，那么这两个数一定在[begin,end+1]之间，这个过程时间复杂度O(n)，因此整个复杂度O（nlogn）.
public static void findSum(int[] a,int sum){
Arrays.stor(a);
int begin=0;
int end=a.length-1;
while(begin
if(a[begin]+a[end]
begin++;
else if(a[begin]+a[end]
end--;
else{
Sysotem.oyt.println(a[begin]+","+a[end]);
begin++;
end--;
}
}
}
6、如何把一个数组循环右移k位 O（n）
public static void reverse（int[] a，int b,int e）{
for(;b
int temp=a[e];
a[e]=a[b];
a[b]=temp;
}
}
public static void shift_k(int a[],int k){
k=k%n;
reverse(a,n-k,n-1);
reverse(a,0,n-k-1);
reverse(a,0,n-1);
}
7、如何找出数组中第k个最小的数
方法1：排序法 O（nlogn）
将数组从小到大进行排序，数组第k-1个就是第k个最小的元素。
方法2：剪枝法
采快速排序的思想来实现。思路：选取一个枢纽temp=a[n-1]，把比它小的放在左边，比它大的放在右边，然后判断temp的位置。如果它的位置为k-1，则它就是第k个最小的元素；如果它的位置小于k-1,则说明第k个最小的元素一定在数组右半边，采用递归在数组右边继续查找；否则在左半边查找。
public static int quikStort(int array[],int low,int high,int k){
int i,j;
int temp;
if(low>hign)
return Integer.MIN_VALUE;
i=low+1;
j=hign;
temp=a[i];
while(i
while(i=temp)
j--;
if(j
array[i++]=array[j];
while(i
i++;
if(j
array[j--]=array[i];
}
array[i]=temp;
if(i+1==k)
return temp;
else if(i+1>k)
return quikStort(array,low,i-1,k);
esle
return quikStort(array,i+1,high,k);
}
8、如何查找数组中出现一次的数字
出现一次的数，其他出现2次
方法1：异或法
任何一个异或它本身为0。
public static int findNotDouble(inr a[]){
int result=a[0];
for(int i=1;i
result^=a[i];
return result;
}
引申：上述方法只使用其他数字出现偶数次。
9、如何找出数组中唯一重复的元素
P272
异或法，空间换时间、位图法
10、如何用递归求一个整数数组的最大元素
递归求解数组第一个元素和数组中其他元素组成的子数组的最大值。
private int max(int a,intr b){
return a>b?a:b;
}
public int maxNumber(int a[],int begin){
int length=a.length-begin;
if(length==1){
return a[begin];
}else{
return max(a[begin],maxNumber(a,begin+1));
}
}
11、如何求数对之差的最大值
p276
12、如何求绝对值最小的元素
13、如何求数组中两个元素最小距离
14、如何求指定数字在数组中第一次出现的位置
15、如何对数组的两个子有序段进行合并
16、如何计算两个有序整数数组的交集
17、如何判断一个数组中的数值是否连续相邻
18、如何求解数组中反序的个数
19、如何求解最小三元组的距离
6、字符串
1、如何实现字符串反转
public void swap(char cArr,int front,int end){
while(front
char tmp=cArr[end];
cArr[end]=cArr[front];
cArr[front]=tmp;
front++;
end--;
}
}
public String swapWords(String s){
char[] cArr=s.toCharArray();
//对整个字符串进行反转
swap(cArr,0,cArr.length-1);
int begin=0;
//对每个单词进行反转
for(int i=1;i
if(cArr[i]==" "){
swap(cArr,begin,i-1);
begin=i+1;
}
}
}
2、如何判断连个字符串是否由相同的字符组成
两个字符串的字母以及相应字母个数相同
方法1：排序法
先将字符串排序，，然后比较。
public static boolean compare（String s1,String s2）{
byte[] b1=s1.getBytes();
byte[] b2=s2.getBytes();
Arrays.sort(b1);
Arrays.sort(b2);
s1=new String(b1);
s2=new String(b2);
if(s1.equeal(s2)){
return true;
}else{
return false;
}
}
方法2：空间换时间
3、如何删除字符串中重复的字符
P298
4、如何统计一行字符中有多少个单词
public static int wordCount(String s){
int word=0;
int count=0;
for(int i=0;i
if(s.charAt(i)==" "){
word=0;
}else if(word==0){
word=1;
count++;
}
}
return count;
}
5、如何按要求打印数组的排列情况
6、如何输出字符串的所有组合
7、二叉树
一一一一一一一一一一一海量数据处理一一一一一一一一一一一一
1、基本方法
hash法、Bit-map法、Bloom filter法、数据库优化法、倒排索引法、外排序法、Trie树、堆、双层桶法、MapReduce法
Hash法
常见构建散列函数的方法：
直接地址法：取关键字或者关键字的某个线性函数值为散列地址。
取模法：
数字分析法：
折叠法：
平方取中法：
除留余数法：
随机数法：
解决冲突的方法：开放地址法、链接地址法、再散列法、建立公共溢出区
Bit-map法
使用位图数组表示某些元素是否存在
2、经典实例分析
top K问题
方法：分治+Trie树/hash+小顶堆
重复问题
方法：位图法
排序问题
方法：数据库排序、分治法、位图法
