JAVA基础面试题

二分查找

比较次数

奇数取中间
偶数取中间靠左

对于数量庞大，可以采取

2的次方

log n / log 2

如果求出是小数，则整数加1

---

冒泡排序

文字描述

1. 依次比较数组中相邻两个元素大小，若a[i] > a[j+1},则交换两个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排在最后
2. 重复以上步骤，直到整个数组有序

优化方式：

每轮冒泡时,最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序，直接退出外层循环即可。

上代码

public class Bubbling {
public static void main(String[] args) {
//int[] arr = {2,3,4,1,10,8,5};
    int[] arr = {3,2,3,4,5};
    bubbling(arr);


}

private static void bubbling(int[] arr) {

    for(int i = 0; i < arr.length - 1; i++) {
        boolean isSwap = false; //判断是否交换位置，如果没有则结束
        for(int j = 0; j < arr.length - 1 - i; j++) {
            System.out.println("比较次数"+j+1);
            if(arr[j] > arr[j+1]) {
                swap(arr,j,j+1);
                isSwap = true;
            }
        }
        System.out.println("第"+i+"轮"+ Arrays.toString(arr));
        if(!isSwap) {
            break;
        }
    }

}

private static void swap(int[] arr, int j, int i) {
    int temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;


  }
}

更优方法

    private static void bubbling2(int[] arr) {
    int n = arr.length - 1;//比较的次数
    while(true){
        int last = 0; //最后一次交换的索引
        for(int j = 0; j < n; j++) {
            System.out.println("比较次数"+(j+1));
            if(arr[j] > arr[j+1]) {
                swap(arr,j,j+1);
                last = j;
            }
        }
        System.out.println("第轮"+ Arrays.toString(arr));
        n = last;
        if(n == 0) {
            break;
        }

    }
}

选择排序

文字排序

1. 将数组分成两个子集，排序的和未排序的，每一轮从未排序的子集中选出最小的元素，放入排序子集。
2. 重复以上步骤，直到整个数组有序

选择排序与冒泡排序对比

1. 选择排序不稳定，冒泡排序稳定
2. 数组有序情况下，冒泡比选择快
3. 一般情况下，选择排序比冒泡排序快，因为选择排序交换次数少

插入排序

文字描述

1. 将数组分为两个区域，排序区域和未排序区域，每一轮从未排序区域中取出第一个元素，插入到排序区域（需保证顺序)
2. 重复以上步骤，直到整个数组有序

与选择排序比较

1. 大部分情况下，插入都略优于选择

2. 插入属于稳定排序算法，而选择属于不稳定排序

上代码

 public class Insert {
public static void main(String[] args) {
    int[] arr = {2,3,4,1,10,8,5};
    insert(arr);
    System.out.println(Arrays.toString(arr));
}

private static void insert(int[] arr) {
    for(int i = 1; i < arr.length; i++) {
        int t = arr[i];
        int j = i - 1;
        while(j >= 0) {
            if(t < arr[j]) {
                arr[j+1] = arr[j];
            }else {
                break;
            }
            j--;
        }
        arr[j+1] = t;
    }

 }
}

快速排序

1. 每一轮排序选择一个基准点进行分区
   1. 让小于基准点的元素的进入一个分区，大于基准点的元素的进入另一个分区
   2. 当分区完成时，基准点元素的位置就是其最终位置
2. 在子分区内重复以上过程，直到子分区元素个数小于等于1，这就是分而治之的思想（divide-and-conquer）

单边循环快排

1. 选择最右元素作为基准点元素

2. j指针负责找到比基准点小的元素，一旦找到则与i进行交换

3. i指针维护小于基准点元素的边界，也是每次交换的目标索引

4. 最后基准点与i交换，i即为分区位置

   上代码

   public class Quick {
   public static void main(String[] args) {
   int[] arr = {2,3,4,1,10,8,5};
   // partion(arr,0,arr.length - 1);
   quick(arr,0,arr.length - 1);
   }

   private static void quick(int[] arr, int l, int r) {
   if(l >= r) {
   return;
   }
   //索引值
   int index = partion(arr,l,r);
   quick(arr,l,index-1);
   quick(arr,index+1,r);
   }

    /**
     * 找出最终基准点的索引
     * @param arr
     * @param l
     * @param r
     * @return
     */
   

   private static int partion(int[] arr, int l, int r) {
   //找最右边作为基准点
   int pv = arr[r];
   int i = l;
   int j = i;
   
   for( ; j < r; j++) {
   //找到比基准点小于的值
   if(arr[j] < pv) {
   //与i进行交换
   if(i != j) {
   swap(arr, i, j);
   }
   i++;
   }
   }
   if(i != r) {
   swap(arr,i,r);
   }
   
   System.out.println(Arrays.toString(arr)+i);
   
   return i;
   }

   private static void swap(int[] arr, int j, int i) {
   int temp = arr[j];
   arr[j] = arr[i];
   arr[i] = temp;
   }
   }

双边循环

1. 选择左边作为基准点
2. i从左到右查询比基准点大的值，j从右到左查询比基准点小的值，直到i和j相交
3. 最后基准点与i交换

上核心代码

private static int partion1(int[] arr, int l, int r) {
    int pv = arr[l];
    int i = l;
    int j = r;
    while(i < j) {
        //先从右到左找小于基准点的值
        while (i < j && pv < arr[j]) {
            j--;
        }
        //从左到右找大于的基准点的值
        while(i < j && pv >= arr[i]) {
            i++;
        }
        swap(arr,i,j);-
    }
    swap(arr,l,i);
    System.out.println(Arrays.toString(arr)+"j="+j);
    return  i;
}

注意事项

1. 必须先从右到左开始找，否则会出现大出现在前面
2. 基准点不参与它们所找的值

ArrayList扩容机制

1. ArrayList()会使用长度为零的数组
2. ArrayList(int initalCapacity)会使用指定的容量数组
3. public ArrayList(Collection<? extends E> c)会使用c作为容量大小
4. add(Object o)首次扩容为10，下次1.5倍。但实际上先右移>>1,在加上原有上的容量。
5. addAll(Collection c) 没有元素是，扩容是Math.max(10,实际个数),有元素是,扩容是Math.max(原容量1.5倍，实际元素个数）

fail-fast 与 fail-safe

1. ArrayList是fail-fast的典型代表，遍历的同时不能修改，尽快失败
2. CopyOnWriteArrayList是fail-safe的典型代表,遍历的同时可以修改，原理是读写分离
3. Vector也是fail-fast

ArrayList vs LinkedList

ArrayList

1. 基于数据，连续内存
2. 随机访问快（指根据下标访问)
3. 尾部插入，删除性能可以，其他部分插入、删除都会移动数据，性能低
4. 可以利用cpu缓存，局部性原理

LinkedList

1. 基于双向链表，无需连续内存
2. 随机访问慢（要沿着链表遍历)
3. 头尾插入删除性能高
4. 占用内存多

HaspMap

底层数据结构，1.7与1.8有何不同

1. 1.7 数组+链表 1.8 数组 + (链表 | 红黑树)

为何要用红黑树,为何一上来不树化，树化阈值为何8，何时树化，何时退为链表

1. 红黑树用来避免Dos攻击，防止链表超长时性能下降，树化应当偶然情况

   hash表的查找，更新的时间复杂度是O(1),而红黑树的查找，更新的时间复杂度是O(log2n)，TreeNode占用空间也比普通Node的大，如非必要，尽量还是使用链表。
   hash值如果足够随机，则在hash表内按泊松分布，在负载因子0.75的情况下，长度超过8链表出现概率是0.00000006(亿分之6),选择8就是为了让树化几率足够小

2. 树化两个条件：链表长度超过树化阈值；数组容量>=64

3. 退化情况1：在扩容时如果拆分树时，树元素个数<=6则会退化链表

4. 退化情况2：remove树节点时，若root，root.left,root.right,root.left.left为null，也会退化链表

什么情况下会扩容

1. 当HashMap的数量超过原容量的3/4（0.75）,就会扩容（2*原容量）

什么情况下，链表长度已经超过8，但在扩容后，长度并没有减少

1. 当他们hash值都一样时，扩容并不会变。（这个时候就有红黑树了）

索引如何计算

计算对象的hashCode(), 在进行调用HashMap中的hasp()方法进行二次哈希最后&（capiticy - 1) 等价于 % 16得到索引

hashCode都有了，为何还要提供hash()方法

二次hash()是为了综合高位数据，让哈希分布更为均匀

数据容量为何是2的n次幂

计算索引是，如果是2的n次幂可以使用位与运算代替取模，效率更高
扩容时hash&oldCap == 0的元素留在原来位置，否则则新位置=旧位置+oldCap

为什么要选择数据容量是2的n次幂，不是2的n次幂行不行

1. 是设计者综合了各种因素，这样效率更高
2. 可以的，那么他的hash值会更加分布，例如HashTable就不是2的n次幂

put方法流程，1.7和1.8有何不同

1. HashMap是懒惰创建数组的，首次使用才创建数组

2. 计算索引（桶下标)

3. 如果桶下标还没人占用，创建Node占位返回

4. 如果桶下标已经有人占用

   1.已经是TreeNode走红黑树的添加或更新逻辑
   2.是普通Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑

5. 返回前检查容量是否超过阈值，一旦超过进行扩容

6. 不同

   链表插入节点时，1.7是头插法，1.8是尾插法
   1.7是大于等于阈值且没有空位时才扩容，而1.8是大于阈值就扩容
   1.8在扩容计算Node索引时，会优化

加载因子为何默认是0.75f

1. 在空间占用与查询时间之间取得较好的权衡
2. 大于这个值，空间节省了，但链表就会比较长影响性能
3. 小于这个值，冲突少了，但扩容就会更频繁，空间占用多

多线程下会有啥问题

1. 扩容死链（1.7）
2. 数据错乱 (1.7,1.8)

key是否为null，作为key的对象有什么要求？

1. HashMap的key可以为null，但Map的其他实现则不然
2. 作为key对象，必须实现hashCode和equals(equals相等，则hashCode相同，但hashCode相等，equals不一定相等),并且key的内容不能修改

String对象的hashCode()如何设计，为啥每个乘的是31

####目标是达到较为均匀的散列效果，每个字符串的hashCode足够独特

1. 字符串的每个字符串都可以表现为一个数字，称为Si，其中i的范围是0 ~ n-1
2. 31代入公式有较好的散列特性，并且31*h可以被优化为

   即32*h - h
   即2的5次幂 * h - h
   即 h << 5 - h

五种单例模式

第一种饿汉式

/**
 * 饿汉式
 * 1.提供私有的构造方法
 * 2.提供私有静态的常量，用来保存实例对象
 * 3.提供公有静态方法，来获取实例对象
 */
public class Singleton1 implements Serializable {
   private Singleton1(){
       if(INSTANCE != null) {
           throw new RuntimeException("单列对象不能重复创建");
       }
       System.out.println("private Singleton1()");
   }
   private static final Singleton1 INSTANCE = new Singleton1();

   public static Singleton1 getInstance() {
       return INSTANCE;
   }

   public static void otherMethod(){
       System.out.println("otherMethod()");
   }
//   public Object readResolve() {
//       return INSTANCE;
//   }
}

这种饿汉式很不安全，破坏方式有三种

上代码

1. 反射破坏

     private static void reflection(Class<?> clazz) throws Exception {
   
    Constructor<?> constructors = clazz.getDeclaredConstructor();
    constructors.setAccessible(true);
    System.out.println("反射创建实例:"+constructors.newInstance());
   
     }
   

2. 反序列破坏

    private static void serializable(Object instance) throws Exception{
        ByteArrayOutputStream bos = new ByteArrayOutputStream();
        ObjectOutputStream oos = new ObjectOutputStream(bos);
        oos.writeObject(instance);
        ObjectInputStream ois = new ObjectInputStream(new ByteArrayInputStream(bos.toByteArray()));
        System.out.println("反序列化创建实例:"+ois.readObject());
    
    }
   

3. unsafe破坏,基本无解

    private static void unsafe(Class<?> clazz) throws Exception {
   
    Object o = Unsafe.getUnsafe().allocateInstance(clazz);
    System.out.println("Unsafe 创建实例:"+o);
   

   }

第二种枚举饿汉式

public enum Singleton2 {
INSTANCE;
private Singleton2() {
    System.out.println("private Singleton2");

}

@Override
public String toString() {
    return getClass().getName()+"@" + Integer.toHexString(hashCode());

}
public static Singleton2 getInstance() {
    return INSTANCE;
}
public static void otherMethod(){
    System.out.println("otherMethod()");
}
}

这种我以为很效率挺高，也比较安全

第三种同步锁懒汉式

public class Singleton3 implements Serializable {

private Singleton3() {
    System.out.println("private Singleton3()");
}
private static  Singleton3 INSTANCE = null;

public static  synchronized   Singleton3 getInstance() {
    if(INSTANCE == null) {
        INSTANCE = new Singleton3();
    }
    return INSTANCE;
}
public static void otherMethod(){
    System.out.println("otherMethod()");
}

}

第四种dcl(双重锁懒汉式)

public class Singleton4 implements Serializable {
private Singleton4() {
    System.out.println("private Singleton4()");
}
private static volatile Singleton4 INSTANCE = null;

public static Singleton4 getInstance() {
    if(INSTANCE == null) {

        synchronized (Singleton4.class) {
            if(INSTANCE == null) {
                INSTANCE = new Singleton4();
            }
        }
    }
    return INSTANCE;
}

用双重锁的时候一定要用volatile来修饰变量，在多线程下，才会安全，防止构造函数在赋值之后，产生一些有些初始化没有完成。

第五种内部类懒汉式

public class Singleton5 implements Serializable {

private Singleton5() {
    System.out.println("private Singleton5()");
}

private static class Holder {
    static Singleton5 INSTANCE = new Singleton5();
}

public static Singleton5 getInstance() {
    return Holder.INSTANCE;
}
public static void otherMethod(){
    System.out.println("otherMethod()");
}
}

在jdk中那些体现了单例模式

Runtime类是饿汉式

例如：exit() 和 gc()

###System类是双检锁的懒汉式
例如：console

Collections类里面有各种单例模式