Java面试题总结

一、JavaSE

1 Java基础

1.1 Java和php的区别

• php函数库由c语言编写，而Java核心运行库由Java编写，在运行Java程序时，用户编写的代码和引用的类库都需要在JVM下解释执行。
• PHP内置模板引擎，自身就是一种模板引擎语言；Java Web需要使用JSP容器如Tomcat或第三方模板引擎
• PHP可以直接运行在多线程环境下，开发者不用维护，这些都由PHP-FPM/HHVM/Apache实现；Java需要自己编写代码

1.2 Java和JavaScript的区别

• Java是一种纯面向对象的语言，即使开发再简单的程序，也需要设计对象；JavaScript是一种脚本语言，本身带有非常丰富的内部对象库
• Java源代码执行前必须编译；JavaScript是一种解释性语言，不需要编译，由游览器解释执行
• Java是强类型变量，所有变量必须提前声明；JavaScript是弱类型变量，不需要声明

1.3 &和&&的区别

• &是按位与，&&是逻辑与（短路与）
• &两边的数字时，会将数字转换成二进制数来进行按位与计算；
• &两边是表达式时，两边都会判断是否为真，只有两边都为真整体才为真；&&当左边为假时就会跳出了，不会对右边进行判断，速度更快

System.out.println(12&5); //4
System.out.println(3<4&5>2); //true

|与 || 的是一样的原理

1.4 String 、StringBuffer、StringBulider的区别

• String是字符串常量，是一个被final修饰的不可变对象，StringBuffer 字符串变量（线程安全 Synchronized修饰），StringBuilder 字符串变量（线程不安全）

• 
  上述代码对一个String类型的字符串进行“拼接”会生成三个对象，并不是真正意义上的字符串拼接，效率极其低下

  String s="hello";
  s=s+"world";
  //三个对象："hello" "world" "helloworld"

• StringBuffer 和 StringBuilder 类的对象能够被多次的修改，并且不产生新的未使用对象

• 一般情况下效率： String<StringBuffer<StringBuilder

1.5 值传递和引用传递

• 值传递是对基本型变量而言的,传递的是该变量的一个副本,改变副本不影响原变量
• 引用传递一般是对于对象型变量而言的,传递的是该对象地址的一个副本, 并不是原对象本身 。 所以对引用对象进行操作会同时改变原对象
• 一般认为,java内的传递都是值传递，例如：当一个对象被当作参数传递给一个方法后，此方法可改变这个对象的属性，并可返回变化后的结果，但这也属于值传递

1.6 八大数据类型及拆箱装箱

6种数字类型（4个整数型，2个浮点型），1种字符类型，还有1种布尔型

byte ————-> Byte
short ————-> Short
int ————-> Integer
long ————-> Long
float ————-> Float
double ————-> Double
char ————-> Char
boolean ————-> Boolean

//拆箱，即，把基包装类型转换为基本类型
//装箱，即，基本类型转换为对应的包装类型。
Integer a = 1;  //自动装箱 将int类型的1自动封装为Integer类型 对应：Integer.valueOf(1);

注意：包装类型的比较不要使用==

Integer a=10;Integer b =10;  System.out.println(a==b); //true
Integer a=200;Integer b =200;  System.out.println(a==b); //false

Byte、Short、Integer、Long、Character的定义中都有一个缓存机制，-128~127对应的对象会缓存到缓存中，调用valueOf()方法时，会先判断数据是否在这个范围内，如果在范围内，返回缓存对象，如果超出范围，新建一个对象返回。所以在这个范围内的数值，用==比较会返回true。否则会引起一些间歇性的bug，很难定位。

1.7 Java8新特性

• Lambda 表达式 − Lambda允许把函数作为一个方法的参数（函数作为参数传递进方法中。
• 方法引用− 方法引用提供了非常有用的语法，可以直接引用已有Java类或对象（实例）的方法或构造器。与lambda联合使用，方法引用可以使语言的构造更紧凑简洁，减少冗余代码。
• 默认方法− 默认方法就是一个在接口里面有了一个实现的方法。
• 新工具− 新的编译工具，如：Nashorn引擎 jjs、 类依赖分析器jdeps。
• Stream API −新添加的Stream API（java.util.stream） 把真正的函数式编程风格引入到Java中。
• Date Time API − 加强对日期与时间的处理。
• Optional 类 − Optional 类已经成为 Java 8 类库的一部分，用来解决空指针异常。
• Nashorn, JavaScript 引擎 − Java 8提供了一个新的Nashorn javascript引擎，它允许我们在JVM上运行特定的javascript应用。

1.8 ==与equals的区别

• ==是比较运算符，如果两个数都是基本数值类型，则比较的是他们的值，就算类型不一样，使用 == 比较也相等；如果是引用数据类型，则比较的是内存地址

• equals是Object类中的方法，其最终还是调用的==来进行两个对象的比较，源码如下：

  public boolean equals(Object obj) {
   return (this == obj);
  }

• 但有些对象中对equals方法进行了重写，如String对象中重写了equals方法：

• public boolean equals(Object anObject) {
  if (this == anObject) {
      return true;
  }
  if (anObject instanceof String) {
      String anotherString = (String)anObject;
      int n = value.length;
      if (n == anotherString.value.length) {
          char v1[] = value;
          char v2[] = anotherString.value;
          int i = 0;
          while (n-- != 0) {
              if (v1[i] != v2[i])
                  return false;
              i++;
          }
          return true;
      }
  }
  return false;
  }
  //其实质就是比较值是否相等，不管类型和地址是否相等

double a = 3.0d;
int b = 3;
System.out.println(a == b);        //true
String s1 = "abc";
String s2 = "abc";
String s3 = new String("abc");
System.out.println(s1 == s2);      //true s1与s2的内存地址是同一个字符串，都在常量池中
System.out.println(s1.equals(s2)); //true
System.out.println(s1 == s3);      //false s1与s3的内存地址不一样，一个在常量池一个在堆中
System.out.println(s1.equals(s3)); //true

1.9 为什么重写equals还要重写hashcode

• 使用hashcode方法提前校验，可以避免每一次比对都调用equals方法，提高效率
• 重写equals()必须重写hashCode()，二者参与计算的自身属性字段应该相同；
• equals()相等的两个对象，hashcode()一定相等；反过来：hashcode()不等，一定能推出equals()也不等；
• hashcode()相等，equals()可能相等，也可能不等。

1.10 final关键字

• final修饰类时，这个类不能被继承，并且类中所有的方法都会被隐式的指定为final方法
• final修饰方法时，这个方法会被锁定，不能被修改和重写
• final修饰变量时，如果是基本数据类型，则这个变量的值不会被改变；如果是引用数据类型，则这个变量初始化后不会再指向另一个对象

1.11 volatile关键字

Java volatile关键字最全总结：原理剖析与实例讲解(简单易懂)_夏日清风-CSDN博客_java volatile

• volatile是Java提供的一种轻量级的同步机制，相比于synchronized（synchronized通常称为重量级锁），volatile更轻量级
• 保证可见性，不保证原子性，JMM会强制刷新变量值到主存，但同时也会使其他线程中的缓存失效
• 禁止指令重排
  • ```java 1> 重排序操作不会对存在数据依赖关系的操作进行重排序 比如：a=1;b=a; 这个指令序列，由于第二个操作依赖于第一个操作，所以在编译时和处理器运行时这两个操作不会被重排序。 2> 重排序是为了优化性能，但是不管怎么重排序，单线程下程序的执行结果不能被改变 比如：a=1;b=2;c=a+b这三个操作，第一步（a=1)和第二步(b=2)由于不存在数据依赖关系， 所以可能会发生重排序，但是c=a+b这个操作是不会被重排序的，因为需要保证最终的结果一定是c=a+b=3。

3> 重排序在单线程下一定能保证结果的正确性，但是在多线程环境下，可能发生重排序，影响结果，下例中的1和2由于不存在数据依赖关系，则有可能会被重排序，先执行status=true再执行a=2。而此时线程B会顺利到达4处，而线程A中a=2这个操作还未被执行，所以b=a+1的结果也有可能依然等于2。 public class TestVolatile{ int a = 1; boolean status = false;

//状态切换为true
public void changeStatus{
    a = 2;   //1
    status = true;  //2
}
//若状态为true，则为running
public void run(){
    if(status){   //3
        int b = a + 1;  //4
        System.out.println(b);
    }
}

}

   -  执行到volatile变量时，其前面的所有语句都执行完，后面所有语句都未执行。且前面语句的结果对volatile变量及其后面语句可见 
<a name="c5dd7334"></a>
#### 1.12 单列模式的双重锁为什么要加volatile
```java
public class TestInstance {
    //volatile修饰
    public volatile static TestInstance testInstance;
    public static TestInstance getTestInstance() {
        if (testInstance == null) {
            synchronized (TestInstance.class) {
                if (testInstance == null) {
                    testInstance = new TestInstance();
                }
            }
        }
        return testInstance;
    }
}

在并发多线程下，不使用volatile关键字，在第6行会出现问题。instance = new TestInstance(); 可以分解为3行伪代码：

a. memory = allocate() //分配内存
b. ctorInstanc(memory) //初始化对象
c. instance = memory //设置instance指向刚分配的地址

上面的代码在编译运行时，可能会出现重排从a-b-c排序为a-c-b。 在多线程的情况下当线程A在执行第6行代码时，B线程进来执行到第2行代码。 假设此时A执行第9行代码的过程中发生了指令重排序，即先执行了a和c，没有执行b。 那么由于A线程执行了c导致instance指向了一段地址，此时实例对象是一个未初始化的不为null的对象，当B线程执行到第6行判断instance不为null，会直接跳到第13行并返回一个未初始化的对象。

1.13 构造函数

• 当对象被创建时构造函数就会被调用。每一个类都有一个默认构造函数（无参构造），默认构造函数是没有参数列表的，
• 如果我们没有重载构造函数，那么就会使用默认的构造函数；如果重载了构造函数，那么就不会自动生成无参构造。
• 构造函数重载与方法重载相似，一个类可以有有个重载构造函数，每一个构造函数都有一个唯一的参数列表。
• Java不支持C++的复制构造函数，因为不重载构造函数的情况下，Java不会创建默认的复制构造函数

1.14 方法重载和方法重写

重写：（不同类中）

• 子类对父类允许访问的方法进行重写编写，返回值和参数列表都不能变。
• 访问权限不能比父类中被重写的方法的访问权限更低。例如：如果父类的一个方法被声明为public，那么在子类中重写该方法就不能声明为protected
• 声明为final和static的方法不能被重写；构造方法不能重写
• 重写方法不能抛出新的检查异常或者比被重写方法申明更加宽泛的异常。例如： 父类申明了 IOException，那么在重写这个方法的时候不能抛出 Exception 异常，因为 Exception 是 IOException 的父类，只能抛出 IOException 的子类异常。

重载：（一个类中）

• 每个重载的方法，都有唯一的参数列表
• 返回值可以相同也可以不同，所以无法以返回值类型来区分
• 被重载的方法可以改变访问修饰符，也可以声明更广的异常

方法重载是一个类的多态性表现,而方法重写是子类与父类的一种多态性表现。

public class Test1 {
    public void call() {
        System.out.println("call1");
    }
    //重载 改变了返回值和参数列表
    public int call(int num) {
        System.out.println("call2" + num);
        return num;
    }
}
//子类重写父类方法 只能改变方法主体
class Test2 extends Test1 {
    @Override
    public void call() {
        System.out.println("call2");
    }
}

1.15 反射

• 反射是框架设计的灵魂
• 反射就是把java类中的各种成分映射成一个个的Java对象
• 例如：一个类有：成员变量、方法、构造方法、包等等信息，利用反射技术可以对一个类进行解剖，把个个组成部分映射成一个个对象
• 在运行期间，一个类，只有一个Class对象产生。

获取class对象的三种方式：

public class Test2 {
    public static void main(String[] args) throws ClassNotFoundException {
        //1 实例.getClass()：通过实例化对象获取该实例的 Class 对象
        Test2_User user = new Test2_User();
        Class aClass1 = user.getClass();
        System.out.println(aClass1.getName());
        //2 类名.class：这种获取方式只有在编译前已经声明了该类的类型才能获取到Class对象
        Class aClass2 = Test2_User.class;
        System.out.println(aClass2.getName());
        //3 Class.forName(“类的全限定名”)：通过类的全限定名获取该类的 Class 对象
        Class<?> aClass3 = Class.forName("com.qing.测试.Test2_User");
        System.out.println(aClass3.getName());
    }
}
class Test2_User{
}
//三种方式常用第三种，第一种对象都有了还要反射干什么。第二种需要导入类的包，依赖太强，不导包就抛编译错误。
//一般都第三种，一个字符串可以传入也可写在配置文件中等多种方法。

获取类中所有信息：

//构造方法
Constuctor[] getConstructors()：获取类中所有被public修饰的构造器 Constructor
getConstructor(Class…<?> paramTypes)：根据参数类型获取类中某个构造器，该构造器必须被public修饰
Constructor[] getDeclaredConstructors()：获取类中所有构造器 Constructor
getDeclaredConstructor(class…<?> paramTypes)：根据参数类型获取对应的构造器
//方法
Method[] getMethods()：获取类中被public修饰的所有方法
Method getMethod(String name, Class…<?>
paramTypes)：根据名字和参数类型获取对应方法，该方法必须被public修饰
Method[] getDeclaredMethods()：获取所有方法，但无法获取继承下来的方法
Method getDeclaredMethod(String name, Class…<?>paramTypes)：根据名字和参数类型获取对应方法，无法获取继承下来的方法
//变量
Field[] getFields()：获取类中所有被public修饰的所有变量 
Field getField(Stringname)：根据变量名获取类中的一个变量，该变量必须被public修饰 Field[]
getDeclaredFields()：获取类中所有的变量，但无法获取继承下来的变量 Field
getDeclaredField(String name)：根据姓名获取类中的某个变量，无法获取继承下来的变量

反射创建对象

-1：通过类对象调用newInstance()方法，例如：String.class.newInstance()
-2：通过类对象的getConstructor()或getDeclaredConstructor()方法获得构造器（Constructor）对象并调用其newInstance()方法创建对象，例如：String.class.getConstructor(String.class).newInstance(“Hello”);

反射的应用场景：

• Spring 实例化对象：当程序启动时，Spring 会读取配置文件applicationContext.xml并解析出里面所有的标签实例化到IOC容器中。
• 反射 + 工厂模式：通过反射消除工厂中的多个分支，如果需要生产新的类，无需关注工厂类，工厂类可以应对各种新增的类，反射可以使得程序更加健
• JDBC连接数据库：使用JDBC连接数据库时，指定连接数据库的驱动类时用到反射加载驱动类

1.16 Static Nested Class 和 Inner Class

Nested Class （一般是C++的说法），Inner Class (一般是JAVA的说法)。

• Inner Class（内部类）定义在类中的类， 它的创建依赖一个外部类对象作为宿主，内部类必须寄生在外部类对象中才能创建实例
• 静态内部类（嵌套类）：这个类没有必要单独存放一个文件，它一般只被外部类使用，可以直接用 “外部类名+内部类名” 获得，跟随类的加载而产生
• 静态内部类中不能访问外部类的非静态成员, 因为静态方法不能直接访问非静态成员

1.17 abstract class和interface

1. 抽象类可以有构造方法，接口不能有构造方法
2. 抽象类中可以有普通成员变量，接口中没有普通成员变量
3. 抽象类中可以包含非抽象的普通方法，接口中的所有方法必须是抽象的，不能有非抽象的普通方法
4. 抽象类中抽象方法的访问类型可以是public，protected，但接口中的抽象方法只能是public类型，并且默认即为public abstract类型
5. 抽象类中可以包含静态方法和私有方法；接口中不能包含静态方法和私有方法，jdk1.8后静态方法必须有方法体
6. 抽象类和接口中都可以包含静态成员变量，抽象类中的静态成员变量的访问类型可以任意，但接口中定义的变量只能是public static final类型，并且默认即为public static final类型
7. 一个类可以实现多个接口，但只能继承一个抽象类

//抽象类
abstract class MyClass2 {
    private int a;
    int b;
    //默认构造方法
    public MyClass2() {
    }
    //自定义构造方法
    public MyClass2(int a, int b) {
        this.a = a;
        this.b = b;
    }
    //抽象方法 子类必须重写
    abstract void m1();
    //私有方法
    private void m2() {
        System.out.println("m2");
    }
}
class MyClass3 extends MyClass2 {
    //子类重写父类的抽象方法
    @Override
    void m1() {}
}
//接口
interface A {
    //默认修饰public static final可省略 必须初始化
    public static final int a = 0;
    //默认修饰public abstract可省略 实现类必须实现该方法
    public abstract void m3();
}
class MyClass1 implements A {
    //子类必须实现接口的所有方法
    @Override
    public void m3() {
        System.out.println(A.a);
    }
}

1.18 Comparable和Comparator

源码比较：

Comparable：

接口只有一个方法compare,比较次对象与指定对象的顺序，如果该对象小于，等于或大于指定对象，则分别返回负整数，零或正整数。

实现Comparable接口，重写compareTo方法；数组使用 Arrays.sort(user)，集合使用Collections.sort(list)

public class Test4 {
    public static void main(String[] args) {
        User[] user = new User[]{new User("qing", 50), new User("fan", 25)};
        //直接调用sort函数
        Arrays.sort(user);
        System.out.println(Arrays.toString(user));
    }
}
class User implements Comparable<User> {
    private String name;
    private int age;
    //set 、get、toString略
    @Override
    public int compareTo(User o) {
        //从小到大排序
        return this.age - o.age;
    }
}

Comparator：

该类本身不支持排序（即没有实现Comparable接口），那么我们就可以建立一个“该类的比较器”来进行排序

Comparator中的equals方法可以不实现，也可以实现。equals方法因为是Object类中的，是每个类都与生俱来的方法。

public class Test4 {
    public static void main(String[] args) {
        User[] user = new User[]{new User("qing", 50), new User("fan", 25)};
        //new了一个比较器
        Arrays.sort(user, new Comparator<User>() {
            @Override
            public int compare(User o1, User o2) {
                return o1.getAge() - o2.getAge();
            }
        });
        System.out.println(Arrays.toString(user));
    }
}
//user类没有实现Comparable接口
class User {
    private String name;
    private int age;
}

1.19 object方法

clone() ：用来另存一个当前存在的对象（复制对象、浅拷贝）
hashCode()：用于获取对象的哈希值，这个值的作用是检索
equale()：用于确认两个对象是否相同
toString()
getClass()
wait()：用于让当前线程失去操作权限，当前线程进入等待序列
wait(long)：设置线程等待时间
wait(long,int)
notify()：用于随机通知一个持有对象的锁的线程获取操作权限
notifyAll()：用于通知所有持有对象的锁的线程获取操作权限
finalize()：垃圾回收器准备释放内存的时候，会先调用finalize()

1.20 Clone()方法

复制对象和复制引用：

Person p = new Person(23, "zhang"); 
Person p1 = p; 
System.out.println(p); 
System.out.println(p1); 
/*打印：
com.qing.测试.User1@1b6d3586
com.qing.测试.User1@1b6d3586
*/
//可以看出，打印的地址值是相同的，既然地址都是相同的，那么肯定是同一个对象。p和p1只是引用而已，他们都指向了一个相同的对象Person(23, "zhang"，可以把这种现象叫做复制引用
Person p = new Person(23, "zhang"); 
Person p1 = (Person) p.clone(); 
System.out.println(p); 
System.out.println(p1); 
/*打印：
com.qing.测试.User1@1b6d3586
com.qing.测试.User1@4554617c
*/
//从打印结果可以看出，两个对象的地址是不同的，也就是说创建了新的对象， 而不是把原对象的地址赋给了一个新的引用变量

浅拷贝和深拷贝：

• 对于基本数据类型，都是浅拷贝，直接将值复制就行
• 对于引用数据类型：
  • 浅拷贝：拷贝对象的引用值，拷贝的对象和原对象还是属于一个对象，使用==比较为true，clone()就是浅拷贝
  • 深拷贝：新建一个对象，将原对象的值复制给新对象，两个对象的地址值不同，，使用==比较为false

总结：Clone方法是复制对象，克隆产生的对象与原对象的地址不同，属于两个不同的对象；但是Clone方法又是浅拷贝，对于对象中的引用数据类型，其地址值又是一样的，使用==判断为true，所以会出现对象的每个数据地址值都相等，但对象地址值不等的情况！

User1 user1 = new User1("q", 15);
User1 user2= (User1) user1.clone();
System.out.println(user1); //com.qing.测试.User1@1b6d3586
System.out.println(user2); //com.qing.测试.User1@4554617c 
System.out.println(user1.getName()==user2.getName()); //true

1.21 ArrayList、LinkedList、Vector

• ArrayList和Vector基于数组实现，顺序存储，初始容量都是10；LinkedList基于双向链表实现
• ArrayList和LinkedList是线程不安全的，如果想要并发调用，则可以使用Collections类中的静态方法synchronizedList(）；Vector实现线程安全的，它大部分的方法都包含关键字synchronized

 List<Object> list = Collections.synchronizedList(new ArrayList<>(Arrays.asList(1,2,3)));

• ArrayList扩容后的容量是之前的1.5倍，且不可以自定义增量；Vector默认情况下扩容后的容量是之前的2倍，可以自定义增量
• ArrayList和Vector插入、删除的时间复杂度为O(n)，查找时间复杂度为O(1)；LinkedList 插入、删除为O(1)，查找为O(n)

1.22 HashMap和Hashtable

• 底层数据结构不同:jdk1.7底层都是数组+链表,但jdk1.8 HashMap加入了红黑树
• Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。
• 添加key-value的hash值算法不同：HashMap添加元素时，是使用自定义的哈希算法；而HashTable是直接采用key的hashCode()
• 实现方式不同：Hashtable 继承的是 Dictionary类，而 HashMap 继承的是 AbstractMap 类。
• 初始化容量不同：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。
• 扩容机制不同：当已用容量>总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 +1。
• 支持的遍历种类不同：HashMap只支持Iterator遍历,而HashTable支持Iterator和Enumeration两种方式遍历
• 迭代器不同：HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，而Hashtable 则不会。
• 部分API不同：HashMap不支持contains(Object value)方法，没有重写toString()方法,而HashTable支持contains(Object value)方法，而且重写了toString()方法
• 同步性不同: Hashtable是同步(synchronized)的，适用于多线程环境；而hashmap不是同步的，适用于单线程环境。

1.23 快速失败(fail-fast)和安全失败(fail-safe)

• 快速失败：在迭代一个集合的时候，如果有另一个线程正在修改正在访问的那个集合时，就会抛出一个 ConcurrentModification异常。java.util包下的都是快速失败。
• 安全失败：迭代的时会去底层集合做一个拷贝，所以在修改上层集合的时候是不会受影响的，不会抛出 ConcurrentModification异常。java.util.concurrent包下的全是安全失败的。
• 迭代器本身的remove()方法不会抛出ConcurrentModificationException异常，集合本身的remove()则不行。但这并不是一个一定发生的行为，要看JVM
• 快速失败原理：在迭代器访问集合时，会设置一个modCount变量。迭代器每次使用hasNext/next遍历集合都会检测modCount是否等于expectedmodCount。当集合中的内容被修改时就会改变modCount的值，导致 modCount！=expectedmodCount ，则会抛出异常。但是当修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出，所以不能依赖于这个异常是否抛出而进行并发操作的编程
• 安全失败原理：因为迭代时会对原数据进行拷贝，所有对数据的修改操作都在拷贝的数据上进行，不会修改原数据，自然就不会检测到modCount值改变。但迭代器拿不到新修改的数据，只能对原始数据进行遍历。

1.24 Iterator和ListIterator

• Iterator是所有Collection集合都可以使用的；ListIterator只能对List类的集合使用
• Iterator只支持hasNext()、next()、remove()，只支持前向遍历；ListIterator继承了Iterator，在原有的基础上进行方法扩展，支持前向遍历和后向遍历

//ListIterator接口
public interface ListIterator<E> extends Iterator<E> {
    //继承自Iterator的接口
    boolean hasNext();         //后面是否有元素
    E next();                  //游标向后移动，取得后面的元素
    void remove();             //删除最后一个返回的元素
    //ListIterator新增的接口
    boolean hasPrevious();     //前面是否有元素
    E previous();              //游标往前移动，取得前面的元素
    int previousIndex();       //取得游标前的index
    int nextIndex();           //取得游标后的index
    void set(E e);             //将当前元素改设成e
    void add(E e);             //增加一个元素
}

扩展：

• 通常只有在使用LinkedList时才会搭配ListIterator
• 因为LinkedList几乎所有的时间消耗都是在去找到这个元素在哪，查找时间复杂度为O(N)，而找到此元素之后，对他进行修改是非常容易的事情(只要改指针就可以了)，所以使用ListIterator的话，就可以节省下这个查找时间
• 而对ArrayList来说，查找时O(1)，因此使用ListIterator省下的查找时间非常少，所以对他来说，并没有迫切的需要使用ListIterator

1.25 ConcurrentHashMap

0 1.7和1.8的区别

• 数据结构：取消了segment分段锁，采用数组+链表+红黑树
• 安全机制：1.7 采用 Segment 的分段锁机制实现线程安全，其中 Segment 继承自 ReentrantLock，对每个数据操作都会上锁；1.8 采用CAS+synchronized保证线程安全，只对Node数组上锁。
• 1.8中链表转为红黑树，可以降低hash冲突概率，降低查找时间复杂度

1 实现原理

1.7中由segment+hashEntry结构组成，即ConcurrentHashMap将哈希桶数组分为了一个个segment小数组，每个segment数组又由多个HashEntry组成

如下图：首先将数据分为一段一段的存储，然后给每一段数据配一把锁（可重入锁ReentrantLock），当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现了真正的并发访问。。Segment 默认为16，也就是并发度为 16。

1.8中改为了和HashMap一样的数据结构：Node数组+链表+红黑树，在锁的实现上，抛弃了原有的 Segment 分段锁，采用CAS + synchronized实现更加细粒度的锁（内置锁 synchronized）。将锁的粒度缩小到了桶数组上，只需要对每个桶数组元素（链表的头结点）上锁就行，如下图：

1.7中的可重入锁会继承AQS锁来获得同步支持，但不是每个节点都需要同步支持，所以1.7效率很低，内存开销大

1.8中的synchronized锁引入了大量的优化，有多重锁状态，会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。

2 get原理

1.7：

• 首先根据key计算出hash值，再根据hash值定位到具体的hashEntry对象，进行链表遍历，找到具体元素。
• 由于hashEntry的对象都是有volatile修饰，保证了并发可见性，所以每次拿到的值都是最新值

1.8：

• 根据key计算hash值，判断数组是否为空
• 首节点直接返回
• 判断是否是红黑树，采用链表遍历或红黑树遍历

1.8源码：

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    //获取hash值
    int h = spread(key.hashCode());
    //判断数组是否为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        //判断是否是链表首节点
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //红黑树遍历
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        //链表遍历
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

3 put原理

1.8：

• 根据key计算hash
• 判断是否需要初始化
• 定位到Node数组节点，判断：
  • 如果为null，则进行CAS方式添加
  • 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容
  • 如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入
• 链表长度为8时，数组扩容或链表转为红黑树

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    //计算hash
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        //是否需要初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //当前链表为空则直接CAS添加
            if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        //f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            //synchronized锁，进行链表插入或红黑树插入
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    //链表遍历
                    if (fh >= 0) {    
                       //...
                    }
                    //红黑树遍历
                    else if (f instanceof TreeBin) {
                       //...
                    }
                }
            }
            if (binCount != 0) {
                //链表长度大于8时转为红黑树
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

4 迭代弱一致性

与 HashMap 迭代器是强一致性不同，ConcurrentHashMap 迭代器是弱一致性。

ConcurrentHashMap 的迭代器创建后，就会按照哈希表结构遍历每个元素，但在遍历过程中，内部元素可能会发生变化，如果变化发生在已遍历过的部分，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器就会发现并反映出来，这就是弱一致性。

这样迭代器线程可以使用原来老的数据，而写线程也可以并发的完成改变，更重要的，这保证了多个线程并发执行的连续性和扩展性，是性能提升的关键。

1.26 HashMap

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始化容量16
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量 2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f; //初始化阈值
static final int TREEIFY_THRESHOLD = 8; //初始化树化阈值 8
static final int UNTREEIFY_THRESHOLD = 6; //初始化链化阈值 6
static final int MIN_TREEIFY_CAPACITY = 64; //初始化数组树化阈值 64

1 数据结构

JDK1.7：数组+链表

JDK1.8：数组+链表+红黑树，如下图：

2 为什么选择红黑树

红黑数本质是一种二叉平衡树，为了保持平衡，新增规则：

• 根节点为黑色，节点要么是红色要么是黑色
• 每个叶节点（null节点）永远是黑色
• 红色节点的两个子节点一定是黑色
• 从任何一个节点开始到任意一个叶子节点，所经过的黑色节点数一定相等

不用二叉树是因为二叉树最坏时间复杂度是O（n），而红黑数插入、删除、查找的时间复杂度都是O（logn）

不用二叉平衡树是因为二叉平衡树比红黑数更严格，为保持平衡所旋转次数也更多，效率更低

3 put流程

• 首先进行哈希值的扰动，获取一个新的哈希值
• 判断tab数组是够为空或长度为0，如果是则需要扩容
• 根据哈希值计算下标，如果对应下标存有元素则直接覆盖，若没有则直接插入
• 插入时判断tab【i】是够是树节点，若是则进行树插入，否则进行链表插入
• 链表插入时遍历链表判断是否有key相等，若有则覆盖，没有则进行尾插
• 尾插时结束后判断链表是否需要树化，链表长度大于8，tab数组长度大于64则进行树化
• 成功插入元素后判断tab数组是否达到阈值，达到则需扩容

4 hash扰动函数

哈希函数是先获得key的hashcode值，让高16位与低16位进行异或运算，降低hash碰撞概率

static final int hash(Object key) {
    int h;
    // key的hashCode和key的hashCode右移16位做异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

int 值范围为 -2147483648~2147483647，加起来大概 40 亿的映射空间。一个 40 亿长度的数组，内存是放不下的， HashMap 数组的初始大小才 16，所以就需要用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标，源码使用位运算来代替取模运算。

计算下标：

bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {
     return h & (length-1);
}

（数组长度 - 1）正好相当于一个 “低位掩码”，与 操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度 16 为例，16-1=15。2 进制表示是 0000 0000 0000 0000 0000 0000 0000 1111。和某个散列值做 与 操作如下，结果就是截取了最低的四位值。

扰动函数示意图：

新hash值的计算使用的是高16位与低16位进行异或运算，这种方式成功保留了高位的相，增大了hash散列分部的随机性，这让新hash值与（n-1）进行 与 运算时，hash冲突的概率大大降低。

5 为什么容量是2的倍数

1》 方便hash取余

计算下标时使用的是（n-1）&hash，数组容量是2的倍数，那么转成二进制最高位一定是1，低位全是0。在进行减一操作后，所有0 1互换。如

16:      1 0 0 0 0
16-1=15: 0 1 1 1 1
32：      1 0 0 0 0 0
32-1=31： 0 1 1 1 1 1
64:       1 0 0 0 0 0 0
64-1=63： 0 1 1 1 1 1 1

这样在使用&运算时，能有效的降低hash冲突概率，增大散列分布

2》 方便扩容

HashMap中的元素在超过负载因子HashMap大小时就会产生扩容，初始化时16 0.75=12，数组容量会翻倍，扩容后的容量也是2的倍数

6 初始化传一个17的值会怎么处理

当初始化map时，传的容量不是2的倍数，那么HashMap会向上寻找最小的2的幂次的数。传入17会找到32；传入35会找到64

源码如下：

public HashMap(int initialCapacity, float loadFactor) {
 ...
 this.loadFactor = loadFactor;
 this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
 int n = cap - 1;
 n |= n >>> 1;
 n |= n >>> 2;
 n |= n >>> 4;
 n |= n >>> 8;
 n |= n >>> 16;
 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 
}

以17位例子：

7 解决hash冲突的方法

• 链地址法：在冲突的位置拉一个链表，把冲突的元素放进去。
• 开放地址法：开放定址法就是从冲突的位置再接着往下找，给冲突元素找个空位。找到空闲位置的方法也有很多种：线行探查法: 从冲突的位置开始，依次判断下一个位置是否空闲，直至找到空闲位置；平方探查法: 从冲突的位置x开始，第一次增加1^2 个位置，第二次增加2^2…，直至找到空闲的位置
• 再hash法：换种哈希函数，重新计算冲突元素的地址
• 建立公共溢出区：换种哈希函数，重新计算冲突元素的地址

8 为什么树化阈值是8

红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树，牺牲了空间换时间，更多的是一种兜底的策略，保证极端情况下的查找效率。

阈值为什么要选8呢：和统计学有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为8的情况，发生概率仅为0.00000006。

红黑树转回链表的阈值为什么是6，而不是8：是因为如果这个阈值也设置成8，假如发生碰撞，节点增减刚好在8附近，会发生链表和红黑树的不断转换，导致资源浪费。

9 为什么扩容因子是0.75

出于对空间成本和时间成本平衡的考虑

如果扩容因子太大，那么空位就会更少，hash冲突的概率就会增大，查找时间成本也会增大

如果扩容因子太小，空位很多时就扩容，会造成空间浪费

10 扩容机制

因为HashMap初始长度是2的幂，扩容也是增加2的幂次，所以扩容后新的元素位置要么不变，要被也增加2的幂次

下图n为table的长度，图a表示扩容前的key1和key2两种key确定索引的位置，图b表示扩容后key1和key2两种key确定索引位置。

11 Jdk1.8的优化

• 数据结构：数组+链表改位了数组+链表+红黑树，发生hash冲突时插入链表，时间复杂度由O（n）转为O（logn）
• 链表插入方式：1.7将新元素放入数组中，采用头插形式；1.8后使用链表尾插，避免了1.7头插时链表反转或形成环的情况
• 扩容：1.7对所有元素进行重新hash定位，且是插入前扩容；1.8新位置要么不变，要么是变为原位置+扩容大小，且插入后再扩容
• 散列函数：1.7 做了四次移位和四次异或，jdk1.8只做一次。原因：做 4 次的话，边际效用也不大，改为一次，提升效率

12 是否线程安全

HashMap不是线程安全的，可能会发生这些问题：

• 多线程下扩容死循环：1.7使用头插法，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
• 多线程的 put 可能导致元素的丢失：多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。
• put 和 get 并发时，可能导致 get 为 null：线程 1 执行 put 时，因为元素个数超出 threshold 而导致 rehash，线程 2 此时执行 get，有可能导致这个问题。这个问题在 JDK 1.7 和 JDK 1.8 中都存在。

解决线程不安全办法：

• 使用HashTable ，所有操作都有synchronized关键字修饰，但粒度大
• Collections 集合工具的内部类Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现
• 使用ConcurrentHashMap

13 1.7的死循环

put流程：

//添加元素方法 -> 添加新节点方法 -> 扩容方法 -> 把原数组元素重新分配到新数组中
put()  --> addEntry()  --> resize() -->  transfer()
问题就发生在 transfer 这个方法中

假设，原数组容量只有2，其中一条链表上有两个元素 A,B，如下图：

现在，有两个线程都执行 transfer 方法，每个线程都会生成一个newTable数组，但两个数组中的数据都是同一份，即操作table1中的元素会改变table2中的元素

1》 假设线程一执行到了上图1中所指的代码①处，恰好 CPU 时间片到了，线程被挂起，不能继续执行了。 记住此时，线程一中记录的 e = A ， e.next = B。

2》 然后线程二正常执行，扩容后的数组长度为 4， 假设 A，B两个元素又碰撞到了同一个桶中。然后，通过循环后，采用头插法，最终呈现的结构如下：

此时e=B，e.next=A，线程一不知道这个变化

3》此时，线程一解挂，继续往下执行。注意，此时线程一，记录的还是 e = A，e.next = B，因为它还未感知到最新的变化。

线程一进行第二次头插后链表关系变为：

4》当线程一第二次循环时，发现了线程二修改带来的变化，原本B.next=null，该结束循环，但是此时B.next=A，还会继续循环，所以就会出现A->B->A的情况。

当使用get方法时，就会因为e不为空，造成死循环

2 设计模式

2 设计模式

2.1 面向对象的六原则+一法则

3 JVM

1 类加载机制

2 双亲委派机制

4 多线程

5 并发+锁

二、JavaEE

1 MySQL

2 Spring

3 SpringBoot

4 SpringCloud

5 redis

6 Mybatis

三、专业课

1 计网

2 操作系统

3 数据结构