Java杂七杂八
Error和exception的区别?Error类一般指的是与虚拟机相关的问题，比如系统崩溃，虚拟机错误，内存空间不足，对于这种错误导致的应用程序中断，仅靠程序本身无法恢复和预防，遇到这样的错误，建议让程序终止。
Exception表示程序可以处理的异常，遇到这类异常，应该尽可能处理异常，使程序恢复运行，而不应该随意终止异常。
1、final定义的常量，一旦初始化，不能被修改，对基本类型来说其值不可变，对引用来说是其引用不可变。其初始化只能再两个地方
其定义处、构造函数中，两者只能选其一，不能在定义时给了值又在构造函数中赋值
不管有无异常发生，finally总会执行，若catch中有return语句也执行。
一个类不能即被定义成abstract又被定义成final
finalize方法定义在object中
在Java中，内存泄漏就是存在一些被分配的对象，这些对象存在以下一些特点
1、对象是可达的
2、对象是无用的
发生内存泄漏的第一个迹象通常是：在应用程序中出现了OutOfMemoryError（OOM）
ArrayList和LinkedList的remove和contains方法都依赖equals方法。
HashSet：底层hash表，若两个元素的hash值不同，则一定不是同一个元素，若hash值相同则判断equals，若equals相同，则是同一个对象，若equals不同，则不是一个对象（hashset的contains和remove依赖于和顺从的和equals）
TreeSet集合的特点是可以对其中的元素进行排序，换句话说，一种情况是放进treeset中的元素必须具有比较性，集合的底层结构是二叉树，保证元素唯一性的方法是compareTo方法返回0.另一种情况是元素没有比较性，但集合有比较性，定义一个类，实现comparator接口，实现一个比较器。
IOC控制反转，容器控制程序对象之间的关系，而不是传统实现中，有程序代码之间控制，又名依赖注入。
所有类的创建、销毁由spring来控制，也就是说控制对象生命周期不是引用他的对象，而是spring。对于某个对象而言，以前是他控制其他对象，现在是所有对象都被spring控制，这就是控制反转。
依赖注入的思想是通过反射机制实现的。在实例化一个类时，它通过反射调用类中的set方法将实现保存在hashmap中的类属性注入到类中。
spring实现aop：jdk动态代理，cglib动态代理。
JDK动态代理：其代理对象必须是某个接口的实现，他是通过在运行期间创建一个接口的实现类来完成对目标对象的代理。
核心类有：InnovationHandler，Proxy
Cglib优点类似jdk动态代理，只是他在运行期间生成的代理对象是针对目标类扩展的子类。MethodInterceptor
多态：父类引用指向子类对象，对于static，编译运行都看左边
二叉平衡树：是一颗空树、或者左右两个子树的高度差绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。
图的深度优先遍历和广度优先遍历。
深度：设x是当前被访问的顶点，在对x做过访问标记后，选择一条从x触发的未检测的边（x,y），若发现顶点y已经访问过，则重新选择另一条从x出发的未检测的边，否则沿边（x，y）到达未曾访问过的y，对y访问并将其标记为已经访问；然后从y离开时搜索，直到搜索完y出发的所有路径，即访问完所有从y出发的所有边都已经检测过为止，遍历结构不唯一。
广度：设x、y是两个相继要访问的未访问过的节点，我们分别从x和y出发搜索器相邻节点x1，x2，x3，xn和y1，y2，yn
对其中未访问者进行访问并将其入队列，这种方法是将每个已经访问的顶点入队，故保证了每个顶点最多有一次入队。
泛型，即参数化类型，泛型擦除：Java编译器生成的字节码文件不包含有泛型信息，泛型信息将在编译时被擦除，这个过程称为泛型擦除，其主要过程为（将所有泛型参数用其最左边界类型替换），移除所有的类型参数。
内存溢出：程序在申请内存时，没有足够的内存空间供其使用。
内存泄漏：分配出去的内存不再使用，但是无法回收。
String s1 = “abcde”;
String s2 = “abc”+”de”;
s1==s2是true
常量池中只会维护一个值相同的String对象。
当调用String类的intern()方法时，若常量池中已经包含一个等于此String字符串（用Object的equals方法确定），则返回池中的字符串，否则将此String 对象在常量池中的引用。比如String s1 = new String(“asd”);s1=s1.intern();
String s2 = “asd”; s1==s2;是true的。
几个String的例子如下：
String s1 = new String(“777”);
String s2 = “aaa777”;
String s4 = “aaa”+s1;
s2==s4是false的
StringBuffer内部实现是char数组，默认初始化长度是16，每当字符串长度大于cache数组长度时，jvm会构造更大的char数组，并将原先的数组内容复制到新数组。
String s=“abc”+“de”，在编译期间就能确定字符串值得情况下，使用效率最高。
String s =”a”+”b”; 只创建了一个对象
String s1=”a”;s1+=”b”;创建了两个对象，第一个是“a”，当执行第二句话时，因为String类不可变性，所以又创建了一个对象
1、String s1= new String(“abc”);
2、String s2 = new String(“abc”);
执行1时，“abc”本来就是池中得对象，而在运行时执行new String(“abc”)，将池中得对象复制一份放到堆中，并且把堆中得这个对象得引用交给s1持有，这条语句就创建了两个对象，执行2后，一共创建了三个对象。
MVC
M：model enetity 业务逻辑
V：view视图，用户看到并与之交互的界面
C：controller根据用户的输入，控制用户界面显示和更新model对象状态，功能模块和显示模块分离，提高可维护性，可复用性，可扩展性。
JDBC中，连接操作是由Driver Manager管理，JDBC的建立和关闭是极其耗资源的，connection接口实现连接数据库。JDBC连接数据库分为4步。
1、加载驱动Class.forName(“com.mysql.jdbc.Driver”)
2、创建连接Connection con = DriverManager.getConnection(url,username,password);
3、创建statement Statement s = con.createStatement()
4、执行sql s.executeQuery();
prepareStatement是预编译的语句，callableStatement：存储过程调用
DatebaseMetaDate类的很多方法都可以知道数据库中存储过程的详情。
servlet：是用于Java编写的服务端程序，其使用java编写的服务器端程序，其使用java servlet API，当客户机发送请求到服务器时，服务器可以将请求发送给servlet，并让servlet建立起服务器返回给客户机响应。当启动web服务器或者客户机第一次请求服务时，可以自动装入servlet。装入后，servlet继续运行直到其他客户机发出请求。
servlet生命周期
servlet生命周期分为3个阶段
1、初始化阶段：调用init方法
2、响应客户请求：调用service
3、终止：调用destory
若两个对象的 equals 为 true，则 hashcode 为 true。
cookie和session http 都是无状态协议，web服务器不能辨别出哪些请求是同一个浏览器发的，浏览器每次请求都是独立的。
cookie放在浏览器端，浏览器第一次访问服务器时，没有cookie，然后服务器给浏览器一个cookie，以后每次浏览器访问服务器都要带上这个cookie
默认情况下cookie是会话级别，存储在浏览器内存中，用户退出浏览器被删除，若希望浏览器将cookie存在磁盘上，则要使用maxage，并给一个秒为单位的时间，表示cookie可以存活的时间。
cookie作用范围：可以作用当前目录和当前子目录，但不能作用与当前目录的上一级。
cookie：在客户端保持http状态信息的方案会话跟踪。
session在服务器端保持http状态信息。
当浏览器第一次访问服务器时，没有cookie，服务器也就得不到JSession_id，然后服务器创建一个session对象，并返回一个JSession_id给浏览器，通过cookie返回，下次浏览器再访问服务器就带上cookie，其中有（JSession_id），服务器就能找到对应的session对象。
JSession_id可以通过cookie传输，也可以通过url传送
一个session对应一个sessionID
session：浏览器和服务器的一次会话，若浏览器不关，至始至终都是一个session，因为用cookie传送。
URL重写：response的encodeURL（String URL）方法和encoderredirectURL（String URL）两个都一样。
当程序需要为某个客户端的请求创建session时，服务器首先检查这个客户端的请求是否包含一个session的表示，如果包含就说明以前已经为此客户创建过JSession_id，服务器就按照这个JSession_id检索出来（若检索不到，可能会新建一个，这种情况下可能会出现再服务器已经删除了该用户的session对象。但用户人为的请求在URL上赋一个JSession_Id的参数）如不包含则创建一个session，并生成与这个session有关的JSession_id，这个JSession_id将在本次响应中返回给客户端。
默认session用cookie
若第一访问某web应用程序的一个jsp页面，且该jsp页面的page指定session=true，服务器会创建一个httpsession对象
关闭服务器只是使存储在浏览器内存中的session cookie失效，不会使服务器端的session对象失效。
SpringMVC
使用DispatcherServlet进行分发，到达合适的controller。每个请求来到dispatcherServlet，disPatcherServlet的<Servlet>和<ServletMapping>，在Servlet中需要一个xml文件，自己创建，里面来配置SpringMVC的属性。
代理设计模式
代理类和委托类有相同的接口，一个代理类的对象与一个委托类的对象关联。
代理类的对象本身并不真正实现服务，而是通过调用委托类的对象的相关方法来提供特定的服务。
JDK动态代理：
反射：proxy类：类的静态方法用来生成动态代理的实例
innovationhandler接口有一个invoke方法用来集中处理动态代理对象方法的调用，通常该方法中实现对委托类的代理访问，每次生成动态代理对象都要指定一个对应的调用处理器。
CGlib动态代理：jdk代理机制只能代理实现了接口的类，而没有实现接口的类不能用jdk动态代理。CGlib是针对类来实现代理，他的原理是对指定的目标类生成一个子类，并覆盖其中方法实现增强，因为采用的是继承，所以不能对final修饰的类进行代理。methodinterceptor
内部类一共有4种
1、成员内部类
2、局部内部类
3、静态内部类
4、匿名内部类：实现一个接口 or 继承一个抽象类。
Java本地方法：该方法的实现是非Java写的，可以用Java调用c或cpp代码，这是出于性能的考虑或者访问底层操作系统。
Java反射：可以在运行时获取类或者对象的相关信息。
一个类可以有一个或者多个静态代码块。静态代码块在类被加载时执行，优于构造函数的执行，并且按照各静态代码块在类种的顺序执行。
Java用Observer接口和Obserable类实现观察者模式
1、创建被观察者类observable类
2、创建观察者类Observer接口
3、对于被观察者，添加他的观察者 void add Observer(Observer o)，该方法把观察者对象添加到观察者列表中，当被观察事件发生时，调用
setchange来设置一个内部标志，注明数据发生了变换。
notifyObservers()：调用观察者对象列表中all Observer的update方法，通知他们数据发生变换，只有在setchange被调用后，notifyObsevers才会调用update
4、对于观察者类，实现Observer接口的唯一方法update
Java接口的修饰符只能是abstract和public
Interator和collection、map无关
JDBC：桥接模式
局部变量没有默认值
Java的序列化算：1、当前类的描述 2、当前类属性的描述 3、父类的描述 4、父类属性的描述 5、父类属性值描述 6、子类属性值描述
类描述是从下到上，类属性描述是从上到下。
Unicode码是2个字节
漏引了某个jar包
单例模式
单例模式饿汉式
public class Singleton{ //静态成员变量 private static Singleton singleton= new Singleton(); //构造函数私有化 private Singleton(){} public static Singleton getInstace(){ return singleton; } }
在类加载时，直接将实例对象初始化，并且该实例是静态的，属于类的成员变量，通过调用类的静态方法返回该对象。
饿汉式是线程安全的，不管系统的哪个线程获取这个对象都是同一个对象，缺点就是在一开始就创建了这个对象，占用内存空间。
懒汉式
1 public class Singleton{ 2 //不初始化 3 private static Singleton singleton = null; 4 private Singleton(){} 5 //调用时才动态实例化 6 public static Singleton getInstance(){ 7 if(singleton == null){ 8 singleton = new Singleton(); 9 } 10 return singleton; 11 } 12 }
懒汉式解决了实例对象初始化占用内存的情况，但是懒汉式存在线程安全的问题，当多个线程同时访问getInstance方法时，有可能在第一个if还没new出来时，第二的线程判断已经进入了if了，则会创建新的实例，单例模式设计失败。
所以就有了双重检测的单例模式
1 public class Singleton{ 2 private volatile static Singleton singleton = null; 3 private Singleton(){} 4 public static Singleton getInstance(){ 5 if(singleton==null){ 6 synchronized(Singleton.class){ 7 if(singleton==null){ 8 singleton = new Singleton(); 9 } 10 } 11 return singleton; 12 } 13 14 } 15 }
创建变量的步骤
1、申请一块内存，调用构造方法初始化
2、返回一个指针指向这个内存
这两个操作，jvm并没有规定谁先谁后。
所以可能返回一个指针指向还没初始化的内容。
枚举实现单例
enum danli{ INSTANCE; }
ArrayList VS Vector（都实现了list接口，都是数组实现）
不安全 安全
扩容50% 扩容100%
ArrayList VS LinkedList
数组 链表
适合检索和在末尾插入或删除 适合在中间插入或删除
另外 LinkedList还实现了queue接口，他还提供peek(),poll(),offer()等方法
hashmap和hashtable底层原理
1、HashMap概述
HashMap是基于哈希表的Map接口的非同步实现。此实现所有可选的映射，并允许使用null值和null键。此类不保证映射的顺序，特别不保证该顺序恒久不变。
2、HashMap的数据结构
HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。
当我们往hashmap中put元素的时候，先根据key的hashcode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么就在这个位置上的元素将以链表的形式存放，新加入的放在链头，先加入的放入链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。
hash(int h)方法根据key的hashcode重新计算一次散列，此算法加入了高位计算，防止低位不变，高位变化时，造成hash冲突。
1 static int hash(int h) { 2 h ^= (h >>> 20) ^ (h >>> 12); 3 return h ^ (h >>> 7) ^ (h >>> 4); 4 }
在HashMap中是这样做的：调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处
1 static int indexFor(int h, int length) { 2 return h & (length-1); 3 }
这个方法非常巧妙就是提过h&（length-1）来得到该对象的保存位，而hashmap底层数组长度总是2的n次方
当length总是 2 的n次方时，h& (length-1)运算等价于对length取模，也就是h%length
HashMap的resize（rehash）
当HashMap的元素越来越多的时候，hash冲突的几率也越来越搞，因为数组的长度是固定的，所以为了提高查询的效率，就要对HashMap进行扩容，数组扩容这个操作就是resize
当HashMap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
Fail-Fast机制
我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么就会抛出ConcurrentModificationException，这就是所谓的fail-fast策略。
这一策略在源码中实现是通过modcount，修改次数。
对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount
在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：
注意到modCount声明为volatile，保证线程之间修改的可见性。
HashTable简介
和hashMap一样，Hashtable也是一个散列表，它存储的内容是键值对（key-value）映射。
Hashtable继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。
hashtable 的函数都是同步的，key，value都不可以为null
1.Hashtable是个线程安全的类（HashMap线程安全）；
2.Hasbtable并不允许值和键为空（null），若为空，会抛空指针（HashMap可以）；
3.Hashtable不允许键重复，若键重复，则新插入的值会覆盖旧值（同HashMap）；
4.Hashtable同样是通过链表法解决冲突；
5.Hashtable根据hashcode计算索引时将hashcode值先与上0x7FFFFFFF,这是为了保证hash值始终为正数;
6.Hashtable的容量为任意正数（最小为1），而HashMap的容量始终为2的n次方。Hashtable默认容量为 11，HashMap默认容量为 16；
7.Hashtable每次扩容，新容量为旧容量的2倍加2，而HashMap为旧容量的2倍；
8.Hashtable和HashMap默认负载因子都为0.75;
八大排序算法
一、直接插入排序
基本思想：
经常碰到这样一类排序问题：把新的数据插入到排好的数据列中。
将第一个数和第二个数排序，然后构成一个有序序列。
将第三个数插入进去，构成一个新的有序序列。
1 public void insertSort(int[] a){ 2 int length=a.length;//数组长度，将这个提取出来是为了提高速度。 3 int insertNum;//要插入的数 4 for(int i=1;i<length;i++){//插入的次数 5 insertNum=a[i];//要插入的数 6 int j=i-1;//已经排序好的序列元素个数 7 while(j>=0&&a[j]>insertNum){//序列从后到前循环，将大于insertNum的数向后移动一格 8 a[j+1]=a[j];//元素移动一格 9 j--; 10 } 11 a[j+1]=insertNum;//将需要插入的数放在要插入的位置。 12 } 13 }
二、希尔排序
基本思想：
对于直接插入排序问题，数据量巨大时。
1、将数的个数设为n，取k=n/2，将下标差值为k的数分为一组，构成有序序列
2、再取k=k/2，将下标差值为k的书分为一组，构成有序序列。
3、重复第二步，直到k=1执行简单插入排序。
1 public void sheelSort(int[] a){ 2 int d = a.length; 3 while (d!=0) { 4 d=d/2; 5 for (int x = 0; x < d; x++) {//分的组数 6 for (int i = x + d; i < a.length; i += d) {//组中的元素，从第二个数开始 7 int j = i - d;//j为有序序列最后一位的位数 8 int temp = a[i];//要插入的元素 9 for (; j >= 0 && temp < a[j]; j -= d) {//从后往前遍历。 10 a[j + d] = a[j];//向后移动d位 11 } 12 a[j + d] = temp; 13 } 14 } 15 } 16 }
三、简单选择排序
基本思想
常用于取序列中最大最小的几个数时。
如果每次比较都交换就是交换排序，如果每次比较完一个循环再交换，就是简单选择排序
1、遍历完整个序列，将最小的数放在前面
2、遍历剩下的序列将最小的放在前面，
3、重复第二步，直到只剩一个数。
1 public void selectSort(int[] a) { 2 int length = a.length; 3 for (int i = 0; i < length; i++) {//循环次数 4 int key = a[i]; 5 int position=i; 6 for (int j = i + 1; j < length; j++) {//选出最小的值和位置 7 if (a[j] < key) { 8 key = a[j]; 9 position = j; 10 } 11 } 12 a[position]=a[i];//交换位置 13 a[i]=key; 14 } 15 }
四、堆排序
堆简单选择排序的优化
1、将序列构建成大顶堆
2、将根节点与最后一个节点交换，然后断开最后一个节点。
3、重复1/2步，直到所有节点断开
1 public void heapSort(int[] a){ 2 System.out.println("开始排序"); 3 int arrayLength=a.length; 4 //循环建堆 5 for(int i=0;i<arrayLength-1;i++){ 6 //建堆 7 buildMaxHeap(a,arrayLength-1-i); 8 //交换堆顶和最后一个元素 9 swap(a,0,arrayLength-1-i); 10 System.out.println(Arrays.toString(a)); 11 } 12 } 13 private void swap(int[] data, int i, int j) { 14 // TODO Auto-generated method stub 15 int tmp=data[i]; 16 data[i]=data[j]; 17 data[j]=tmp; 18 } 19 //对data数组从0到lastIndex建大顶堆 20 private void buildMaxHeap(int[] data, int lastIndex) { 21 // TODO Auto-generated method stub 22 //从lastIndex处节点（最后一个节点）的父节点开始 23 for(int i=(lastIndex-1)/2;i>=0;i--){ 24 //k保存正在判断的节点 25 int k=i; 26 //如果当前k节点的子节点存在 27 while(k*2+1<=lastIndex){ 28 //k节点的左子节点的索引 29 int biggerIndex=2*k+1; 30 //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在 31 if(biggerIndex<lastIndex){ 32 //若果右子节点的值较大 33 if(data[biggerIndex]<data[biggerIndex+1]){ 34 //biggerIndex总是记录较大子节点的索引 35 biggerIndex++; 36 } 37 } 38 //如果k节点的值小于其较大的子节点的值 39 if(data[k]<data[biggerIndex]){ 40 //交换他们 41 swap(data,k,biggerIndex); 42 //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值 43 k=biggerIndex; 44 }else{ 45 break; 46 } 47 } 48 } 49 }
5、冒泡排序
一般不用。
1、将序列中所有元素两两比较，将最大的放在后面。
2、将剩余序列中的所有元素两两比较，将最大的放在最后面。
3、重复第二步，直到只剩下一个数
1 public void bubbleSort(int[] a){ 2 int length=a.length; 3 int temp; 4 for(int i=0;i<a.length;i++){ 5 for(int j=0;j<a.length-i-1;j++){ 6 if(a[j]>a[j+1]){ 7 temp=a[j]; 8 a[j]=a[j+1]; 9 a[j+1]=temp; 10 } 11 } 12 } 13 }
6、快速排序
1、选择第一个数为p，小于p的数放在左边，大于p的数放在右边
2、递归的将p左边和右边的数都按照第一步进行，直到不能递归
1 public static void quickSort(int[] numbers, int start, int end) { 2 if (start < end) { 3 int base = numbers[start]; // 选定的基准值（第一个数值作为基准值） 4 int temp; // 记录临时中间值 5 int i = start, j = end; 6 do { 7 while ((numbers[i] < base) && (i < end)) 8 i++; 9 while ((numbers[j] > base) && (j > start)) 10 j--; 11 if (i <= j) { 12 temp = numbers[i]; 13 numbers[i] = numbers[j]; 14 numbers[j] = temp; 15 i++; 16 j--; 17 } 18 } while (i <= j); 19 if (start < j) 20 quickSort(numbers, start, j); 21 if (end > i) 22 quickSort(numbers, i, end); 23 } 24 }
7、归并排序
速度仅次于快排，内存少的时候使用，可以进行并行计算的时候使用
1、选择相邻两个数组成一个有序序列。
2、选择相邻的两个有序序列组成一个有序序列。
3、重复第二步，直到全部组成一个有序序列。
1 public static void merge(int[] arr,int low,int mid,int high,int[] tmp){ 2 int i = 0; 3 int j = low,k = mid+1; //左边序列和右边序列起始索引 4 while(j <= mid && k <= high){ 5 if(arr[j] < arr[k]){ 6 tmp[i++] = arr[j++]; 7 }else{ 8 tmp[i++] = arr[k++]; 9 } 10 } 11 //若左边序列还有剩余，则将其全部拷贝进tmp[]中 12 while(j <= mid){ 13 tmp[i++] = arr[j++]; 14 } 15 16 while(k <= high){ 17 tmp[i++] = arr[k++]; 18 } 19 20 for(int t=0;t<i;t++){ 21 arr[low+t] = tmp[t]; 22 } 23 } 24 25 public static void mergeSort(int[] arr,int low,int high,int[] tmp){ 26 if(low<high){ 27 int mid = (low+high)/2; 28 mergeSort(arr,low,mid,tmp); //对左边序列进行归并排序 29 mergeSort(arr,mid+1,high,tmp); //对右边序列进行归并排序 30 merge(arr,low,mid,high,tmp); //合并两个有序序列 31 } 32 }
8、基数排序
基本思想
用于大量数，很长的数进行排序
1、将所有的数的个位数取出，按照个位数进行排序，构成一个序列。
2、将新构成的所有数的十位数取出，按照十位数进行排序，构成一个序列。
1 public void sort(int[] array) { 2 //首先确定排序的趟数; 3 int max = array[0]; 4 for (int i = 1; i < array.length; i++) { 5 if (array[i] > max) { 6 max = array[i]; 7 } 8 } 9 int time = 0; 10 //判断位数; 11 while (max > 0) { 12 max /= 10; 13 time++; 14 } 15 //建立10个队列; 16 List<ArrayList> queue = new ArrayList<ArrayList>(); 17 for (int i = 0; i < 10; i++) { 18 ArrayList<Integer> queue1 = new ArrayList<Integer>(); 19 queue.add(queue1); 20 } 21 //进行time次分配和收集; 22 for (int i = 0; i < time; i++) { 23 //分配数组元素; 24 for (int j = 0; j < array.length; j++) { 25 //得到数字的第time+1位数; 26 int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i); 27 ArrayList<Integer> queue2 = queue.get(x); 28 queue2.add(array[j]); 29 queue.set(x, queue2); 30 } 31 int count = 0;//元素计数器; 32 //收集队列元素; 33 for (int k = 0; k < 10; k++) { 34 while (queue.get(k).size() > 0) { 35 ArrayList<Integer> queue3 = queue.get(k); 36 array[count] = queue3.get(0); 37 queue3.remove(0); 38 count++; 39 } 40 } 41 } 42 }
快速排序在无序时效率最高，有序时效率最低。
堆排序、基数排序、归并排序、选择排序的排序次数和初始化状态无关，即最好情况和最坏情况一样。
知道中序且知道前序或后序任何一个就可以确定一颗二叉树。
Integer.parseInt(s,x);
s是需要转换的字符串，x为按什么进制2，10，16，8，默认是10。
16进制的字符串前面有0x
哈希表查找的时间复杂度与原始数量无关，hash表在查找元素时，是通过计算hash值来定位元素，从而直接访问元素。所以hash表的插入、删除、查找都是O(1)。
空间复杂度
归并O（n）
快速O（logn）
其余5种O（1）
观察者模式
1、推模型：传递的信息多，更具体
2、拉模型：目标对象在通知观察者时。只传递少量信息，由观察者主动到目标对象中获取。相当于是观察者从目标对象中拉数据，update方法中传目标对象的引用为拉模型Observer接口
Observable类
用代理模式，代理类可以对他的用户隐藏一个对象的具体信息，因此，使用代理模式的时候，我们常常在一个代理类中创建一个对象的实例。当我们使用装饰器时，我们通常的做法是将一个原始对象作为一个参数传给装饰器构造器。
设计模式
大类分为5种
1、创建型模式：工厂方法、抽象工厂、单例、建造者、原型
2、结构型模式：适配器，桥接，装饰，代理，外观，组合，享元
3、行为型模式：策略、模板方法、责任链、观察者、命令、备忘录、访问者、中介者、解析器、状态、迭代子模式
其实还有两种，并发行模式和线程池模式
工厂方法模式适合，凡是出现了大量的产品需要创建，并且具有公共的接口，可以通过工厂方法模式进行创建，一个工厂里，不同方法创建不同的类。
抽象工厂：工厂方法模式有一个问题就是，类的创建依赖于工厂，也就是说想要扩展程序，必须对工厂类进行修改，用抽象工厂，创建多个工厂类，这样一旦需要增加新的功能，直接增加新的工厂类就可以了，不用改以前的代码，一个工厂生产一个具体对象。
建造者模式，工厂模式提供的是创建单个对象的模式，而建造者模式则是将各种产品集中起来管理，用来创建复合对象。
原型模式，将一个对象作为原型，对其进行复制克隆，产生一个和原对象类似的新对象。
接口的适配器模式：有时我们写的接口种有多个抽象方法，当我们写该接口的实现类时，必须实现该接口的所有方法，但并不是所有方法都是我们必须的，有时候只需要一些，此时我们可以借助于一个抽象类，该抽象类实现该接口，实现所有的方法，我们不和原始接口打交道，只和抽象类联系，所以我们写一个类继承抽象类，重写我们需要的方法就行。
类的适配：当希望将一个类转换为满足另一个接口的类时，创建一个新类，继承原有的类，实现新的接口。
对象的适配，当希望将一个对象转换为满足另一个新接口的对象时，创建一个wrapper类，持有原类实例，在wrapper类的方法种，调用实例的方法。
外观模式facade：为了解决类与类之间的依赖关系，将他们关系放在facade类种。
组合模式：在处理类似树形结构问题时很方便
同步阻塞，用户空间的应用程序执行一个系统调用，这意味着应用程序会一直阻塞，直到系统调用完成为止。
同步非阻塞，设备以非阻塞形式打开，这意味着io操作不会立刻完成，需要应用程序调用多次来等待完成。
同步与异步
同步：发出一个调用时，在没有得到结果前，该调用就不返回，一旦返回就有结果
异步：调用在发出之后就直接返回，所以没有返回结果。换句话说，当一个异步调用发生后，调用者不会立即得到结果，而是在调用发生后，被调用者通过状态通知来通知调用者，或者通过回调函数来处理这个调用。
阻塞和非阻塞
1、阻塞：调用结果返回之前当前线程会挂起，调用线程只有在得到结果之后才会返回
2、非阻塞：不能立刻得到结果之前，该调用就不会阻塞当前线程
BIO ：同步并阻塞，一个连接一个线程，适用于链接数量小且固定的架构。
NIO：同步非阻塞：一个请求一个线程，客户端发送的链接请求都会注册到多路复用器上，多路复用器轮询到链接有io请求时才启动一个线程进行处理，适用于链接比较多比较短。
AIO：异步非阻塞，一个有效请求一个线程，适用于链接数目多且长。
装饰模式：新增行为
代理模式：访问控制
线程池中线程任务就是不多检测任务队列是否有任务并不断执行队列中的任务
TreeMap底层是红黑树
Hashset基于HashMap实现，hashset的元素都放在hashmap的key上面，而value统一为private static final object PERSENT = new Object();允许null值，不允许重
Hashset的add，调用的是hashmap的put
SpringMVC运行原理
1、客户端请求提交到DispatcherServlet
2、由DispatcherServlet控制器查询一个或者多个handlermapping，找到处理请求的controller
3、DispatcherServlet将请求提交给controller
4、controller调用逻辑处理完后，返回methodAndView
5、DispatcherServlet查询一个或多个view Resolver试图解析器，找到modelandview指定的视图。
6、视图负责将结果显示到客户端。
排序：1、内部排序：在内存中进行排序
2、外部排序：因排序数量很大，一次不能容纳所有的排序记录，在排序工程中需要访问外存。
堆对应一颗完全二叉树
对冒泡排序常见的改进方式是加入一个标志变量 exchange，用于标志某一趟排序过程 中是否有数据交换，若进行某一趟排序时并没有数据交换，则说明数据已经按要求排好，可 立即结束排序，避免不必要的比较过程。
不受初始元素影响的排序：选择、堆、归并
应用服务器
1、tomcat：免费支持servlet jsp
2、JBoss：开源应用服务器
3、Weblogic、webSphere：业界第一的appserver
4、apache：最广泛的http服务器但只支持静态网页
验证证书是否有效：
1、验证证书是否在有效期内：证书中会包含证书的有效期的起始时间和结束时间
2、验证证书是否被吊销。被吊销的证书是无效的，验证吊销有两种：CRL和OCSP。
CRL：吊销证书列表，证书被吊销后会被记录在 CRL 中，CA 定期发布 CRL，应用程 序可以依靠 CRL 来验证证书是否被吊销。有两个缺点：1）可能会很大，下载很麻烦。2）有 滞后性，就算证书被吊销了，应用也只能等到发布最新的 CRL 才能知道。OCSP：在线证书 状态检查协议，应用按照标准发送一个请求，对某张证书进行查询，之后服务器返回证书状 态。OCSP 可认为是即时的（实际实现中可能有延迟）。
3、验证证书上是否有上级CA签名：
每一级证书都是由上一级 CA 证书签发的，上级 CA 证书还可能有上级，最后会找到根证书， 根证书即自签证书，自己签自己。以上三点只要有一个没通过，这张证书就是无效的，不该 信任。
满二叉树：除叶子结点外的所有节点均有两个子节点，叶子节点数达到最大，所有叶子 节点都在同一层；完全二叉树：满是完全的特例；哈夫曼树：每个节点要么没子节点点，要 么有两个子节点。
快排改进：1）和插入排序组合，由于快速排序在处理小规模数据时表现不好，因此在 数据规模小到一定程度时，改用插入排序，具体小到何种程度，一般文章说 5-10.（SCISTL 硅谷标准模块采用 10）2）中轴元素（左边比他小，右边比他大），可以取最左边、最右边、 中间这三个位置的元素中的中间值。3）分成三堆，一方面避免相同元素，另一方面降低了 子问题规模（一堆小于一堆等于一堆大于）。