↻
❮
❯
⬆︎
×
分类 Java后端  14183字  48分钟♻️ 📤 🖨 

JavaSE基础：面向对象、基本语法、异常处理、集合框架…

作者

本文全面介绍了JavaSE基础知识，涵盖了面向对象编程的核心概念（如继承、封装、多态和抽象），详解了Java中的访问权限修饰符、对象克隆、静态和实例变量的区别，以及抽象类和接口的不同之处。文章还讨论了Java中的异常处理机制，包括Error与Exception类的区别、编译时和运行时异常的处理方式，介绍了I/O流、字节流与字符流的转换、序列化机制等内容，还详细剖析了JavaSE集合框架中List、HashMap的原理，是Java面试准备的实用参考。

1 面向对象

1.1 面向对象的特性

  • 继承：从已有类得到继承信息创建新类的过程。提供继承信息的类称为父类（超类、基类）；得到继承信息的类称为子类（派生类）。继承让变化中的软件系统有了一定的延续性，同时也是封装程序中可变因素的重要手段。
  • 封装：把数据和操作数据的方法绑定起来，对数据的访问只能通过已定义的接口。面向对象的本质就是将现实世界描绘成一系列完全自治、封闭的对象。在类中编写的方法就是对实现细节的一种封装，即编写一个类就是对数据和数据操作的封装。可以说，封装就是隐藏一切可隐藏的东西，只向外界提供最简单的编程接口。
  • 多态：允许不同子类型的对象对同一消息作出不同的响应，即用同样的对象引用调用同样的方法但是做了不同的事情。多态性分为编译时的多态性和运行时的多态性。如果将对象的方法视为对象向外界提供的服务，那么运行时的多态性可以解释为：当A系统访问B系统提供的服务时，B系统有多种提供服务的方式， 但一切对A系统来说都是透明的。方法重载（Overload）实现的是编译时的多态性（也称为前绑定），而方法重写 （Override）实现的是运行时的多态性（也称为后绑定）。运行时的多态是面向对象最精髓的东西，要实现多态需要做两件事：① 方法重写（子类继承父类并重写父类中已有的或抽象的方法）；② 对象造型（用父类型引用引用子类型对象，这样同样的引用调用同样的方法就会根据子类对象的不同而表现出不同的行为）。

默认情况下面向对象有3大特性——封装、继承、多态，有时也称抽象为第4大特性：

  • 抽象：将一类对象的共同特征总结出来构造类的过程，包括数据抽象和行为抽象两方面。抽象只关注对 象有哪些属性和行为，并不关注这些行为的细节是什么。
  • 注意String类是final类，不可被继承。
  • Java 中实现多态的机制是什么？
    【答】靠的是父类或接口定义的引用变量可以指向子类或具体实现类的实例对象，而程序调用的方法在运行期才动态绑定，就是引用变量所指向的具体实例对象的方法，也就是内存里正在运行的那个对象的方法，而不是引用变 量的类型中定义的方法。

1.2 访问权限修饰符

不同的权限修饰符的区别见下表（不写表示默认default）：

修饰符 当前类 同包 子类 其他包
public ✓ ✓ ✓ ✓
protected ✓ ✓ ✓ ×
default ✓ ✓ × ×
private ✓ × × ×

1.3 对象克隆

在实际编程过程中，常会遇到这种情况：有一个对象A，在某一时刻A中已经包含了一些有效值，此时可能会需要一个和A完全相同新对象B，并且此后对B任何改动都不会影响到A中的值，也就是说，A与B是两个独立的对象，但B的初始值是由A对象确定的。在Java语言中，用简单的赋值语句是不能满足这种需求的。要满足这种需求虽然有很多途径，但实现clone()方法是其中最简单，也是最高效的手段。

1.3.1 new和clone()的过程

  • new操作符的本意是分配内存。程序执行到new操作符时，首先去看new操作符后的类型（因为只有知道类型后， 才能知道要分配多大的内存空间）。分配完内存后，再调用构造函数，填充对象的各个域，这一步叫做对象的初始化。构造方法返回后，一个对象创建完毕，可以将其引用（地址）发布到外部，在外部就可以使用这个引用操纵这个对象。
  • clone()方法在第一步与new相似，都是分配内存，但调用方法时，分配的内存和原对象（即调用方法的对象）相同。然后再使用原对象中对应的各个域，填充新对象的域，填充完成之后方法返回，一个新的相同的对象被创建，同样可以把这个新对象的引用发布到外部。

1.3.2 复制引用和复制对象

以下代码执行后打印的地址值是相同的，说明p和p1只是引用而已，他们都指向了一个相同的对象。这种现象称为复制引用。

Person p = new Person(23, "zhang");
Person p1 = p;
System.out.println(p);
System.out.println(p1);

复制引用

以下代码才是真正的克隆对象，所打印的两个对象的地址是不同的，也就是说创建了新的对象， 而不是把原对象的地址赋给了一个 新的引用变量。

Person p = new Person(23, "zhang");
Person p1 = (Person) p.clone();
System.out.println(p);
System.out.println(p1);

克隆对象

1.3.3 深拷贝和浅拷贝

以下示例代码的Person类中有两个成员变量，分别是age和result，age是int型，result是Result类。要想使用clone，需实现Cloneable接口并实现clone()方法。如下所示：

public class Person implements Clonable {
    private int age;
    private Result result;

    public Person() {}

    public Person(int age, Result result) {
        this.age = age;
        this.result = result;
    }

    public int getAge() {
        return this.age;
    }

    public Result getResult() {
        return this.result;
    }

    @Override
    protected Object clone() throws CloneNotSupportedException {
        return (Person) super.clone();
    }
}

由于age是基本数据类型，那么对它的拷贝为直接将一个4字节的整数值拷贝就行。
但result是引用类型， 则对它的拷贝有两种方式：直接将原对象中引用型成员的引用值拷贝给新对象对应的字段——浅拷贝；或根据原对象中的引用型成员指向的对象创建一个新的相同的对象，将其引用赋给新对象对应的字段——深拷贝。

clone()方法默认执行浅拷贝。要想实现深拷贝，需在clone()方法内部，把该对象的其他引用对象也要clone一份，这就要求这个被引用的对象必须也要实现 Cloneable接口并实现clone()方法。如下例所示：

@Override
protected Object clone() throws CloneNotSupportedException {
    Person newPerson = (Person) super.clone();
    newPerson.result = (Result) this.result.clone();
    return newPerson;
}

1.4 静态变量和实例变量

  • 静态变量：被static修饰符修饰的变量，也称为类变量。它属于类，不属于类的任何一个对象。一个类不管创建多少个对象，静态变量在内存中有且仅有一个拷贝。
  • 实例变量：必须依存于某一实例，需要先创建对象然后通过对象才能访问到它。

静态变量可以实现让多个对象共享内存。

1.5 抽象类和接口

  • 不同点
    • 抽象类（Abstract Class）
      1. 如果一个类中有抽象方法，那么这个类一定是抽象类；但抽象类可以没有抽象方法
      2. 可以存在构造方法
      3. 可以存在普通属性、方法、静态属性和静态方法
      4. 抽象类中的抽象方法需要有子类实现，如果子类不实现，则子类也需要定义为抽象的
    • 接口（Interface）
      1. 接口中的方法永远都被public来修饰
      2. 没有构造方法，也不能实例化接口对象
      3. 只有方法的声明，没有方法体
      4. 只能定义常量，如果定义变量，在编译的时候都会默认加上“public static final”
      5. 接口中定义的方法都需要实现类来实现，如果实现类不能实现接口中的所有方法，则实现类需要定义为抽象类
      6. 静态方法不能被子类重写（覆盖），因此接口中不定声明静态方法
      7. 使用接口可以实现多继承
  • 相同点
    1. 不能实例化
    2. 可以将抽象类和接口类型作为引用类型
    3. 一个类如果继承了某个抽象类或者实现了某个接口都需要对其中的抽象方法全部进行实现，否则该类仍需要被声明为抽象类
  • 抽象方法是否可同时是静态的 (static), 是否可同时是本地方法 (native)，是否可同时被synchronized
    【答】都不能。抽象方法需要子类重写，而静态的方法是无法被重写的，因此二者是矛盾的。本地方法是由 本地代码（如 C 代码）实现的方法，而抽象方法是没有实现的，也是矛盾的。synchronized和方法的实现细节有关， 抽象方法不涉及实现细节，因此也是相互矛盾的。

1.6 静态嵌套类和内部类

  • 静态嵌套类（Static Nested Class）：被声明为静态（static）的内部类，可以不依赖于外部类实例被实例化。
    • 内部类（Inner Class）：需要在外部类实例化后才能实例化。

Java中非静态内部类对象的创建要依赖其外部类对象

【例】以下代码中的foo()和main()均为静态方法，没有this，即没有所谓的外部类对象，因此无法直接创建内部类对象。只能通过实例化外部类后再实例化内部类。

class Outer {
    class Inner {}

    public static void foo() {
        // new Inner(); 无法实例化内部类
        new Outer().new Inner();
    }

    public void bar() {
        new Inner();
    }

    public static void main(String[] args) {
        // new Inner(); 无法实例化内部类
        new Outer().new Inner();
    }
}

2 JavaSE语法

2.1 基本数据类型

Java 的基本数据类型所占字节数如下表所示

数据类型 字节数 数据表示范围
byte 1 -128 ~ 127
short 2 -32768 ~ 32767
int 4 -2147483648 ~ 2147483647
long 8 -2^63^ ~ 2^63^-1
float 4 -3.403E38 ~ 3.403E38
double 8 -1.798E308 ~ 1.798E308
char 2 表示一个字符，如'a'、'A'、0、'龍'
boolean 1 true or false
  • String是引用类型，底层用char数组实现。详见：字符串类
  • Java5以前，switch(expr)中，expr只能是 byte、short、char、int。
    从Java 5开始，引入了枚举类型， expr也可以是enum类型。
    从Java 7开始，expr还可以是字符串（String），但长整型（long）在目前所有的版本中都是不可以的。

2.2 Java中的goto语句

goto是Java中的保留字，在目前版本的Java中没有使用。根据James Gosling（Java 之父）编写的《The Java Programming Language》一书的附录中给出了一个Java关键字列表，其中有goto和const，但是这两个关键字目前无法使用，因此有些地方称之为保留字（其实保留字这个词应有更广泛的意义，因为熟悉C语言的都知道，在系统类库中使用过的有特殊意义的单词或单词的组合都被视为保留字）。

  • 在Java中，如何跳出当前的多重嵌套循环
    【答】在最外层循环前加一个标记如A，用 break A;可以跳出多重循环。（Java 中支持带标签的break和continue语句，作用类似C和C++中的goto语句，但是就像要避免使用goto一样，应避免使用带标签的 break 和 continue，因为它不会让你的程序变得更优雅，很多时候甚至有相反的作用）。

2.3 &和&&

  • &运算符有两种用法：(1)按位与；(2)逻辑与。
  • &&运算符的作用是短路与运算，若左边的表达式的值为false，右边的表达式会直接不进行运算。

一般情况下都使用&&而非&，例如在验证用户登录时判定用户名非null且非空字符串，应写为username != null && !username.equals("")，二者的顺序不能交换，更不能用&运算符，因为第一个条件若不成立，根本不能进行字符串的equals()比较，否则会产生NullPointerException空指针异常。

逻辑或运算符|和短路或运算符||同理。

2.4 值传递和引用传递

Java语言的方法调用只支持参数的值传递。当一个对象实例作为一个参数被传递到方法中时，参数的值就是对该对象的引用。对象的属性可以在被调用过程中被改变，但对对象引用的改变是不会影响到调用者的。C++和C#中可通过传引用或传输出参数来改变传入的参数的值。

  • 当一个对象被当作参数传递到一个方法后，此方法可改变这个对象的属性，并可返回变化后的结果，那么这里到底是值传递还是引用传递?
    【答】是值传递。Java 语言的方法调用只支持参数的值传递。

2.5 重载和重写

方法的重载（Overload）和重写（Override）都是实现多态的方式，区别在于前者实现的是编译时的多态性，而后者实现的是运行时的多态性。重写时要给方法追加@Override注解。

重载发生在一个类中，同名的方法如果有不同的参数列表（参数类型不同、参数个数不同或者二者都不同）则视为重载；重写发生在子类与父类之间，要求子类被重写方法与父类被重写方法有相同的返回类型，比父类被重写方法更好访问，不能比父类被重写方法声明更多的异常（里氏代换原则）。重载对返回类型没有特殊的要求。

  • 方法重载的规则：
    1. 方法名一致，参数列表中参数的顺序、类型、个数不同。
    2. 重载与方法的返回值无关，存在于父类和子类之间、同类中。
    3. 可以抛出不同的异常，可以有不同修饰符。
  • 方法重写的规则：
    1. 参数列表必须完全与被重写方法的一致，返回类型必须完全与被重写方法的返回类型一致。
    2. 构造方法不能被重写，声明为final的方法不能被重写。声明为static的方法不能被重写，但能够被再次声明。
    3. 访问权限不能比父类中被重写的方法的访问权限更低。
    4. 重写的方法能够抛出任何非强制异常（UncheckedException，非运行时异常），无论被重写的方法是否抛出异常。但重写的方法不能抛出新的强制性异常，或者比被重写方法声明的更广泛的强制性异常。
  • 为什么函数不能根据返回类型来区分重载？
    【答】因为调用时不能指定类型信息，编译器不知道你要调用哪个函数。

2.6 equals()和hashCode()

Java对于equals()和hashCode()方法的规定如下：

  1. 如果两个对象相同（即equals()返回 true），那么它们的hashCode()值一定相同。
  2. 如果两个对象的 hashCode()相同，它们并不一定相同。

实际可以违背上述规定，但此时就会发现在使用容器时，相同的对象可以出现在Set集合中，同时增加新元素 的效率会大大下降（对于使用哈希存储的系统，如果哈希码频繁的冲突将会造成存取性能急剧下降）。

在Joshua Bloch的《Effective Java》中这样介绍equals()方法：首先须满足以下原则——

  1. 自反性：x.equals(x)必须返回true
  2. 对称性：x.equals(y)返回true时，y.equals(x)也必须返回true
  3. 传递性：x.equals(y)和y.equals(z)都返回 true时，x.equals(z)也必须返回true
  4. 一致性：当x和y引用的对象信息没有被修改时，多次调用x.equals(y)应该得到同样的返回值
  5. 对于任何非null值的引用x，x.equals(null)必须返回false

实现高质量的 equals 方法的诀窍包括：

  1. 使用==操作符检查“参数是否为这个对象的引用”
  2. 使用instanceof操作符检查“参数是否为正确的类型”
  3. 对于类中的关键属性，检查参数传入对象 的属性是否与之相匹配
  4. 编写完后，检查是否满足对称性、传递性、一致性
  5. 重写时总是同时重写hashCode()
  6. 不要将参数中的Object对象替换为其他的类型
  • ==和equals()的区别
    【答】一个是方法，一个是运算符——

    • ==：如果比较的对象是基本数据类型，则比较的是数值是否相等；如果比较的是引用数据类型，则比较的是对象的地址值是否相等。
    • equals()：用来比较方法两个对象的内容是否相等。不能用于基本数据类型变量，如果没有对equals()方法进行重写，则比较的是引用类型的变量所指向的对象的地址。

2.7 字符编码方式

Java中使用的编码是Unicode（不选择任何特定的编码，直接使用字符在字符集中的编号，这是统一的唯一方法），一个char 类型占2个字节（16 比特），因此可以存储一个中文汉字。

使用Unicode意味着字符在JVM内部和外部有不同的表现形式：在JVM内部都是Unicode，当这个字符被从JVM内部转移到外部时（例如存入文件系统中），需要进行编码转换。所以Java中有字节流和字符流，以及在字符流和字节流之间进行转换的转换流，如InputStreamReader和OutputStreamReader，这两个类是字节流和字符流之间的适配器类，承担了编码转换的任务。

3 异常处理

3.1 异常处理机制

Java对异常进行了分类，不同类型的异常分别用不同的Java类表示，所有异常的根类为java.lang.Throwable， Throwable下面又派生了Error和Exception两个子类。

3.1.1 Error类和Exception类

  • Error类：一般指与虚拟机相关的问题，如系统崩溃，虚拟机错误，内存空间不足，方法调用栈溢出等。对于这类 错误的导致的应用程序中断，仅靠程序本身无法恢复和和预防，遇到这样的错误，建议让程序终止。
  • Exception类：表示程序可以处理的异常，可以捕获且可能恢复。遇到这类异常，应该尽可能处理异常，使程序恢复运行，而不应该随意终止异常。按照异常需要处理的时机，又分为分为编译时异常和运行时异常 。

3.1.2 编译时异常和运行时异常

只有java语言提供了编译时异常（CheckedException，强制性异常），Java认为编译时异常都是可以被处理的异常，所以Java程序必须显式处理编译时异常。如果程序没有处理编译时异常，该程序在编译时就会发生错误无法编译。这体现了Java的设计哲学：没有完善错误处理的代码根本没有机会被执行。
对编译时异常处理方法有两种：

  1. 当前方法知道如何处理该异常，则用try...catch块来处理该异常。注意异常机制有这么一个原则：如果在catch中遇到return或异常等使得该函数终止，那么若有finally就必须先执行finally代码块里面的代码然后再返回值。
  2. 当前方法不知道如何处理，则在定义该方法时用throws字句声明抛出该异常。

运行时异常（RuntimeException、非强制性异常）只有当代码在运行时才发行的异常（如除数为0、数组下标越界等），编译时不需要try...catch。Runtime异常产生频繁，处理麻烦，若显式声明或捕获将会对程序的可读性和运行效率影响很大。所以由系统自动检测并将它们交给缺省的异常处理程序。当然如果有处理要求也可以显式捕获它们。

3.1.3 常见的RuntimeException

  • java.lang.NullPointerException：空指针异常。出现原因：调用了未经初始化的对象或者是不存在的对象。
  • java.lang.ClassNotFoundException：指定的类找不到。出现原因：类的名称和路径加载错误；通常都是程序 试图通过字符串来加载某个类时可能引发异常。
  • java.lang.NumberFormatException：字符串转换为数字异常。出现原因：字符型数据中包含非数字型字符。
  • java.lang.IndexOutOfBoundsException：数组角标越界异常，常见于操作数组对象时发生。
  • java.lang.IllegalArgumentException：方法传递参数错误。
  • java.lang.ClassCastException：数据类型转换异常。

3.2 throw和throws的区别

  • throw
    1. throw语句用在方法体内，表示抛出异常，由方法体内的语句处理。
    2. 是具体向外抛出异常的动作，所以它抛出的是一个异常实例，执行throw语句一定是抛出了某种异常。
  • throws
    1. throws语句用在方法声明后面，表示如果抛出异常，由该方法的调用者来进行异常的处理。
    2. throws声明这个方法会抛出某种类型的异常，让它的使用者知道需要捕获的异常的类型。
    3. throws表示出现异常的一种可能性，并不一定会发生这种异常。

3.3 final、finally、finalize()的区别

  • final：用于声明属性，方法和类，分别表示属性不可变，方法不可覆盖，被其修饰的类不可继承。
  • finally：异常处理语句结构的一部分，表示总是执行。
  • finalize()：Object类的一个方法，在垃圾回收器执行的时候会调用被回收对象的此方法，可以覆盖此方法提供垃圾收集时的其他资源回收，例如关闭文件等。该方法更像是对象生命周期的临终方法，当该方法被系统调用则代表该对象即将“死亡”。注：主动调用该方法并不会导致该对象“死亡”，因为这是一个被动的方法（实为回调方法），无需主动调用。

4 IO流

4.1 流的类型

  • 按照流的方向分类
    • 输入流（InputStream）
    • 输出流（OutputStream）
  • 按照实现功能分类
    • 节点流：可以从或向一个特定的地方（节点）读写数据。如FileReader。
    • 处理流：对一个已存在的流的连接和封装，通过所封装的流的功能调用实现数据读写。如BufferedReader。处理流的构造方法总是要带一个其他的流对象做参数。一个流对象经过其他流的多次包装，称为流的链接。
  • 按照处理数据的单位分类
    • 字节流（继承于InputStream和OutputStream）
    • 字符流（继承于InputStreamReader和OutputStreamWriter）

4.2 字节流和字符流

字符流

字节流

  • 字节流读取时，读到一个字节就返回一个字节； 字符流使用了字节流读到一个或多个字节时，根据指定的编码表，将对应的字符返回（中文对应的字节数是两个，在 UTF-8 码表中是 3 个字节）。
  • 字节流可以处理所有类型数据（主要为byte型数据），如图片、MP3、AVI视频文件；字符流只能处理字符数据。因此只要是处理纯文本数据，就优先考虑使用字符流，除此之外都用字节流。
  • 字节流转字符流：
    字节输入流转字符输入流通过InputStreamReader实现，该类的构造函数可以传入InputStream对象。
    字节输出流转字符输出流通过OutputStreamWriter实现，该类的构造函数可以传入OutputStream对象。

4.3 序列化

序列化是一种处理对象流的机制，用于解决在对对象流进行读写操作时所引发的问题。对象流为将对象的内容进行流化，可以对流化后的对象进行读写操作，也可将流化后的对象传输于网络之间。

实现：将需要被序列化的类实现Serializable接口， 该接口没有需要实现的方法，只是为了标注该对象是可被序列化的。使用一个输出流（如FileOutputStream）构造一个ObjectOutputStream对象流对象（抛出IOException），再使用该对象的writeObject(obj)方法将对象obj写出（即保存其状态）。输入流的实现同理。

【例】将java对象序列化到文件里

// 对象输入流
ObjectOutputStream objectOutputStream = new ObjectOutputStream(new FileOutputStream(new File("test_obj")));
objectOutputStream.writeObject(new User("akira", 37));
objectOutputStream.close();

// 对象输入流
ObjectInputStream objectInputStream = new ObjectInputStream(new FileInputStream(new File("text_obj")));
User user = (User) objectInputStream.readObject();
System.out.println(user);
objectInputStream.close();

5 集合框架

Java集合框架

5.1 数据结构基础

相关资源：数据结构强化笔记

时间复杂度表示算法的执行时间与数据规模之间的增长关系。

空间复杂度表示算法占用的额外存储空间与数据规模之间的增长关系。

大O表示法：O(1)\lt O(\log n)\lt O(n)\lt O(n\log n)\lt O(n^2)\lt O(n^3)\lt O(n^k)\lt O(2^n)\lt O(n!)

5.1.1 数组

数组（Array）是一种用连续内存空间存储相同数据类型数据的线性数据结构。

数组

寻址：

  • 公式：数组的首地址 + 索引 × 存储数据的类型大小
  • 数组索引从0开始，因为若从1开始时，对于cpu来说增加了一个减法指令。

时间复杂度分析：

  • 随机存取：O(1)
  • 查找
    • 顺序查找：O(n)
    • 二分查找：O(\log n)
  • 插入、删除：平均O(n)

5.1.2 链表（单链表、双链表）

链表（Linked List）中的每一个元素称之为结点（Node），物理存储单元上，非连续、非顺序的存储结构。

单链表（Single Linked List）的每个结点包括两个部分——存储数据元素的数据域、存储下一个结点地址的后继指针next

单链表

查找、插入、删除的时间复杂度：

  • 头结点：O(1)
  • 其他结点：O(n)

双链表（Double Linked List）结点除了有一个后继指针next指向后面的结点外，还有一个前驱指针prev指向前面的结点

双链表

查找、插入、删除的时间复杂度：

  • 头尾结点：O(1)
  • 其他结点：O(n)
  • 给定结点指针：O(1)

5.1.3 二叉树

⼆叉树（Binary Tree）：⼀种特殊的有序树，要么为空树，要么每个结点最多只有两棵⼦树，即结点的度只能为0、1、2，子树区分左右顺序（左、右子结点）。

二叉树

5.1.3.1 二叉搜索树

二叉搜索树（Binary Search Tree, BST）：一种常见的特殊二叉树，又名二叉排序树。

通常定义：

  1. 所有子树中，左儿子值 < 父结点值 < 右儿子值
  2. 没有键值相等的结点

时间复杂度分析：

  • 插入、删除：O(\log n)
  • 查找
    • 平均情况：O(\log n)
    • 最坏情况（退化成链表）：O(n)

二叉搜索树

5.1.3.2 红黑树

红黑树（Red Black Tree）：一种自平衡的二叉搜索树，曾称平衡二叉B树（Symmetric Binary B-Tree）。在添加或删除结点时，若不符合其定义会发生O(1)时间复杂度的旋转，以满足其定义。

定义：

  1. 结点要么是红色，要么是黑色
  2. 根结点为黑色
  3. 叶结点均为黑色的空结点
  4. 红色结点的子结点均为黑色
  5. 从任一结点到叶子结点的所有路径都包含相同数目的黑色结点

查找、新增、删除时间复杂度：均为O(\log n)

红黑树

5.1.4 散列表

散列表（Hash Table）：又名哈希表。由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性，根据键（Key）直接访问内存中的值（Value）。

散列函数：将键映射为数组下标的函数，可表示为hashValue = hash(key)。基本要求如下

  • 计算结果应为大于等于0的整数
  • 若key1 == key2，则两者的哈希值也应相同，即hash(key1) == hash(key2)
  • 若key1 != key2，则两者的哈希值也必不相同，即hash(key1) != hash(key2)，实际几乎不可能完美实现

散列表

散列冲突：多个key映射到同一个数组下标位置。

拉链法：常用的冲突解决方法。数组的每个下标位置称为桶（Bucket）或者槽（Slot），每个桶（槽）对应一条链表，散列值相同的元素存储于相同槽位对应的链表中。

时间复杂度分析：

  • 插入：O(1)
  • 查找、删除
    • 平均情况：O(1)
    • 最坏情况（退化为链表）：O(n)
    • 改造成其他高效的动态数据结构（如红黑树）：O(\log n)

拉链法

将拉链法中的链表改造红黑树的另一个非常重要的原因：可以防止DDoS攻击
分布式拒绝服务攻击（Distributed Denial of Service，DDoS）：指处于不同位置的多个攻击者同时向一个或数个目标发动攻击，或者—个攻击者控制了位于不同位置的多台机器并利用这些机器对受害者同时实施攻击。由于攻击的发出点是分布在不同地方的，这类攻击称为分布式拒绝服务攻击，其中的攻击者可以有多个

5.2 List

5.2.1 ArrayList源码分析

常见属性

ArrayList常用属性

构造方法

ArrayList构造方法

新增元素和扩容操作

ArrayList新增元素和扩容操作

  • ArrayList底层是用动态的数组实现的
  • 初始容量为0，当第一次添加数据的时候才会初始化容量为10
  • 在进行扩容时，容量变成原来容量的1.5倍，每次扩容都需要拷贝数组
  • 在添加数据时
    • 确保数组已使用长度（size）加1之后足够存下下一个数据
    • 计算数组的容量，若当前数组已使用长度+1大于当前的数组长度，则调用grow()方法扩容（原来的1.5倍）
    • 确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
    • 返回添加成功布尔值。

5.2.2 数组与List之间的转换

  • 数组转List：使用java.util.Arrays工具类的asList()静态方法
  • List转数组：使用List对象的toArray()方法。无参方法返回Object数组；传入初始化长度的数组对象，返回该对象数组

数组与List之间的转换

【问】转换后修改数据的后果：

  1. 用Arrays.asList()转List后，如果修改了数组内容，list受影响吗？
    【答】受影响。因为其底层使用Arrays类中的一个内部类ArrayList来构造集合，在该集合的构造器中，将传入的集合进行了包装而已，最终指向的都是同一个内存地址。
  2. List用toArray()转数组后，如果修改了List内容，数组受影响吗？
    【答】不受影响。调用了toArray后在底层进行了元素值的拷贝，因此即使list修改了以后，数组也不受影响。

转换后修改数据的后果

5.2.3 ArrayList与LinkedList的区别

  • 底层数据结构
    1. ArrayList是动态数组的数据结构实现
    2. LinkedList是双向链表的数据结构实现
  • 操作数据效率
    1. 随机存取：ArrayList为顺序存储，支持随机存取，即时间复杂度为 $O(1)$ ；LinkedList不支持随机存取
    2. 顺序查找：ArrayList与LinkedList均需遍历全表，时间复杂度均为 $O(n)$
    3. 插入、删除
      • ArrayList尾部增删的时间复杂度为 $O(1)$ ；其他部分增删需挪动元素，时间复杂度为 $O(n)$
      • LinkedList头尾结点增删的时间复杂度为 $O(1)$ ；其他均需遍历链表，时间复杂度为 $O(n)$
  • 内存空间占用
    1. ArrayList底层是数组，内存连续，节省内存
    2. LinkedList底层为双向链表，需要额外存储两个指针，更占内存
  • 线程安全
    1. ArrayList和LinkedList都不是线程安全的
    2. 若想保证线程安全，有两种方案：
      • 在方法内使用，局部变量是线程安全的
      • 使用线程安全的List（如下图所示）

使用线程安全的List

5.3 HashMap

5.3.1 实现原理

底层为哈希表，即 数组 + ( 链表 | 红黑树 )

  1. 当往HashMap中put元素时，利用hashCode()重新计算出当前对象元素的哈希值，即在数组中的下标
  2. 若出现哈希值相同，此时有两种情况
    • 若key相同，则覆盖原始值
    • 若key不同（出现冲突），则将值放入链表或红黑树中
  3. 获取时，直接找哈希值对应的下标，再进一步判断key是否相同，从而找到对应值

HashMap原理

在JDK1.7和JDK1.8中的区别

  • JDK1.8之前采用拉链法，即数组中每一格对应一条链表。若遇到哈希冲突，则将冲突的值加至链表中。
  • JDK1.8中，当链表的长度大于阈值（默认为8）且数组长度达到64时，将链表转换为红黑树，以减少搜索时间。扩容resize()时，若红黑树拆分成的树的结点数小于等于临界值6个，则退化成链表。

5.3.2 HashMap源码分析

常见属性

HashMap常见属性

构造函数

HashMap构造函数

5.3.2.1 put()方法的具体流程

添加数据流程图

put()方法的具体流程

  1. 判断键值对数组table是否为空或为null，否则执行resize()进行扩容（初始化）。
  2. 根据键计算哈希值得到数组索引。
  3. 判断table[i] == null，若条件成立，则直接新建、添加结点。
  4. 若上述条件不成立
    1. 判断table[i]的首个元素是否和键一样，若相同则直接覆盖值。
    2. 判断table[i]是否为treeNode（即是否是红黑树），若是，则直接在树中插入键值对。
    3. 遍历table[i]，在对应链表的尾部插入数据，并判断：当链表的长度大于8时，将链表转换为红黑树，在红黑树中执行插入操作。遍历过程中若发现键已存在则直接覆盖值。
  5. 插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold（数组长度*0.75，即填满75%），若超过则进行扩容。

5.3.2.2 扩容机制

扩容流程

扩容流程

  • 在添加元素或初始化时需要调用resize()方法进行扩容。第一次添加数据初始化数组长度为16，之后每次扩容均达到扩容阈值（数组长度*0.75）
  • 每次扩容时，均为将其容量翻倍
  • 扩容后会新创建一个数组，再把老数组中的数据挪到新数组中
    • 对于没有哈希冲突的结点，新数组中的索引为 e.hash & (newCap - 1)
    • 若为红黑树，则执行红黑树的结点插入操作
    • 若为链表，则需遍历链表。可能需要拆分链表：判断是否有 e.hash & oldCap == 0，即该元素要么停留在原始位置，要么移动到原始位置＋增加的数组大小

5.3.3 寻址算法

寻址算法

  • (h = key.hashCode()) ^ (h >>> 16)：扰动算法，使哈希值更加均匀，減少哈希冲突
  • (n - 1) & hash：得到数组中的索引，代替取模，性能更好，数组长度必须是2的n次幂

数组长度必须是2的n次幂的原因

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

5.3.4 在JDK1.7中的多线程死循环问题

HashMap在JDK1.7中的数据结构为：数组+链表
在数组进行扩容时，链表使用头插法，有可能导致死循环

下图中变量e指向需要迁移的对象，变量next指向下一个需要迁移的对象，可见在数据迁移的过程中并没有新的对象产生，只是改变了对象的引用

在JDK1.7中的多线程死循环问题

【例】
线程1：读取到当前的hashmap数据，数据中一个链表在准备扩容时，线程2介入
线程2：也读取hashmap，直接进行扩容。因为是头插法，链表的顺序会颠倒（原来的顺序为AB，扩容后的顺序为BA）。线程2执行结束
线程1：继续执行时就会出现死循环问题——线程1先将A移入新的链表，再将B插入到链头，由于线程2的原因，B的next指向了A，所以B->A->B，形成循环。

在JDK1.8中将扩容算法进行了调整，链表改用尾插法，避免了上述的死循环问题。

发表评论