高频面试题

1. ArrayList的扩容机制

• ArrayList的默认初始化容量是10，底层是使用一个Objcet[]来存放元素，向ArrayList添加元素的时候，先让Size（集合所包含元素个数）+1，如果Size+1大于底层Object[]的长度的话就触发扩容（扩容使得新数组容量是旧数组容量的1.5倍，如果新容量大于Integer.MAX_VALUE-8，就让新容量指向 Integer.MAX_VALUE），最后调用 Arrays.copyOf(elementData, newCapacity)在旧数组的基础上复制出一个以新容量为长度的新数组作为ArrayList的底层数组。

    //默认初始化容量
    private static final int DEFAULT_CAPACITY = 10;

   //添加元素有可能会触发扩容，效率较低
    public boolean add(E e) {
    
        //进行写操作之前让Size+1再检查底层数组容量是否可用,同时modCount++
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;//检查通过后，再添加元素到数组
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
    
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    } 

    private static int calculateCapacity(Object[] elementData, int minCapacity)     {
    
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureExplicitCapacity(int minCapacity) {
    
        modCount++;//该集合被修改得次数加1
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);//如果给定得容量大于底层数组的容量，就进行扩容
    }
    //扩容方法
    private void grow(int minCapacity) {
    
        // overflow-conscious code
        //先拿旧数组容量
        int oldCapacity = elementData.length;
        //在旧容量的基础上扩容百分之50，得到新容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            //计算出来的新容量如果小于给定容量就让新容量指向给定容量
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //如果新容量大于Integer.MAX_VALUE-8，就让新容量指向 Integer.MAX_VALUE
            newCapacity = hugeCapacity(minCapacity); 
        elementData = Arrays.copyOf(elementData, newCapacity);
      }
    

2. 为什么HashMap的加载因子是0.75？

• 加载因子的作用在于判断map是否需要扩容，而扩容是一个比较耗时的操作。

  • 如果加载因子过小，比如 loadFactor=0.5f，初始容量=16的情况下，那么元素超过16*0.5=8个就会扩容到32，假设添加第9个元素成功，那么就会有23个数组位置空闲，空间利用率大概为9/23=39%，因此频繁的扩容不仅耗时而且浪费空间。
  • 如果加载因子过大，比如loadFactor=1.0f，初始容量=16的情况下，那么元素超过16个才会触发扩容，虽然空间利用率大，但是桶中元素的冲突肯定会变多，元素越来越多之后会影响到map的查询时间效率。
  • 总结：loadFactor=0.75f 是空间和时间成本的一种折中（1+0.5）/ 2 = 0.75

• HashMap相关源码分析

3. JDK1.7 HashMap存在的问题以及1.8的优化？

• 1.7存在问题一： HashMap随着数据量的增加会使得哈希表上的链表长度过长，进而导致查询效率降低。

• 1.8优化问题一： 链表长度大于8的时候会被转化成红黑树，以此来提升查询效率，如果链表长度再次小于6会重新变回链表。

  //当单个位置的数据链表长度超过 8 的时候会将该链表转换为红黑树
    static final int TREEIFY_THRESHOLD = 8;
    //当当前位置的红黑树内容长度小于 6 的时候会重新变回链表
    static final int UNTREEIFY_THRESHOLD = 6;
    //当某个位置的链表在转换为红黑树的时候,如果此时数组长度小于 64 会先进行扩容
    static final int MIN_TREEIFY_CAPACITY = 64;

• 1.7存在问题二： 多线程下，扩容使用头插法导致循环链表问题。
  使用头插法的原因：是因为HashMap的编写人员认为新加入的数据更常用，新加入的元素放在前面会更容易查询到。
• 1.8优化问题二： 采用了尾插法防止了环形链表的产生，扩容后节点顺序不会反掉，不存在死循环问题。
• 1.7 单线程 扩容正常转移节点

 oldTable ：  table[0]   a -> b -> c 
 newTable：   table[0]   c -> b -> a
 Entry<K,V> e 
 Entry<K,V> next

​                    e   =  a             e  = b                      e = c

​                    next ->  b          next - > c                  next  -> null 

​                    a.next = null       b.next = a                  c.next = b

​                    newTable[0] =  a    newTable[0]  = b            newTable[0] = c

  链表结果 :         a -> null           b -> a  -> null              c -> b -> a -> null

• 1.7 多线程 扩容异常导致循环链表

// jdk 1.7 扩容时节点转移方法
void transfer(Entry[] newTable) {
    
      Entry[] src = table; 
      int newCapacity = newTable.length;
      for (int j = 0; j < src.length; j++) {
     
          Entry<K,V> e = src[j];           
          if (e != null) {
     // B1： 两个线程都先进入if
              src[j] = null; 
              do {
     
                  Entry<K,V> next = e.next; 
                 int i = indexFor(e.hash, newCapacity);// 设a b c 都落在同一个桶上
                 e.next = newTable[i]; // B2：线程1歇脚点
                 newTable[i] = e;  
                 e = next;             
             } while (e != null);
         }
     }
 }


已有：线程1 + 线程2 并发执行
前提条件：原来的桶中链表元素都 落在 新哈希表的同一桶上
假设2个线程都添加了元素，都触发了扩容机制，然后都构建了自己的Entry[] newTable
    1.两个线程都进入B1，都进了if代码块。
    2.此时线程2放弃了CPU执行权，线程1继续执行
    3.线程1执行到B2（未执行），线程1被挂起
    4.此时线程1： e->a 、next->b
    5.线程2再次获取到CPU执行权，构建新哈希表的某个链表节点newTable[0]
    6.线程2 newTable2[0] -> b -> a 到这个步骤后再次丢失执行权
    7.线程1抢到CPU执行权，继续执行B2步骤代码  
       a.next=null; newTable1[0]=a; e=b;
       再次循环： Entry<K,V> next = b.next; //即 next指向了a
                 b.next = a;  
                 newTable1[0] = b;  
                 e = a;
       再次循环： a.next = newTable1[0] 即  a.next = b       
       到此循环链表形成：b -> a -> b

4. mysql索引的底层数据结构？

数据结构模拟插入

• B+树 在 B树的基础上，为所有的叶子节点加上了链式指针，所有叶子节点形成了一个从小到大的有序的链表，大大加快了区间查找的效率，同时非叶子节点不存储data只做索引作用，所有的叶子的节点都存储了完整的数据行信息。
• B树不管是 叶子节点 还是 非叶子节点 都存储了data，要进行范围查询的话需要进行递归遍历，因此B树的区间查找效率是比较低的。

5. 线程池原理？

线程池总结

6. Spring Bean 的生命周期？

• 1.Spring启动，查找并加载需要被Spring管理的bean，进行Bean的实例化。
• 2.Bean实例化后对将Bean的引用和值注入到Bean的属性中。
• 3.如果Bean实现了BeanNameAware接口的话，Spring将Bean的Id传递给setBeanName()方法。
• 4.如果Bean实现了BeanFactoryAware接口的话，Spring将调用setBeanFactory()方法，将BeanFactory容器实例传入。
• 5.如果Bean实现了ApplicationContextAware接口的话，Spring将调用Bean的setApplicationContext()方法，将bean所在应用上下文引用传入进来。
• 6.如果Bean实现了BeanPostProcessor接口，Spring就将调用他们的postProcessBeforeInitialization()方法。
• 7.如果Bean 实现了InitializingBean接口，Spring将调用他们的afterPropertiesSet()方法。类似的，如果bean使用init-method声明了初始化方法，该方法也会被调用。
• 8.如果Bean 实现了BeanPostProcessor接口，Spring就将调用他们的postProcessAfterInitialization()方法。
• 9.此时Bean已经准备就绪，可以被应用程序使用了。他们将一直驻留在应用上下文中，直到应用上下文被销毁。
• 10.如果bean实现了DisposableBean接口，Spring将调用它的destory()接口方法，同样，如果bean使用了destory-method 声明销毁方法，该方法也会被调用。

7. spring的bean是线程安全的吗？

• 在spring中，并没有提供Bean的线程安全策略，因此spring容器中的bean并不具备线程安全的特性。

• 考虑Spring Bean的线程安全与否要结合Bean的Scope作用域来分析，常见的作用域就是singleton和prototype。

• prototype（多例bean）： 对于prototype中作用域中的bean，因为每次getBean的时候，都会创建一个新的对象，线程之间不存在Bean共享问题，因此prototype作用域下的bean不存在线程安全问题。

• singleton（单例bean）（默认作用域）： 对于singleton作用域中的bean，所有的线程都是共享一个单例实例的bean，因此是存在线程安全问题的，但是如果单例bean是一个无状态的bean，即多线程操作中不会对bean的成员变量进行查询以外的操作（不存在多个线程同时写这个成员变量的场景），那么这个单例bean就是线程安全的。

  • 有状态的bean：就是有实例变量的对象，可以保存数据，是非线程安全的。
  • 无状态的bean：就是没有实例变量的对象，不能保存数据，是线程安全的。

• 解决方案：

  • 1.最简单的解决方案就是将有状态的bean的作用域由singleton改为prototype。
  • 2.在类中定义一个ThreadLocal的成员变量，将需要可变的成员变量保存在ThreadLocal中，采用ThreadLocal解决线程安全问题，为每一个线程提供一个独立的变量副本，不同线程只操作自己线程上的副本变量（推荐）。

8. 怎么理解java面向对象三大特性之一的多态？

• 面向接口编程，方便扩展，方法入参使用接口提高了方法的兼容性。

9. synchronized关键字底层原理是什么？

• synchronized底层原理
• monitor，它内置在每一个对象中，任何一个对象都有一个monitor与之关联，synchronized在JVM里的实现就是基于进入和退出monitor来实现的，底层则是通过成对的MonitorEnter和MonitorExit指令来实现，因此每一个Java对象都有成为Monitor的潜质。所以我们可以理解monitor是一个同步工具。
  • monitorenter，如果当前monitor的进入数为0时，线程就会进入monitor，并且把进入数+1，那么该线程就是monitor的拥有者(owner)。
  • 如果该线程已经是monitor的拥有者，又重新进入，就会把进入数再次+1。也就是可重入的。
  • monitorexit，执行monitorexit的线程必须是monitor的拥有者，指令执行后，monitor的进入数减1，如果减1后进入数为0，则该线程会退出monitor。其他被阻塞的线程就可以尝试去获取monitor的所有权。
  • 使用 javap -v 绝对路径\Test.class 反编译 Test.class 为 jvm指令。

public class Test {
    
    static long count = 0;
    public static final  Object LOCK = new Object();
    public void lock(){
    
        synchronized (LOCK){
    
            count++;
            System.out.println("count = " + count);
        }
    }
}

  public void lock();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=4, locals=3, args_size=1
         0: getstatic     #2                  // Field LOCK:Ljava/lang/Object;
         3: dup
         4: astore_1
         5: monitorenter
         6: getstatic     #3                  // Field count:J
         9: lconst_1
        10: ladd
        11: putstatic     #3                  // Field count:J
        14: getstatic     #4                  // Field java/lang/System.out:Ljava/io/PrintStream;
        17: new           #5                  // class java/lang/StringBuilder
        20: dup
        21: invokespecial #6                  // Method java/lang/StringBuilder."<init>":()V
        24: ldc           #7                  // String count =
        26: invokevirtual #8                  // Method java/lang/StringBuilder.append:(Ljava/lang/
String;)Ljava/lang/StringBuilder;
        29: getstatic     #3                  // Field count:J
        32: invokevirtual #9                  // Method java/lang/StringBuilder.append:(J)Ljava/lan
g/StringBuilder;
        35: invokevirtual #10                 // Method java/lang/StringBuilder.toString:()Ljava/la
ng/String;
        38: invokevirtual #11                 // Method java/io/PrintStream.println:(Ljava/lang/Str
ing;)V
        41: aload_1
        42: monitorexit
        43: goto          51
        46: astore_2
        47: aload_1
        48: monitorexit
        49: aload_2
        50: athrow
        51: return

• monitorexit指令出现了两次，第1次为同步正常退出释放锁；第2次为发生异常退出释放锁；
• synchronized锁的优化
  • JDK1.5之前，synchronized是属于重量级锁，重量级需要依赖于底层操作系统的Mutex Lock实现，然后操作系统需要切换用户态和内核态，这种切换的消耗非常大，所以性能相对来说并不好。
  • JDK1.6之后，开始对synchronized进行优化，增加了自适应的CAS自旋、锁消除、锁粗化、偏向锁、轻量级锁这些优化策略。锁的等级从无锁，偏向锁，轻量级锁，重量级锁逐步升级，并且是单向的，不会出现锁的降级。

10. java的Lock锁的底层原理是什么？

• CAS + AQS