首页 > 笔经面经 > Java 知识点整理:算法、设计模式、语法

Java 知识点整理:算法、设计模式、语法

头像
冠状病毒biss
编辑于 2020-06-12 11:02:30 APP内打开
赞 34 | 收藏 244 | 回复9 | 浏览3794

排序算法 9

P1:排序算法的分类

排序算法可以分为内部排序和外部排序,在内存中进行的排序称为内部排序,当要排序的数据量很大时无法全部拷贝到内存,需要使用外存进行排序,这种排序称为外部排序。

内部排序包括比较排序和非比较排序,比较排序包括插入排序、选择排序、交换排序和归并排序,非比较排序包括计数排序、基数排序和桶排序。其中插入排序又包括直接插入排序和希尔排序,选择排序包括直接选择排序和堆排序,交换排序包括冒泡排序和快速排序。


P2:直接插入排序

直接插入排序属于插入排序,是一种稳定的排序,平均时间复杂度和最差时间复杂度均为 O(n²),当元素基本有序时的最好时间复杂度为O(n),空间复杂度为 O(1)。

基本原理是每一趟将一个待排序的记录,按其关键字的大小插入到已经排好序的一组记录的适当位置上,直到所有待排序记录全部插入为止。适用于待排序记录较少或基本有序的情况。

public void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int insertNum = nums[i];
        int insertIndex;
        for (insertIndex = i - 1; insertIndex >= 0 && nums[insertIndex] > insertNum; insertIndex--) {
            nums[insertIndex + 1] = nums[insertIndex];
        }
        nums[insertIndex + 1] = insertNum;
    }
}

优化:直接插入并没有利用到要插入的序列已有序的特点,插入第 i 个元素时可以通过二分查找找到要插入的位置,再把第 i 个元素前 1位与插入位置之间的所有元素后移,把第 i 个元素放在目标位置上。

public void binaryInsertionSort(int[] nums) {
    for (int index = 1; index < nums.length; index++) {
        int insertNum = nums[index];
        int insertIndex = -1;
        int start = 0;
        int end = index - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (insertNum > nums[mid])
                start = mid + 1;
            else if (insertNum < nums[mid])
                end = mid - 1;
            else {
                insertIndex = mid + 1;
                break;
            }
        }
        if (insertIndex == -1)
            insertIndex = start;
        if (index - insertIndex >= 0)
            System.arraycopy(nums, insertIndex, nums, insertIndex + 1, index - insertIndex);
        nums[insertIndex] = insertNum;
    }
}

P3:希尔排序

希尔排序属于插入排序,又称缩小增量排序,是对直接插入排序的一种改进,并且是一种不稳定的排序,平均时间复杂度为O(n^1.3^),最差时间复杂度为 O(n²),最好时间复杂度为 O(n),空间复杂度为 O(1)。

基本原理是把记录按下标的一定增量分组,对每组进行直接插入排序,每次排序后减小增量,当增量减至 1 时,排序完毕。适用于中等规模的数据量,对规模非常大的数据量不是最佳选择。

public void shellSort(int[] nums) {
    for (int d = nums.length / 2; d > 0 ; d /= 2) {
        for (int i = d; i < nums.length; i++) {
            int insertNum = nums[i];
            int insertIndex;
            for (insertIndex = i - d; insertIndex >= 0 && nums[insertIndex] > insertNum; insertIndex -= d) {
                nums[insertIndex + d] = nums[insertIndex];
            }
            nums[insertIndex + d] = insertNum;
        }
    }
}

P4:直接选择排序

直接选择排序属于选择排序,是一种不稳定的排序,任何情况下时间复杂度都是 O(n²),空间复杂度为 O(1)。基本原理是每次在未排序序列中找到最小元素,和未排序序列的第一个元素交换位置,再在剩余的未排序序列重复该操作直到所有元素排序完毕。适用于数据量较小的情况,比直接插入排序稍快。

public void selectSort(int[] nums) {
    int minIndex;
    for (int index = 0; index < nums.length - 1; index++){
        minIndex = index;
        for (int i = index + 1;i < nums.length; i++){
            if(nums[i] < nums[minIndex]) 
                minIndex = i;
        }
        if (index != minIndex){
            swap(nums, index, minIndex);
        }
    }
}

P5:堆排序

堆排序属于选择排序,是对直接选择排序的改进,并且是一种不稳定的排序,任何情况时间复杂度都为 O(nlogn),空间复杂度为 O(1)。

基本原理是将待排序记录看作完全二叉树,可以建立大根堆或小根堆,大根堆中每个节点的值都不小于它的子节点值,小根堆中每个节点的值都不大于它的子节点值。适用于数据量较大的情况。

以大根堆为例,在建堆时首先将最后一个节点作为当前节点,如果当前结点存在父节点且值大于父节点,就将当前节点和父节点交换。在移除时首先暂存根节点的值,然后用最后一个节点代替根节点并作为当前节点,如果当前节点存在子节点且值小于子节点,就将其与值较大的子节点进行交换,调整完堆后返回暂存的值。

public void add(int[] nums, int i, int num){
    nums[i] = num;
    int curIndex = i;
    while (curIndex > 0) {
        int parentIndex = (curIndex - 1) / 2;
        if (nums[parentIndex] < nums[curIndex]) 
            swap(nums, parentIndex, curIndex);
        else break;
        curIndex =parentIndex;
    }
}

public int remove(int[] nums, int size){
    int result = nums[0];
    nums[0] = nums[size - 1];
    int curIndex = 0;
    while (true) {
        int leftIndex = curIndex * 2 + 1;
        int rightIndex = curIndex * 2 + 2;
        if (leftIndex >= size) break;
        int maxIndex = leftIndex;
        if (rightIndex < size && nums[maxIndex] < nums[rightIndex])
            maxIndex = rightIndex;
        if (nums[curIndex] < nums[maxIndex])
            swap(nums, curIndex, maxIndex);
        else break;
        curIndex = maxIndex;
    }
    return result;
}

P6:冒泡排序

冒泡排序属于交换排序,是一种稳定的排序,平均时间复杂度和最坏时间复杂度均为 O(n²),当元素基本有序时的最好时间复杂度为O(n),空间复杂度为 O(1)。

基本原理是比较相邻的元素,如果第一个比第二个大就进行交换,对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,每一轮排序后末尾元素都是有序的,针对 n 个元素重复以上步骤 n -1 次排序完毕。

public void bubbleSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        for (int index = 0; index < nums.length - 1 - i; index++) {
            if (nums[index] > nums[index + 1]) 
                swap(nums, index, index + 1)
        }
    }
}

优化:当序列已经有序时仍会进行不必要的比较,可以设置一个标志位记录是否有元素交换,如果没有直接结束比较。

public void betterBubbleSort(int[] nums) {
    boolean swap;
    for (int i = 0; i < nums.length - 1; i++) {
        swap = true;
        for (int index = 0; index < nums.length - 1 - i; index++) {
            if (nums[index] > nums[index + 1]) {
                swap(nums, index ,index + 1);
                swap = false;
            }
        }
        if (swap) break;
    }
}

P7:快速排序

快速排序属于交换排序,是对冒泡排序的一种改进,并且是一种不稳定的排序,平均时间复杂度和最好时间复杂度均为 O(nlogn),当元素基本有序时的最坏时间复杂度为O(n²),空间复杂度为 O(logn)。

基本原理是首先选择一个基准元素,然后通过一趟排序将要排序的数据分割成独立的两部分,一部分全部小于等于基准元素,一部分全部大于等于基准元素,然后再按此方法递归对这两部分数据分别进行快速排序。适用于数据量较大且元素基本无序的情况。

快速排序的一次划分从两头交替搜索,直到 low 和 high 指针重合,因此时间复杂度是 O(n),而整个算法的时间复杂度与划分趟数有关。最好情况是每次划分选择的中间数恰好将当前序列几乎等分,经过 logn 趟划分便可得到长度为 1 的子表,这样算法的时间复杂度为O(nlogn)。最坏的情况是每次所选中间数是当前序列中的最大或最小元素,这使每次划分所得的子表其中一个为空表,另一个子表的长度为原表的长度 - 1。这样长度为 n 的数据表的需要经过 n 趟划分,整个排序算法的时间复杂度为O(n²)。

从空间上看尽管快速排序只需要一个元素的辅助空间,但快速排序需要一个栈空间来实现递归。最好的情况下,即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表,所需栈的最大深度为 log(n+1),最坏情况下栈的最大深度为 n。

public void quickSort(int[] nums, int start, int end) {
    if (start < end) {
        int pivotIndex = getPivotIndex(nums, start, end);
        quickSort(nums, start, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, end);
    }
}

public int getPivotIndex(int[] nums, int start, int end) {
    int pivot = nums[start];
    int low = start;
    int high = end;
    while (low < high) {
        while (low <= high && nums[low] <= pivot) 
            low++;
        while (low <= high && nums[high] > pivot) 
            high--;
        if (low < high) 
            swap(nums, low, high);
    }
    swap(nums, start, high);
    return high;
}

优化:当规模足够小时,例如 end - start < 10 时,采用直接插入排序。


P8:归并排序

归并排序是基于归并操作的排序算法,是一种稳定的排序算法,任何情况时间复杂度都为 O(nlogn),空间复杂度为 O(n)。

基本原理是应用分治法将待排序序列分成两部分,然后对两部分分别递归排序,最后进行合并,使用一个辅助空间并设定两个指针分别指向两个有序序列的起始元素,将指针对应的较小元素添加到辅助空间,重复该步骤到某一序列到达末尾,然后将另一序列剩余元素合并到辅助空间末尾。适用于数据量大且对稳定性有要求的情况。

int[] help;

public void mergeSort(int[] arr) {
    int[] help = new int[arr.length];
    sort(arr, 0, arr.length - 1);
}

public void sort(int[] arr, int start, int end) {
    if (start == end) return;
    int mid = start + (end - start) / 2;
    sort(arr, start, mid);
    sort(arr, mid + 1, end);
    merge(arr, start, mid, end);
}

public void merge(int[] arr, int start, int mid, int end) {
    if (end + 1 - start >= 0) System.arraycopy(arr, start, help, start, end + 1 - start);
    int p = start;
    int q = mid + 1;
    int index = start;
    while (p <= mid && q <= end) {
        if (help[p] < help[q]) 
            arr[index++] = help[p++];
        else 
            arr[index++] = help[q++];
    }
    while (p <= mid) arr[index++] = help[p++];
    while (q <= end) arr[index++] = help[q++];
}

P9:排序算法的选择原则

当数据量规模较小时,可以考虑直接插入排序或直接选择排序,当元素分布有序时直接插入排序将大大减少比较次数和移动记录的次数,如果不要求稳定性,可以使用直接选择排序,效率略高于直接插入排序。

当数据量规模中等时,可以选择希尔排序。

当数据量规模较大时,可以考虑堆排序、快速排序和归并排序。如果对稳定性有要求可以采用归并排序,如果元素分布随机可以采用快速排序,如果元素分布接近正序或逆序可以采用堆排序。

一般不使用冒泡排序。


设计模式 7

P1:设计模式的原则

开闭原则:面向对象设计中最基础的设计原则,指一个软件实体(类、模块、方法等)应该对扩展开放,对修改关闭。它强调用抽象构建框架,用实现扩展细节,提高代码的可复用性和可维护性。例如在版本更新时尽量不修改源代码,但可以增加新功能。

单一职责原则:一个类、接口或方法只负责一个职责,可以提高代码可读性和可维护性,降低代码复杂度以及变更引起的风险。

依赖倒置原则:程序应该依赖于抽象类或接口,而不是具体的实现类。可以降低代码的耦合度,提高系统的稳定性。

接口隔离原则:将不同功能定义在不同接口中实现接口隔离,避免了类依赖它不需要的接口,减少了接口之间依赖的冗余性和复杂性。

里氏替换原则:对开闭原则的补充,规定了任何父类可以出现的地方子类都一定可以出现,可以约束继承泛滥,加键程序健壮性。

迪米特原则:也叫最少知道原则,每个模块对其他模块都要尽可能少的了解和依赖,可以降低代码耦合度。

合成/聚合原则:尽量使用组合(has a)或聚合(contains a)而不是继承关系达到软件复用的目的,可以使系统更加灵活,降低耦合度。


P2:设计模式的分类

创建型模式:提供了一种在创建对象的同时隐藏创建逻辑的方式,而不是使用 new 运算符直接实例化对象,这使得程序在判断针对某个给定实例需要创建哪些对象时更加灵活。包括:工厂模式、抽象工厂模式、单例模式、建造者模式、原型模式。

结构型模式:通过类和接口之间的继承和引用实现创建复杂结构对象的功能。包括:适配器模式、桥接模式、过滤器模式、组合模式、装饰器模式、外观模式、享元模式、代理模式。

行为型模式:通过类之间不同的通信方式实现不同的行为方式。包括:责任链模式、命名模式、解释器模式、迭代器模式、中介者模式、备忘录模式、观察者模式、状态模式、策略模式、模板模式、访问者模式。


P3:工厂模式

工厂模式属于创建型模式,分为简单工厂模式,工厂方法模式和抽象工厂模式。

简单工厂模式指由一个工厂对象来创建实例,客户端不需要关注创建的逻辑,只需要提供传入工厂对象的参数。

工厂方法模式指定义一个创建对象的接口,让接口的实现类来决定创建哪一种对象,工厂方法模式让类的实例化推迟到子类中进行。工厂方法模式中客户端只需关心对应的工厂而无需关心创建细节,主要解决了产品扩展的问题,在简单工厂模式中如果产品种类变多,工厂的职责会越来越多,不便于维护。

抽象工厂模式指提供一个创建一系列相关或相互依赖对象的接口,无需指定它们的具体类。客户端不依赖于产品类实例如何被创建和实现的细节,主要用于系统的产品有多于一个的产品族,而系统只消费其中某一个产品族产品的情况。

总结:

简单工厂:一个工厂,一种抽象产品。例如一个麦当劳店,可以生产多种汉堡。

public class MacDonaldFactory {
    public Hamburger eatHamburger(String name) {
        if ("beef".equals(name))
            return new BeefHamburger();
        else if ("pig".equals(name))
            return new PigHamburger();
        return null;
    }
}

interface Hamburger {
    void eat();
}

class BeefHamburger implements Hamburger {
    @Override
    public void eat() {
        System.out.println("吃牛肉汉堡");
    }
}

class PigHamburger implements Hamburger {
    @Override
    public void eat() {
        System.out.println("吃猪肉汉堡");
    }
}

工厂方法:多个工厂,一种抽象产品。例如一个麦当劳店,可以生产多种汉堡,一个肯德基店,也可以生产多种汉堡。

public interface HamburgerFactory {
    Hamburger build();
}

class MCFactory implements HamburgerFactory {
    @Override
    public Hamburger build() {
        return new MCHamburger();
    }
}

class KFCFactory implements HamburgerFactory {
    @Override
    public Hamburger build() {
        return new KFCHamburger();
    }
}

interface Hamburger {
    void eat();
}

class MCHamburger implements Hamburger {
    @Override
    public void eat() {
        System.out.println("吃麦当劳汉堡");
    }
}

class KFCHamburger implements Hamburger {
    @Override
    public void eat() {
        System.out.println("吃肯德基汉堡");
    }
}

抽象工厂:多个工厂,多种抽象产品。例如一个麦当劳店和一个肯德基店都可以生产多种汉堡和可乐。

public interface FoodFactory {
    Hamburger buildHamburger();
    Drink buildDrink();
}

class MCFactory implements FoodFactory {
    @Override
    public Hamburger buildHamburger() {
        return new MCHamburger();
    }

    @Override
    public Drink buildDrink() {
        return new MCDrink();
    }
}

class KFCFactory implements FoodFactory {
    @Override
    public Hamburger buildHamburger() {
        return new KFCHamburger();
    }

    @Override
    public Drink buildDrink() {
        return new KFCDrink();
    }
}

interface Hamburger {
    void eat();
}

class MCHamburger implements Hamburger {
    @Override
    public void eat() {
        System.out.println("吃麦当劳汉堡");
    }
}

class KFCHamburger implements Hamburger {
    @Override
    public void eat() {
        System.out.println("吃肯德基汉堡");
    }
}

interface Drink {
    void drink();
}

class MCDrink implements Drink {
    @Override
    public void drink() {
        System.out.println("喝麦当劳饮料");
    }
}

class KFCDrink implements Drink {
    @Override
    public void drink() {
        System.out.println("喝肯德基饮料");
    }
}

P4:单例模式

单例模式属于创建型模式,是指一个单例类在任何情况下都只存在一个实例,构造器必须是私有的并由自己创建一个静态实例对象,并对外提供一个静态公有的获取实例方法。优点是在内存里只有一个实例,减少了内存的开销,尤其是频繁的创建和销毁实例的情况下,并且可以避免对资源的多重占用。缺点是没有抽象层,难以扩展,与单一职责原则冲突。

饿汉式:在类加载时就初始化创建单例对象,是线程安全的,但不管是否使用都会创建对象,可能会浪费内存。

public class HungrySingleton {
    private HungrySingleton(){}

    private static HungrySingleton instance = new HungrySingleton();

    public static HungrySingleton getInstance() {
        return instance;
    }
}

懒汉式:在外部调用时才会加载,是线程不安全的,可以加锁保证线程安全但效率低。

public class LazySingleton {
    private LazySingleton(){}

    private static LazySingleton instance;

    public static LazySingleton getInstance() {
        if(instance == null) {
            instance = new LazySingleton();
        }
        return instance;
    }
}

双重检查锁:使用 volatile 以及两次检查来减小 synchronized 锁范围,提升效率。

public class DoubleCheckSingleton {
    private DoubleCheckSingleton(){}

    private volatile static DoubleCheckSingleton instance;

    public static DoubleCheckSingleton getInstance() {
        if(instance == null) {
            synchronized (DoubleCheckSingleton.class) {
                if (instance == null) {
                    instance = new DoubleCheckSingleton();
                }
            }
        }
        return instance;
    }
}

静态内部类:可以同时解决饿汉式的内存浪费问题和懒汉式的线程安全问题。

public class StaticSingleton {
    private StaticSingleton(){}

    public static StaticSingleton getInstance() {
        return StaticClass.instance;
    }

    private static class StaticClass {
        private static final StaticSingleton instance = new StaticSingleton();
    }
}

枚举:这种方式是 Effective Java 作者提倡的方式,它不仅能避免多线程同步问题,还能防止反序列化重新创建新的对象,绝对防止多次实例化,也能防止反射破解单例的问题。

public enum EnumSingleton {
    INSTANCE;
}

P5:代理模式

代理模式属于结构型模式,为其他对象提供一种代理以控制对这个对象的访问,可以增强目标对象的功能。优点是可以增强目标对象的功能,一定程度降低代码耦合度,扩展性好。缺点是在客户端和目标对象之间增加代理对象会导致请求处理速度变慢,同时也会增加系统复杂度。

静态代理:代理对象持有真实对象的引用,调用代理对象方法时也会调用真实对象的方法,但是会在真实对象方法的前后增加一些其他逻辑。需要手动完成代理操作,在程序运行前就已经存在代理类的字节码文件,代理类和被代理类的关系在运行前就已经确定了。 缺点是一个代理类只能为一个目标类服务,如果要服务多种类型就会增加很大的工作量。

public interface Company {
    void findWorker();
}

public class Hr implements Company {
    @Override
    public void findWorker() {
        System.out.println("我需要找招聘一个员工");
    }
}

public class Proxy implements Company {
    private Hr hr;

    public Proxy(){
        this.hr = new Hr();
    }

    @Override
    public void findWorker() {
        hr.findWorker();
        System.out.println("找到了员工");
    }

}

动态代理:动态代理在程序运行时才创建具体的代理类,代理类和被代理类的关系在运行前是不确定的。动态代理的适用性更强,主要分为 JDK 动态代理和 CGLib 动态代理。

  • JDK 动态代理:通过 Proxy类的 newInstance 方法获取一个动态代理对象,需要传入三个参数,被代理对象的类加载器、被代理对象实现的接口,以及一个 InvocationHandler 调用处理器实例来指明具体的逻辑,相比静态代理最大的优势是接口中声明的所有方法都被转移到 InvocationHandler 中的 invoke 方法集中处理。

    public static void main(String[] args) {
        Hr hr = new Hr();
        Hr proxyHr = (Hr) Proxy.newProxyInstance(hr.getClass().getClassLoader(), hr.getClass().getInterfaces(), (proxy, method, args1) -> {
            System.out.println("接收代理请求");
            Object obj = method.invoke(hr, args1);
            System.out.println("找到了员工,完成请求");
            return obj;
        });
        proxyHr.findWorker();
    }
  • CGLib 动态代理:与 JDK 动态代理不同的是,JDK 动态代理要求实现被代理对象的接口,而 CGLib 要求继承被代理对象,如果一个类是 final 类则不能使用 CGLib 动态代理。两种代理都是在运行期生成字节码,JDK 动态代理直接写字节码,而 CGLib 动态代理使用 ASM 框架写字节码,ASM 作用于已编译好的 Class 文件,其目的是生成、转换和分析以字节数组表示的已编译 Java 类。 JDK 动态代理调用代理方法是通过反射机制实现的,而 GCLib 动态代理是通过 FastClass 机制直接调用方法的,为代理类和被代理类各生成一个类,该类为代理类和被代理类的方法会分配一个 int 类型的参数,调用方法时可以直接定位而省去反射,因此调用方法的效率更高。


P6:装饰器模式

指在不改变原有对象的基础上,将功能附加到对象上,相比继承可以更加灵活地扩展原有对象的功能,属于结构型模式。这种模式创建了一个装饰类,用来包装原有的类,并在保持类方法签名完整性的前提下提供了额外的功能。装饰器模式适合的场景:在不想增加很多子类的前提下扩展一个类的功能或给一个类添加附加职责、动态地给一个类添加功能,这些功能可以再动态地撤销。

和动态代理的区别:装饰器模式的关注点在于给对象动态添加方法,而动态代理更注重对象的访问控制。动态代理通常会在代理类中创建被代理对象的实例,而装饰器模式会将装饰者作为构造器的参数。


P7:适配器模式

适配器模式属于结构型模式,它作为两个不兼容的接口之间的桥梁,结合了两个独立接口的功能,将一个类的接口转换成另外一个接口,这种模式涉及到一个单一的类,该类负责加入独立的或不兼容的接口功能。优点是使得原本由于接口不兼容而不能一起工作的类可以一起工作。 缺点是过多使用适配器会让系统非常零乱,不易整体进行把握。

和装饰器模式的区别:适配器模式的是要将一个接口转变成另一个接口,目的是通过改变接口来解决接口不兼容的问题。而装饰器模式不是要改变被装饰对象的接口,而是要增强原有对象的功能。例如 java.io 包中,适配器模式是将 InputStream 字节输入流通过适配器 InputStreamReader 转换为 Reader 字符输入流,而装饰器模式是将 InputStream 通过装饰器 BufferedInputStream 增强为缓冲字节输入流。


Java 基础 17

P1:Java 语言的基本概念

优点:

  • 具有平台无关性,摆脱了硬件平台的束缚,实现了“一次编写,到处运行”的理想。

  • 提供了一种相对安全的内存管理和访问机制,避免了绝大部分内存泄漏和指针越界问题。

  • 实现了热点代码检测和运行时编译及优化,使得 Java 程序随运行时间增长可以获得更高的性能。

  • 有一套完善的应用程序接口,还支持很多第三方类库。

Java 平台无关性原理:

主要是通过 JVM 和 Java 语言规范实现。

  • 编译器生成一个体系结构中立的目标文件格式,这是一种编译后的代码,只要有 Java 运行时系统,这些编译后的代码可以在很多处理器上运行。Java 编译器通过生成与特定计算机体系结构无关的字节码指令来实现这一特性,字节码文件不仅可以很容易地在任何机器上解释执行,还可以动态地转换成本地机器代码,转换是由 JVM 实现的,JVM 是平台相关的,屏蔽了不同操作系统的差异。
  • Java 中基本数据类型的大小以及有关运算的行为都有明确的说明,例如 Java 中的 int 类型永远为 32 位的整数,而在 C/C++ 中 int 可能是 16 位整数、32 位整数,也可能是编译器开发商指定的其他任何大小。在 Java 中数值类型有固定的字节数,二进制数据以固定的格式进行存储和传输,字符串则采用标准的 Unicode 格式存储。

专业术语:

  • JDK:Java Development Kit,Java 开发工具包。它提供了编译、运行 Java 程序所需的各种工具和资源,包括 Java 编译器、JRE 以及常用的 Java 基础类库等,是 JAVA 的核心。JDK 是编写 Java 程序的程序员使用的软件。
  • JRE:Java Runtime Environment,Java 运行时环境,是运行基于 Java 语言编写的程序所不可缺少的运行环境。JRE 是运行 Java 程序的用户使用的软件。
  • SE:Standard Edition,标准版,用于桌面或简单服务器应用的 Java 平台。
  • EE:Enterprise Edition,企业版,用于复杂服务器应用的 Java 平台。
  • ME:Micro Edition,微型版,用于小型设备的 Java 平台。

P2:Java 基本数据类型

数据类型 占用内存大小 取值范围
byte 1 字节 -2^7^ ~ 2^7^-1
short 2 字节 -2^15^ ~ 2^15^-1
int 4 字节 -2^31^ ~ 2^31^-1
long 8 字节 -2^63^ ~ 2^63^-1
float 4 字节 ±3.4E+38F(有效位数 6~7 位)
double 8 字节 ±1.7E+308(有效位数 15 位)
char 英文在 UTF-8 和 GBK 中均占 1 字节,中文在 UTF-8 占 3 字节,GBK 占 2 字节。 /
boolean 单个变量用 int 代替,占 4 字节,而数组会编码成 byte 数组,占 1 字节。 true、false

每个基本数据类型都对应一个自己的包装类,除了 int 和 char 对应 Integer 和 Character 之外,其余基本数据类型的包装类都是首字母大写即可。自动装箱指的是将基本数据类型包装为一个包装类对象,例如向一个泛型为 Integer 类型的集合添加 int 类型的元素。自动拆箱指的是将一个包装类对象转换为一个基本数据类型,例如将一个包装类对象赋值给一个基本数据类型的变量。要比较两个包装类的数值需要使用 equals 方法,而不能使用 == 比较运算符。


P3:String

不可变性:String 是不可变类,并且存储数据的 value 字符数组也是 final 修饰的不可变数组,因此当修改一个 String 变量的值时,并没有真正修改它引用的 String 对象的字符数组中的值,而是重新创建了一个 String 对象赋值给了 String 变量进行引用。

字符串拼接:直接使用 + 进行字符串拼接,如果是字面量会自动拼接为一个新的常量。要提升拼接效率可以使用 StringBuilder 或 StringBuffer 可变字符串,区别是 StringBuffer 使用了 synchronized 保证线程安全性,但一般字符串拼接都是单线程操作,所以使用 StringBuilder 较多。常量和常量的拼接,结果也在常量池中,且不存在两个相同的常量。只要参与拼接的字符串里有变量,结果就在堆中。

创建: 如果是通过字符串常量赋值的形式,例如 String s = "s",字符串常量内容存于常量池,变量存于栈中并直接引用常量池中的字符串。如果是通过new 的形式,例如 String s = new String("s"),会先在堆中创建实例对象,然后再去常量池寻找需要的字符串常量,如果找到了则直接使用,没找到则开辟新的空间并存储内容,最后栈中变量引用堆中对象,对象再引用常量池中的字符串。


P4:值调用和引用调用

按值调用指的是方法接收的是调用者提供的值,而按引用调用指的是方法接收的是调用者提供的变量地址。Java 总是采用按值调用,也就是说方法得到的是所有参数值的一个副本,当传递对象时实际上方法接收的是这个对象引用的副本。方法不能修改基本数据类型的参数,可以改变对象参数的状态,但不能让对象参数引用一个新的对象。

举例来说,如果传递了一个 int 类型的值 ,改变该值不会影响实参,因为改变的是该值的一个副本。如果传递了一个 int[] 类型的数组,改变数组的内容会影响实参,而如果改变这个参数的引用,并不会让实参引用新的数组对象。


P5:面向对象

概念:面向对象是一种程序设计思想,相对于面向过程而言更适合解决规模较大的问题。采用面向对象的开发方式可以对现实的事物进行抽象,把现实的事物映射为开发对象,接近人的思维。并且可以通过继承或组合的方式实现代码的重用,因此开发效率高。并且面向对象的开发方式提高了代码的可读性,使代码结构更加清晰,方便代码的维护。

特性:

  • 封装:也称数据隐藏,从形式上看就是将数据和行为组合在一个包中,并对对象的使用者隐藏具体的实现方式。
  • 继承:可以通过继承来扩展一个类,扩展的子类可以继承父类的属性和方法,并可以添加自己独有的属性和方法。Java 中类只可以单继承,接口之间是可以多继承的。继承是一种"is-a"的关系,可以提高代码的复用性。
  • 多态:父类的变量可以引用一个子类的对象,在运行时通过动态绑定来决定调用的方法。
    • 重载:是指同一个类中具有多个方法名相同而方法参数列表不同的方法,重载方法的返回值类型不做要求,但方法的参数列表必须不同。重载属于一种编译时多态。
    • 重写:是指子类具有和父类方法名和方法参数列表都相同的方法,要求返回值不大于父类方法的返回值,抛出的异常类型不大于父类方法抛出的异常类型,访问修饰符可见性不小于父类方法的访问修饰符可见性。重写属于一种运行时多态。

P6:方法修饰符

访问修饰符 本类可见性 本包可见性 子类可见性 不同包可见性
public
protected ×
默认 × ×
private × × ×

P7:接口和抽象类

成员变量:接口中的成员变量默认是 public static final 修饰的常量,抽象类中的成员变量无特殊要求。

构造器:接口和抽象类都不能直接实例化,但接口没有构造器,抽象类是有构造器的。

方法:接口中的方法默认是 public 修饰的,Java 8 开始支持默认方法和静态方法,Java 9 开始支持私有方法。抽象类中的方法不做要求,抽象类可以不含抽象方法,但含有抽象方法的类一定是抽象类。

继承:接口可以多继承和多实现,而抽象类只能单继承。

选择原则:如果知道某个类应该成为基类,那么第一选择应该是让它成为一个接口,只有在必须要有方法定义和成员变量的时候,才应该选择抽象类。在接口和抽象类的选择上,必须遵守这样一个原则:行为模型应该总是通过接口而不是抽象类定义。通过抽象类建立行为模型会出现的问题:如果有一个产品类 A,有两个子类 B 和 C 分别有自己的功能,如果出现一个既有 B 产品功能又有 C 产品功能的新产品需求,由于 Java 不允许多继承就出现了问题,而如果是接口的话只需要同时实现两个接口即可。


P8:Object 类

Object 的类是所有类的父类,Object 类的方法:

  • equals:用于检测一个对象是否等于另一个对象,默认使用 == 比较两个对象的引用,可以重写 equals 方法自定义比较规则。equals 方法需要满足以下规范:自反性、对称性、传递性、一致性并对于任何非空引用 x,x.equals(null) 返回 false。
  • hashCode:散列码是由对象导出的一个整型值,是没有规律的,每个对象都有一个默认的散列码,值由对象的存储地址得出。字符串可能有相同的散列码,因为字符串的散列码是由内容导出的。为了在集合中正确使用对象,一般需要同时重写 equals 和 hashCode 方法,要求是 equals 相同是 hashCode 必须相同,但 hashCode 相同时 equals 未必相同,因此 hashCode 是两个对象相同的必要不充分条件。
  • toString:打印对象时默认会调用它的 toString 方法,如果没有重写该方法默认打印的是表示对象值的一个字符串,一般需要重写该方法。打印数组时可以使用 Arrays.toString() 方法。
  • clone:clone 方法声明为 protected,类只能通过该方法克隆它自己的对象,如果希望其他类也能调用该方法必须定义该方法为 public。如果一个对象的类没有实现 Cloneable 接口,该对象调用 clone 方法会抛出一个 CloneNotSupport 异常。默认的 clone 方法是浅拷贝,一般重写 clone 方法需要实现 Cloneable 接口并指定访问修饰符为 public。
    • 浅拷贝:如果对象包含子对象的引用,拷贝字段就会得到相同子对象的另一个引用,如果共享的子对象是不可变的则是安全的,通常子对象都是可变的,因此浅拷贝是不安全的,拷贝对象的更改会影响原对象。
    • 深拷贝:会完全拷贝基本数据类型和引用数据类型,深拷贝是安全的。
  • finalize:在垃圾收集器清理对象之前调用,由于无法确定该对象执行的具体时机因此已经被废弃。
  • getClass:返回包含对象信息的类对象。
  • wait / notify / notifyAll:阻塞或唤醒持有该对象锁的线程。

P9:内部类

使用内部类主要有两个原因:内部类可以对同一个包中的其他类隐藏。内部类方法可以访问定义这个内部类的作用域中的数据,包括原本私有的数据。内部类是一个编译器现象,与虚拟机无关。编译器会把内部类转换成常规的类文件,用美元符号 $ 分隔外部类名与内部类名,而虚拟机对此一无所知。

静态内部类:由static修饰,属于外部类本身,只加载一次。类可以定义的成分静态内部类都可以定义,可以访问外部类的静态变量和方法,通过 new 外部类.内部类构造器 来创建对象。只要内部类不需要访问外部类对象,就应该使用静态内部类。

成员内部类:属于外部类的每个对象,随对象一起加载。不可以定义静态成员和方法,可以访问外部类的所有内容,通过 new 外部类构造器.new 内部类构造器 来创建对象。

局部内部类:定义在方法、构造器、代码块、循环中。不能声明访问修饰符,只能定义实例成员变量和实例方法,作用范围仅在声明这个局部类的代码块中。

匿名内部类:没有名字的局部内部类,可以简化代码,匿名内部类会立即创建一个匿名内部类的对象返回,对象类型相当于当前 new 的类的子类类型。匿名内部类一般用于实现事件监听器和其他回调。

class OuterClass{

    static class StaticInnerClass {}

    class NormalInnerClass {}

    public void test() {

        class LocalClass {}

        // 静态内部类创建对象
        new OuterClass.StaticInnerClass();

        // 成员内部类创建对象
        new OuterClass().new NormalInnerClass();

        // 局部内部类创建对象
        new LocalClass();

        // 匿名内部类创建对象
        Runnable runnable = () -> {};
    }
}

P10:static

static 关键字主要有两个作用:(1)为某特定数据类型或对象分配单一的存储空间,而与创建对象的个数无关。(2)让某个属性或方法与类而不是对象关联在一起,可以在不创建对象的情况下通过类名来访问。

作用范围:

static 修饰的变量称为静态变量,也叫做类变量,可以直接通过类名来访问,静态变量存储在 JVM 的方法区中。

static 修饰的方法称为静态方法,也叫做类方法,可以直接通过类名来访问,静态方法只能访问静态变量或静态方法。

static 修饰的代码块称为静态代码块,只能定义在类下,会在类加载时执行,只会执行一次。

static 修饰的类称为静态内部类,可以访问外部类的静态变量和方法。

static 也可以用来导入包下的静态变量。

类初始化的顺序:

(1)父类静态代码块和静态变量
(2)子类静态代码块和静态变量
(3)父类普通代码块和普通变量
(4)父类构造器
(5)子类普通代码块和普通变量
(6)子类构造器

其中代码块和变量的初始化顺序按照类中声明的顺序执行。


P11:序列化和反序列化

Java 对象在 JVM 运行时被创建,当 JVM 退出时存活对象都会销毁,如果需要将对象及其状态持久化,就需要通过序列化来实现,将对象及其状态信息保存在字节数组中,在需要时再将这些字节数组反序列化为对象。对象序列化保存的是对象的状态,因此类中的静态变量不会被序列化,因为静态变量是类属性。

要实现序列化功能需要实现 java.io.Serializabale 标记接口,序列化和反序列化必须保持序列化 ID 的一致,一般使用 private static final long serialVersionUID 定义序列化 ID,如果需要序列化父类的状态,父类也需要实现该接口。

有许多序列化框架,例如 fastjson、thrift等,也可以使用 JDK 自带的 ObjectOutputStream 类的 writeObject 方法实现序列化,将对象以流的方式写入磁盘中,ObjectInputStream 类的 readObject 方法实现反序列化,以流的方式从磁盘读取。

除了静态变量外,transient 修饰的变量也不会被序列化。transient 的作用就是把这字段的生命周期仅限于内存中而不会写到磁盘里持久化,被 transient 修饰的变量会被设为对应数据类型的默认初始值。

除了实现 Serializabale 接口外,另一种方法是实现 Exteranlizable 接口。 需要重写 writeExternal 和 readExternal 方法,它的效率比Serializable 高一些,并且可以决定哪些属性需要序列化(即使是 transient 修饰的变量),但是对大量对象或者重复对象则效率低。


P12:反射

在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法,对于任意一个对象,都能够调用它的任意一个方法和属性;这种动态获取的信息以及动态调用对象的方法的功能称为Java的反射机制。优点是运行时动态获取类的全部信息,缺点是破坏了类的封装性,泛型的约束性。反射是框架的核心灵魂,动态代理设计模式采用了反射机制,还有 Spring、Hibernate 等框架也大量使用到了反射机制。

在程序运行期间,Java 运行时系统始终为所有对象维护一个运行时类型标识,这个信息会跟踪每个对象所属的类,虚拟机利用运行时类型信息选择要执行的正确方法,保存这些信息的类名为 Class。

获取 Class 实例的方法有三种:(1)直接通过 类名.class 。②通过对象的 getClass()方法。③通过 Class.forName(类的全限定名)。Class 类中的 getFields、getMethods 和 getConstructors 方法分别返回这个类支持的公共字段、方法和构造器的数组,其中包括父类的公共成员。Class 类中的 getDeclaredFields、getDeclaredMethods 和 getDeclaredConstructors 方法分别返回这个类声明的全部字段、方法和构造器的数组,其中包括私有成员、包成员和受保护成员,但不包括父类的成员。

Field、Method、Constructor 分别用于描述类的字段、方法和构造器。这三个类都有一个 getName 方法返回字段、方法或构造器的名称。Field 类有一个 getType 方法用来返回描述字段类型的一个对象,这个对象的类型也是 Class。Method 和 Constructor 类有报告参数类型的方法,Method 类还有一个报告返回类型的方法。这三个类都有一个 getModifiers 方法,它返回一个整数,用不同的 0/1 位描述所使用的修饰符。


P13:注解

注解是一种标记,可以使类或接口附加额外的信息,是帮助编译器和 JVM 完成一些特定功能的,例如常用注解 @Override 标识一个方法是重写方法。

元注解就是自定义注解的注解,包括:

  • @Target:用来约束注解作用的位置,值是 ElementType 枚举类实例,包括 METHOD 方法、VARIABLE 变量、TYPE 类/接口、PARAMETER 方法参数、CONSTRUCTORS 构造器和 LOACL_VARIABLE 局部变量等。

  • @Rentention:用来约束注解的生命周期,值是 RetentionPolicy 枚举类实例,包括:SOURCE 源码、CLASS 字节码和 RUNTIME 运行时。

  • @Documented:表明这个注解应该被 javadoc 工具记录。

  • @Inherited:表面某个被标注的类型是被继承的。


P14:异常

所有的异常都派生于 Throwable 类的一个类实例,在下一层分为 Error 和 Exception。

Error 类描述了 Java 运行时系统的内部错误和资源耗尽错误,如果出现了这种错误,一般无能为力。

Exception 类又分为 RuntimeException 和其他异常,一般规则是由编程错误导致的异常属于 RuntimeException,如果程序本身没有问题,但由于像 IO 错误这类问题导致的异常属于其他异常。派生于 Error 和 RuntimeException 的异常属于非检查型异常,其余异常都属于检查型异常。

常见的 RuntimeException 异常:

  • ClassCastException,错误的强制类型转换。
  • ArrayIndexOutOfBoundsException,数组访问越界。
  • NullPointerException,空指针异常。

常见的检查型异常:

  • FileNotFoundException,试图打开不存在的文件。
  • ClassNotFoundException,试图根据指定字符串查找 Class 对象,而这个类并不存在。
  • IOException,试图超越文件末尾继续读取数据。

异常处理:

抛出异常:遇到异常不进行具体处理,而是将异常抛出给调用者,由调用者根据情况处理。抛出异常有2种形式,一种是 throws 关键字声明抛出的异常,作用在方法上,一种是使用throw 语句直接抛出异常,作用在方法内。

捕获异常:使用 try/catch 进行异常的捕获,try 中发生的异常会被 catch 代码块捕获,根据情况进行处理,如果有 finally 代码块无论是否发生异常都会执行,一般用于释放资源,Java 7 开始可以将资源定义在 try 代码块中自动释放资源。


P15:泛型

泛型的本质是参数化类型,泛型提供了编译时类型的安全检测机制,该机制允许程序在编译时检测非法的类型。

类型擦除:

虚拟机没有泛型类型对象,所有对象都属于普通类。无论何时定义一个泛型类型,都会自动提供一个相应的原始类型,原始类型的名字就是去掉类型参数后的泛型类型名。类型变量会被擦除,如果没有限定类型就会替换为 Object,如果有限定类型就会替换为第一个限定类型,例如 <T extends A & B> 会使用 A 类型替换 T。

泛型主要用于编译阶段,在编译后生成的 Java 字节代码文件中不包含泛型中的类型信息。

泛型规范:

泛型标记 说明
E(Element) 在集合中使用,表示在集合中存放的元素。
T(Type) 表示类,包括基本的类以及自定义类。
K(Key) 表示键,例如 Map 集合中的 Key。
V(Value) 表示值,例如 Map 集合中的 Value。
N(Number) 表示数值类型。
表示不确定的类型。

泛型限定:

对泛型上限的限定使用<? extends T>,它表示该通配符所代表的类型是 T 类的子类型或 T 接口的子接口。

对泛型下限的限定使用<? super T>,它表示该通配符所代表的类型是 T 类的父类型或 T 接口的父接口。


P16:Java 8 新特性

lambda 表达式:lambda 表达式允许把函数作为一个方法的参数传递到方法中,主要用来简化匿名内部类的代码。

函数式接口:使用 @FunctionalInterface 注解标识,有且仅有一个抽象方法,可以被隐式转换为 lambda 表达式。

方法引用:可以直接引用已有类或对象的方法或构造器,进一步简化 lambda 表达式。方法引用有四种形式:引用构造方法、引用类的静态方法、引用特定类的任意对象方法、引用某个对象的方法。

接口中的方法:接口中可以定义 default 修饰的默认方法,降低了接口升级的复杂性,还可以定义静态方法。

注解:Java 8 引入了重复注解机制,相同的注解在同一个地方可以声明多次。注解的作用范围也进行了扩展,可以作用于局部变量、泛型、方法异常等。

类型推测:加强了类型推测机制,可以使代码更加简洁,例如在定义泛型集合时可以省略对象中的泛型参数。

Optional 类:用来处理空指针异常,提高代码可读性。

Stream 类:把函数式编程风格引入 Java 语言,提供了很多功能,可以使代码更加简洁。方法包括forEach() 遍历、count() 统计个数、filter() 按条件过滤、limit() 取前 n 个元素、skip() 跳过前 n 个元素、map() 映射加工、concat() 合并stream流等。

日期:增强了日期和时间的 API,新的 java.time 主要包含了处理日期、时间、日期/时间、时区、时刻和时钟等操作。

JavaScript:Java 8 提供了一个新的 Nashorn JavaScript 引擎,它允许我们在 JVM上运行特定的 JavaScript 应用。


P17:Java IO

IO 模型 对应的 Java 版本
BIO(同步阻塞 IO) 1.4 之前
NIO(同步非阻塞 IO) 1.4
AIO(异步非阻塞 IO) 1.7

同步和异步是通信机制,阻塞和非阻塞是调用状态。

  • 同步 IO 是用户线程发起 I/O 请求后需要等待或者轮询内核 I/O 操作完成后才能继续执行。

  • 异步 IO 是用户线程发起 I/O 请求后仍可以继续执行,当内核 I/O 操作完成后会通知用户线程,或者调用用户线程注册的回调函数。

  • 阻塞 IO 是指 I/O 操作需要彻底完成后才能返回用户空间 。

  • 非阻塞 IO 是指 I/O 操作被调用后立即返回一个状态值,无需等 I/O 操作彻底完成。

BIO:

同步阻塞式 IO,服务器实现模式为一个连接请求对应一个线程,即客户端有连接请求时服务器端就需要启动一个线程进行处理,如果这个连接不做任何事情会造成不必要的线程开销。可以通过线程池机制改善,这种 IO 称为伪异步 IO。

主要分为字符流和字节流,字符流包括字符输入流 Reader 和字符输出流 Writer,字节流包括字节输入流 InputStream 和 字节输出流 OutputStream,字节流和字符流都有对应的缓冲流和过滤流,也可以将字节流包装为字符流。

适用场景:连接数目少、服务器资源多、开发难度低。


NIO:

同步非阻塞 IO,服务器实现模式为多个连接请求对应一个线程,客户端发送的连接请求都会注册到一个多路复用器 Selector 上,多路复用器轮询到连接有I/O请求时才启动一个线程进行处理,有数据才会开启线程处理,性能比较好。

同步是指线程还是要不断接收客户端连接并处理数据,非阻塞是指如果一个管道没有数据,不需要等待,可以轮询下一个管道。

有三个核心组件:

  • Selector

    选择器或多路复用器,主要作用是轮询检查多个 Channel 的状态,判断 Channel 注册的事件是否发生,即判断 Channel 是否处于可读或可写状态。在使用之前需要将 Channel 注册到 Selector 上,注册之后会得到一个 SelectionKey,通过 SelectionKey 可以获取 Channel 和 Selector 的相关信息。

  • Channel

    双向通道,替换了 IO 中的 Stream,不能直接访问数据,要通过 Buffer 来读写数据,也可以和其他 Channel 交互。

    分类:FileChannel 处理文件、DatagramChannel 处理 UDP 数据、SocketChannel 处理 TCP 数据,用作客户端、ServerSocketChannel 处理 TCP 数据,用作服务器端。

  • Buffer

    缓冲区,本质是一块可读写数据的内存,这块内存被包装成 NIO 的 Buffer 对象,用来简化数据的读写。Buffer 的三个重要属性:position 表示下一次读写数据的位置,limit 表示本次读写的极限位置,capacity 表示最大容量。

    • flip() 将写转为读,底层实现原理是把 position 置 0,并把 limit 设为当前的 position 值。
    • 通过 clear() 将读转为写模式(用于读完全部数据的情况,把 position 置 0,limit 设为 capacity)。
    • 通过 compact() 将读转为写模式(用于没有读完全部数据,存在未读数据的情况,让 position 指向未读数据的下一个)。
    • 通道的方向和 Buffer 的方向是相反的,读取数据相当于向 Buffer 写入,写出数据相当于从 Buffer 读取。

    使用步骤:向 Buffer 写入数据,调用 flip 方法将 Buffer 从写模式切换为读模式,从 Buffer 中读取数据,调用 clear 或 compact 方法来清空 Buffer。

适应场景:连接数目多、连接时间短、开发难度高。


AIO:

异步非阻塞 IO,服务器实现模式为一个有效请求对应一个线程,客户端的 I/O 请求都是由操作系统先完成 IO 操作后再通知服务器应用来启动线程直接使用数据。

异步是指服务端线程接收到客户端管道后就交给底层处理IO通信,自己可以做其他事情,非阻塞是指客户端有数据才会处理,处理好再通知服务器。

AsynchronousServerSocketChannel 异步服务器端通道,通过静态方法 open() 获取实例,通过 accept 方法获取客户端连接通道。

AsynchronousSocketChannel 异步客户端通道,通过静态方法 open() 获取实例,过 connect 方法连接服务器通道。

AsynchronousChannelGroup 异步通道分组管理器,它可以实现资源共享。创建时需要传入一个ExecutorService,也就是绑定一个线程池,该线程池负责两个任务:处理 IO 事件和触发 CompletionHandler 回调接口。

实现方式:

通过 Future 的 get 方法进行阻塞式调用。

通过实现 CompletionHandler 接口,重写请求成功的回调方法 completed() 和 请求失败回调方法 failed()。

适用场景:连接数目多、连接时间长、开发难度高。


9条回帖

回帖
加载中...
话题 回帖

相关热帖

笔经面经近期热帖

近期精华帖

热门推荐