老虎证券社招java工程师面试经验2018.5.11

2018.5.11 老虎证券
问题：
1.如何实现Arraylist的add方法，插入时数组满了怎么办，扩容的话新数组是多大
2.Springmvc的流程
3.JVM内存模型，内存中有什么
4.池有哪些，线程池，数据库连接池，用处
5.Hashcode如何重写

8.Volatile和sychronized的区别
9.工作内存和主内存对应内存模型中哪块
10.Java基础的数据类型和占多少字节
11.搜索树，b+树的应用场景，如何实现的
12.Spring 的IOC为了解决什么问题
13.Hashmap是线程安全的吗？如何实现线程安全
14.ConcurrentHashmap是对什么分段
15.Hashmap的hashcode相同是如何添加数据，为何是用头插法
16.Hashmap在什么时候扩容

19.Spring创建bean和手工创建bean的区别
20.给10万条数据，有重复和不重复的，如何查出前20条
21.排序算法有哪些，说一下堆排序的实现过程
22.new一个包含多个字符串的数组，这句代码执行时，内存的哪些地方有变化
23.将long型的数据转换成int型，如何转换
24.手写单例模式
答案：
1.ArrayList是基于数组实现的，新增元素默认添加到数组的尾部，插入时数组满了会自动扩容，新数组是旧数组的1.5倍。 下面为addd（）方法的源码，其中size指的是数组中存放元素的个数，elementData.length表示数组的长度，当new一个ArrayList系统默认产生一个长度为10的elementData数组，elementData.length=10，但是由于elementData中还未放任何元素所有size=0。如果加入元素后数组大小不够会先进行扩容，每次扩容都将数组大小增大一半，比如数组大小为10一次扩容后的大小为10+5=10;ArrayList的最大长度为 2^32 .

public boolean add(E e) {
   ensureCapacityInternal(size + 1); // 加入元素前检查数组的容量是否足够
   elementData[size++] = e;
   return true;
}
private void ensureCapacityInternal(int minCapacity) {
   modCount++;
// 如果添加元素后大于当前数组的长度，则进行扩容
   if (minCapacity - elementData.length > 0)
     grow(minCapacity);
}
private void grow(int minCapacity) {
   int oldCapacity = elementData.length;
  //将数组的长度增加原来数组的一半。
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;//如果扩充一半后仍然不够，则 newCapacity = minCapacity;minCapacity实际元素的个数。
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
   //数组最大位2^32
  elementData = Arrays.copyOf(elementData, newCapacity);
}

2.SpringMVC流程
1、 用户发送请求至前端控制器DispatcherServlet
2、 DispatcherServlet收到请求调用HandlerMapping处理器映射器。
3、 处理器映射器找到具体的处理器(可以根据xml配置、注解进行查找)，生成处理器对象及处理器拦截器(如果有则生成)一并返回给DispatcherServlet。
4、 DispatcherServlet调用HandlerAdapter处理器适配器。
5、 HandlerAdapter经过适配调用具体的处理器(Controller，也叫后端控制器)。
6、 Controller执行完成返回ModelAndView。
7、 HandlerAdapter将controller执行结果ModelAndView返回给DispatcherServlet。
8、 DispatcherServlet将ModelAndView传给ViewReslover视图解析器。
9、 ViewReslover解析后返回具体View。
10、 DispatcherServlet根据View进行渲染视图（即将模型数据填充至视图中）。
11、 DispatcherServlet响应用户。

3.内存中分为5个部分，其中线程私有的是程序计数器，java虚拟栈，本地方法栈，共享的是堆和方法区。

JVM内存模型总体架构图

程序计数器
多线程时，当线程数超过CPU数量或CPU内核数量，线程之间就要根据时间片轮询抢夺CPU时间资源。因此每个线程有要有一个独立的程序计数器，记录下一条要运行的指令。线程私有的内存区域。如果执行的是JAVA方法，计数器记录正在执行的java字节码地址，如果执行的是native方法，则计数器为空。
虚拟机栈

线程私有的，与线程在同一时间创建。管理JAVA方法执行的内存模型。每个方法执行时都会创建一个桢栈来存储方法的的变量表、操作数栈、动态链接方法、返回值、返回地址等信息。栈的大小决定了方法调用的可达深度（递归多少层次，或嵌套调用多少层其他方法，-Xss参数可以设置虚拟机栈大小）。栈的大小可以是固定的，或者是动态扩展的。如果请求的栈深度大于最大可用深度，则抛出stackOverflowError；如果栈是可动态扩展的，但没有内存空间支持扩展，则抛出OutofMemoryError。使用jclasslib工具可以查看class类文件的结构。下图为栈帧结构图：

本地方法区
和虚拟机栈功能相似，但管理的不是JAVA方法，是本地方法，本地方法是用C实现的。
JAVA堆
线程共享的，存放所有对象实例和数组。垃圾回收的主要区域。可以分为新生代和老年代(tenured)。

新生代用于存放刚创建的对象以及年轻的对象，如果对象一直没有被回收，生存得足够长，老年对象就会被移入老年代。新生代又可进一步细分为eden、survivorSpace0(s0,from space)、survivorSpace1(s1,to space)。刚创建的对象都放入eden,s0和s1都至少经过一次GC并幸存。如果幸存对象经过一定时间仍存在，则进入老年代(tenured)。

方法区
线程共享的，用于存放被虚拟机加载的类的元数据信息：如常量、静态变量、即时编译器编译后的代码。也成为永久代。如果hotspot虚拟机确定一个类的定义信息不会被使用，也会将其回收。回收的基本条件至少有：所有该类的实例被回收，而且装载该类的ClassLoader被回收
4.线程池：在程序启动的时候就创建若干线程来响应处理。池里存放的是工作线程。
作用：一.降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。
二.提高响应速度。当任务到达时，任务可以不需要等到线程创建就能立即执行。
三.提高线程的可管理性。
常用线程池：ExecutorService 是主要的实现类，其中常用的有 : Executors.newSingleThreadPool()
newFixedThreadPool()
new***dTheadPool()
newScheduledThreadPool()
作用：一.资源重用。避免频繁创建，释放连接引起的大量性能开销。它允许应用程序重复使用一个现有的数据库连接，而不是再重新建立一个。
二.缩短系统响应时间。在初始化的过程中，池中已经创建了若干个连接备用。当有请求时，初始化工作已经完成，可直接利用现有的可用连接，减少了创建和释放连接的时间开销。
三.统一管理连接，避免数据库连接遗漏。释放空闲时间超过最大空闲时间的数据库连接来避免因为没有释放数据库连接而引起的数据库连接遗漏。
常见的数据库连接池：Druid，C3P0
5.重写equals()方法的原因：原生的equals()方法比较的是内存地址即obj1==obj2。开发过程中自定义的对象需要业务上的比较。
重写hashCode()的原因：1.若重写了equals()但未重写hashCode(),会违反约定：相等的对象必须要有相同的散列码（hashcode）。
2.对于基于hash实现的类，如HashSet，HashMap，若不重写hashCode()，会导致这些类不能正常使用。原因是：HashMap底层是数组，其下标是传入元素的hashCode和特定值异或决定的。若该数组位置上有值且键值相等，则不处理；若不等则覆盖；若该位置为空，则插入并加入到响应链表中。检查键是否存在也是由hashCode值确定的。当把自定义的对象放在HashMap或HashSet中时，若该对象的某个属性参与了hashCode的计算，则不能更改该属性，否则可能移除不了该元素，导致内存泄漏。
《Effective Java》重写equals()，要遵守的约定：
1、自反性。对于任意的引用值x，x.equals(x)一定为true。
2、对称性。对于任意的引用值x和y，当且仅当y.equals(x)返回true时，x.equals(y)也一定返回true。
3、传递性。对于任意的引用值x、y和z，如果x.equals(y)返回true，并且y.equals(z)也返回true，那么x.equals(z)也一定返回true。
4、一致性。对于任意的引用值x和y，如果用于equals比较的对象没有被修改的话，那么，对此调用x.equals(y)要么一致地返回true，要么一致的返回false。
5、对于任意的非空引用值x，x.equals(null)一定返回false。
《Effective Java》重写hashcode()，要遵守的约定 ：
1.在一个应用程序执行期间，如果一个对象的equals方法做比较所用到的信息没有被修改的话，那么，对该对象调用hashCode方法多次，它必须始终如一地返回 同一个整数。在同一个应用程序的多次执行过程中，这个整数可以不同，即这个应用程序这次执行返回的整数与下一次执行返回的整数可以不一致。
2.如果两个对象根据equals(Object)方法是相等的，那么调用这两个对象中任一个对象的hashCode方法必须产生同样的整数结果。
3.如果两个对象根据equals(Object)方法是不相等的，那么调用这两个对象中任一个对象的hashCode方法，不要求必须产生不同的整数结果。然而，程序员应该意识到这样的事实，对于不相等的对象产生截然不同的整数结果，有可能提高散列表（hash table）的性能。
重写hashCode方法的方式：
a、把某个非零常数值，比如说17（最好是素数），保存在一个叫result的int类型的变量中。
b、对于对象中每一个关键域f（值equals方法中考虑的每一个域），完成一些步骤：
1、为该域计算int类型的散列吗c：
1）如果该域是boolean类型，则计算（f？0:1）。
2）如果该域是byte、char、short或者int类型，则计算（int）f。
3）如果该域是float类型，则计算Float.floatToIntBits(f)。
4）如果该域是long类型，则计算（int）（f ^ (f>>>32)）。
5）如果该域是double类型，则计算Double.doubleToLongBits(f)得到一个long类型的值，然后按照步骤4，对该long型值计算散列值。
6）如果该域是一个对象引用，并且该类的equals方法通过递归调用equals的方式来比较这个域，则同样对这个域递归调用hashCode。如果要求一个更为复杂的比较，则为这个域计算一个“规范表示”，然后针对这个范式表示调用hashCode。如果这个域的值为null，则返回0（或者其他某个常数） 7） 如果该域是一个数组，则把每一个元素当做单独的域来处理。也就是说，递归地应用上述规则，对每个重要的元素计算一个散列码，然后根据步骤下面的做法把这些散列值组合起来。
2、按照下面的公式，把步骤1中计算得到的散列码C组合到result中：
result = 31*result+c。
d、写完hashCode方法之后，问自己“是否相等的实例具有相等的散列码”。如果不是的话，找出原因，并修改。
选择31的原因：31是奇素数。若乘数为偶数且乘法溢出，则信息丢失，因为与2相乘等价于移位运算。使用素数的好处不明显，但习惯上都用素数计算散列值。31的特性是用移位和减法代替乘法，即 31 n =( n << 5 ) - n
给自定义的Student类重写equals()方法和hashCode()方法，其中name为String，age为int，gender为boolean型，代码如下：

//Override注解
 public boolean equals(Object o) {
  if (this == o ) return true;
  if (o == null || getClass() != o.getClass()) return false; 
  Student student = (Student) o;
  if (age != student.age) return false;
  if (gender != student.gender) return false;
  return name != null ? name.equals(student.name) : student.name == null; 
} //Override注解 
public int hashCode() { 
 //name为String类，且String类的源码已经重写过hashCode() 
 int result = name != null ? name.hashCode() : 0;
 result = 31 *result + age;
 result = 31* result + (gender ? 1 : 0); 
 return result; 
}

6.在Java中使用的判断对象存活的算法是可达性分析算法。
判断对象是否存活的方式：
一.引用计数算法： 给对象添加一个引用计数器，当有一个地方引用它时，计数器的值加1；当引用失效时，计数器值减1。任何计数器为0的对象都不可能再被使用。 但主流的java虚拟机并没有使用引用计数算 法来管理内存，原因是它很难解决对象间相互引用的问题。
二.可达性分析算法：通过一系列的称为“GC Roots”的对象作为起始点，从这些节点开始向下搜索，搜索所走过的路径称为引用链，当一个对象到GC Roots没有任何引用链相连（用图论的说法，从GC Roots到这个对象不可达）时，则证明此对象是不可用的。
在java语言中，可作为GC Roots的对象包括以下几种：
1.虚拟机栈（栈帧中的本地变量表）中引用的对象
2.方法区中类的静态属性引用的对象
3.方法区中常量引用的对象
4.本地方法栈中JNI（java的Native方法）引用的对象

一.标记-清除算法。它是最基础的垃圾收集算法。首先要标记需要回收的对象，然后在标记完成后统一回收所有被标记的对象。
不足：1.效率问题，标记和清除两个过程的效率都不高。

2.空间问题，标记清除后产生大量不连续的内存碎片，空间碎片太多可能会导致以后在程序运行过程中需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。

三.标记整理算法。根据老年代的特点，提出了标记整理算法。标记整理和标记清除不同的是，后续步骤不是直接对可回收对象清理，而是让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存。