本文共 7824 字，大约阅读时间需要 26 分钟。

一：ArrayList 和LinkedList ? 两者的查询的时间复杂度？

1ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构 （LinkedList是双向链表，有next也有previous）

2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针

3对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据

4对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。

5 在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的

6LinkedList不支持高效的随机元素访问 但是在ArrayList  支持的高效的随机元素访问

7ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

总结：可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了

二：ArrayList怎么进行扩容  两者的查询的时间复杂度？

ArrayList 怎么进行扩容：通过动态扩容的方式。肯定是在ArrayList.add 方法中

源码：在JDK1.6中

public ArrayList() {      this(10); } public ArrayList(int initialCapacity) {       super();     if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);       this.elementData = new Object[initialCapacity]; }

public boolean add(E e) { //确保内部容量(通过判断，如果够则不进行操作；容量不够就扩容来确保内部容量)     ensureCapacityInternal(size + 1); // ①Increments modCount!!     elementData[size++] = e;//②     return true; }

① ensureCapacityInternal方法名的英文大致是“确保内部容量”，size表示的是执行添加之前的元素个数，并非ArrayList的容量，容量应该是数组elementData的长度。ensureCapacityInternal该方法通过将现有的元素个数数组的容量比较。看如果需要扩容，则扩容。

②是将要添加的元素放置到相应的数组中。

下面具体看 ensureCapacityInternal(size + 1);

// ① 是如何判断和扩容的。private void ensureCapacityInternal(int minCapacity) { //如果实际存储数组 是空数组，则最小需要容量就是默认容量   if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {       minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);   }    ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) {     modCount++; //如果数组（elementData)的长度小于最小需要的容量（minCapacity）就扩容    if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10;

以上，elementData是用来存储实际内容的数组。minExpand 是最小扩充容量。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA共享的空数组实例用于默认大小的空实例。根据传入的最小需要容量minCapacity来和数组的容量长度对比，若minCapactity大于或等于数组容量，则需要进行扩容。

/* *增加容量，以确保它至少能容纳 *由最小容量参数指定的元素数。 * @param mincapacity所需的最小容量 */private void grow(int minCapacity) { // overflow-conscious codeint oldCapacity = elementData.length; //>>位运算，右移动一位。 整体相当于newCapacity =oldCapacity + 0.5 * oldCapacity  // jdk1.7采用位运算比以前的计算方式更快int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //jdk1.7这里增加了对元素个数的最大个数判断,jdk1.7以前是没有最大值判断的，MAX_ARRAY_SIZE 为int最大值减去8（不清楚为什么用这个值做比较）if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 最重要的复制元素方法elementData = Arrays.copyOf(elementData, newCapacity); }

综上所述，ArrayList相当于在没指定initialCapacity时就是会使用延迟分配对象数组空间，当第一次插入元素时才分配10（默认）个对象空间。假如有20个数据需要添加，那么会分别在第一次的时候，将ArrayList的容量变为10 (如下图一)；之后扩容会按照1.5倍增长。也就是当添加第11个数据的时候，Arraylist继续扩容变为10*1.5=15(如下图二)；当添加第16个数据时，继续扩容变为15 * 1.5 =22个(如下图四)。

在JKD1.6中实现是，如果通过无参构造的话，初始数组容量为10，每次通过copeOf的方式扩容后容量为原来的1.5倍，以上就是动态扩容的原理

三：hashMap的底层的数据结构 扩容机制？ 红黑树怎么样装换链表的转换？

从结构实现来讲，HashMap是:数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下如所示。

而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法 。

有序链表转换成二叉树：因为是有序链表，所以可以用分治（递归）的思想，每次折中，中点作为根。

二叉搜索树要转成有序的链表，可以想到的是利用中序遍历二叉树，每得到一个输出结点就修改其指针指向，从而构成有序链表。

HashMap的内部功能实现很多，本文主要从：

1).根据key获取哈希桶数组索引位置：不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能

2).put方法的详细执行：

3).扩容过程：

扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。默认初始容量为16,长度始终保持2的n次方目前最大是2^30

void resize(int newCapacity) { //传入新的容量 2 Entry[] oldTable = table; //引用扩容前的Entry数组 3 int oldCapacity = oldTable.length;  4 if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了 5 threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了 6 return; 7 } 8  9 Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组10 transfer(newTable); //！！将数据转移到新的Entry数组里11 table = newTable; //HashMap的table属性引用新的Entry数组12 threshold = (int)(newCapacity * loadFactor);//修改阈值13 }

这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

四 java的锁体系：说一下公平锁和非公平锁？：

 

五 数据库并发读写出现什么问题：脏读、不可重复读和幻读。两类数据更新问题：第一类丢失更新、第二类丢失更新。

脏读：一个事务读取了另一个事务未提交的数据。

不可重复读：一个事务两次读取同一个数据，两次读取的数据不一致

幻象读：一个事务两次读取一个范围的记录，两次读取的记录数不一致。

更新丢失：一个事务的更新覆盖了另一个事务的更新

六 SQL的锁：

1、 共享锁

用于只读操作(SELECT)，锁定共享的资源。共享锁不会阻止其他用户读，但是阻止其他的用户写和修改。 2、 更新锁 更新锁是一种意图锁，当一个事务已经请求共享琐后并试图请求一个独占锁的时候发生更新琐。例如当两个事务在几行数据行上都使用了共享锁，并同时试图获取独占锁以执行更新操作时，就发生了死锁：都在等待对方释放共享锁而实现独占锁。更新锁的目的是只让一个事务获得更新锁，防止这种情况的发生。 3、 独占锁 一次只能有一个独占锁用在一个资源上，并且阻止其他所有的锁包括共享缩。写是独占锁，可以有效的防止’脏读’。 4、 意图缩 在使用共享锁和独占锁之前，使用意图锁。从表的层次上查看意图锁，以判断事务能否获得共享锁和独占锁，提高了系统的性能，不需从页或者行上检查。 5、 计划锁 Sch-M,Sch-S。对数据库结构改变时用Sch-M，对查询进行编译时用Sch-S。这两种锁不会阻塞任何事务锁，包括独占锁。

七 MySQL中MyISAM与InnoDB区别及选择:

MyISAM存储: 如果表对事务要求不高，同时是以查询和添加为主的，我们考虑使用myisam存储引擎,比如bbs 中的 发帖表，回复表，还有批量添加MyISAM效率高

INNODB 存储: 对事务要求高，保存的数据都是重要数据，我们建议使用INNODB,比如订单表，账号表。

【面试重点】MyISAM 和 INNODB的区别？

1. 事务安全（MyISAM不支持事务，INNODB支持事务）

2. 外键 MyISAM 不支持外键， INNODB支持外键.

3. 锁机制（MyISAM时表锁，innodb是行锁）

4. 查询和添加速度（MyISAM批量插入速度快）

5. 支持全文索引（MyISAM支持全文索引，INNODB不支持全文索引）

6.MyISAM内存空间使用率比InnoDB低

八 找到有序序列中某个值第一次出现的位置，并打印（需要考虑算法复杂度，序列可能很大）

Java反射就是在运行状态中，对于任意一个类，都能够知道这个类的所有属性和方法；对于任意一个对象，都能够调用它的任意方法和属性；并且能改变它的属性。而这也是Java被视为动态。我们知道反射机制允许程序在运行时取得任何一个已知名称的class的内部信息，包括包括其modifiers(修饰符)，fields(属性)，methods(方法)等，并可于运行时改变fields内容或调用methods。那么我们便可以更灵活的编写代码，代码可以在运行时装配，无需在组件之间进行源代码链接，降低代码的耦合度；还有动态代理的实现等等；但是需要注意的是反射使用不当会造成很高的资源消耗！

public class Person { 3     //私有属性 4     private String name = "Tom"; 5     //公有属性 6     public int age = 18; 7     //构造方法 8     public Person() {     9     }10     //私有方法11     private void say(){12         System.out.println("private say()...");13     }14     //公有方法15     public void work(){16         System.out.println("public work()...");17     }18 }//得到 Class 的三种方式//  类型的对象，而我不知道你具体是什么类，用这种方法 3 　　Person p1 = new Person(); 4 　　Class c1 = p1.getClass(); 5          6 //2、直接通过 类名.class 的方式得到,该方法最为安全可靠，程序性能更高 7 //  这说明任何一个类都有一个隐含的静态成员变量 class 8 　　Class c2 = Person.class; 9         10 //3、通过 Class 对象的 forName() 静态方法来获取，用的最多，11 //   但可能抛出 ClassNotFoundException 异常12 　　Class c3 = Class.forName("com.ys.reflex.Person");1 //获得类完整的名字 2 String className = c2.getName(); 3 System.out.println(className);//输出com.ys.reflex.Person 4          5 //获得类的public类型的属性。 6 Field[] fields = c2.getFields(); 7 for(Field field : fields){ 8    System.out.println(field.getName());//age 9 }10         11 //获得类的所有属性。包括私有的12 Field [] allFields = c2.getDeclaredFields();13 for(Field field : allFields){14     System.out.println(field.getName());//name    age15 }16         17 //获得类的public类型的方法。这里包括 Object 类的一些方法18 Method [] methods = c2.getMethods();19 for(Method method : methods){20     System.out.println(method.getName());//work waid equls toString hashCode等21 }22         23 //获得类的所有方法。24 Method [] allMethods = c2.getDeclaredMethods();25 for(Method method : allMethods){26     System.out.println(method.getName());//work say27 }28         29 //获得指定的属性30 Field f1 = c2.getField("age");31 System.out.println(f1);32 //获得指定的私有属性33 Field f2 = c2.getDeclaredField("name");34 //启用和禁用访问安全检查的开关，值为 true，则表示反射的对象在使用时应该取消 java 语言的访问检查；反之不取消35 f2.setAccessible(true);36 System.out.println(f2);37                 38 //创建这个类的一个对象39 Object p2 =  c2.newInstance();40 //将 p2 对象的  f2 属性赋值为 Bob，f2 属性即为 私有属性 name41 f2.set(p2,"Bob");42 //使用反射机制可以打破封装性，导致了java对象的属性不安全。 43 System.out.println(f2.get(p2)); //Bob44         45 //获取构造方法46 Constructor [] constructors = c2.getConstructors();47 for(Constructor constructor : constructors){48     System.out.println(constructor.toString());//public com.ys.reflex.Person()49 }