当前位置：首页 > article >正文

Java 基础知识 (集合框架 + 并发编程 + JVM 原理 + 数据结构与算法)

article 2024/11/24 21:36:05

文章目录

一.集合框架
- 1. 常见集合接口及其特点
- - List 接口
  - Set 接口
  - Map 接口
- 2. ArrayList 和 LinkedList 的区别和适用场景
- - ArrayList
  - LinkedList
- 3. HashSet 和 TreeSet 的特点和用法
- - HashSet
  - TreeSet
- 4. HashMap 和 TreeMap 的实现原理和使用注意事项
- - HashMap
  - TreeMap
- 5. 集合遍历方式
- - 迭代器（Iterator）
  - 增强 for 循环
二.并发编程
- 1. 多线程基础
- - 1.1 线程的创建
  - 1.2 线程状态
- 2. 线程同步
- - 2.1 synchronized 关键字
  - 2.2 Lock 接口
- 3. 线程通信
- - 3.1 wait()、notify()、notifyAll() 方法
- 4. 线程安全
- - 4.1 常见的线程安全问题
  - 4.2 解决方法
- 5. 并发工具类
- - 5.1 ConcurrentHashMap
  - 5.2 CountDownLatch
  - 5.3 CyclicBarrier
- 6. 线程池
- - 6.1 Executor 框架
  - 6.2 线程池的创建和使用
三.JVM 原理
- 1. JVM 内存结构
- - 1.1 堆（Heap）
  - 1.2 栈（Stack）
  - 1.3 方法区（Method Area）
  - 1.4 程序计数器（Program Counter Register）
- 2. 垃圾回收
- - 2.1 垃圾回收算法
  - 2.2 垃圾回收器
- 3. 类加载机制
- - 3.1 类加载过程
  - 3.2 双亲委派模型
- 4. JVM 原理与调优
- - 4.1 JVM 内存模型
  - 4.2 类加载机制
  - 4.3 垃圾回收
  - 4.4 JVM 参数调优
  - 4.5 JVM 诊断工具
四.数据结构与算法
- 1. 数据结构
- - 1.1 数组
  - 1.2 链表
  - 1.3 栈
  - 1.4 队列
  - 1.5 树
  - 1.6 图
- 2. 算法
- - 2.1 排序算法
  - 2.2 搜索算法
  - 2.3 贪心算法
  - 2.4 动态规划
  - 2.5 分治算法

一.集合框架

1. 常见集合接口及其特点

List 接口

特点：有序集合，允许重复元素。
主要实现类：
- ArrayList：基于动态数组实现，支持快速随机访问，但在中间插入或删除元素效率较低。
- LinkedList：基于双向链表实现，适合频繁的插入和删除操作，但随机访问效率较低。

Set 接口

特点：不包含重复元素的集合。
主要实现类：
- HashSet：基于哈希表实现，不保证元素的顺序，插入和查找效率高。
- TreeSet：基于红黑树实现，元素自然排序或自定义排序，插入和查找效率较高。

Map 接口

特点：存储键值对，键唯一，值可以重复。
主要实现类：
- HashMap：基于哈希表实现，不保证键值对的顺序，插入和查找效率高。
- TreeMap：基于红黑树实现，键值对按键的自然顺序或自定义顺序排序，插入和查找效率较高。

2. ArrayList 和 LinkedList 的区别和适用场景

ArrayList

特点：
- 基于动态数组实现。
- 支持快速随机访问。
- 中间插入或删除元素效率较低。
适用场景：
- 需要频繁随机访问元素。
- 元素数量相对固定，不需要频繁插入和删除。

LinkedList

特点：
- 基于双向链表实现。
- 适合频繁的插入和删除操作。
- 随机访问效率较低。
适用场景：
- 需要频繁插入和删除元素。
- 不需要频繁随机访问元素。

3. HashSet 和 TreeSet 的特点和用法

HashSet

特点：
- 基于哈希表实现。
- 不保证元素的顺序。
- 插入和查找效率高。

用法：

HashSet<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");

TreeSet

特点：
- 基于红黑树实现。
- 元素自然排序或自定义排序。
- 插入和查找效率较高。

用法：

TreeSet<String> set = new TreeSet<>();
set.add("Apple");
set.add("Banana");

4. HashMap 和 TreeMap 的实现原理和使用注意事项

HashMap

实现原理：
- 基于哈希表实现。
- 使用哈希码来确定元素的存储位置。
- 解决哈希冲突的方法有链地址法和开放地址法。
使用注意事项：
- 键对象必须正确实现 hashCode 和 equals 方法。
- 不保证键值对的顺序。

用法：

HashMap<String, Integer> map = new HashMap<>();
map.put("Apple", 1);
map.put("Banana", 2);

TreeMap

实现原理：
- 基于红黑树实现。
- 键值对按键的自然顺序或自定义顺序排序。
使用注意事项：
- 键对象必须实现 Comparable 接口或提供 Comparator。
- 插入和查找效率较高，但比 HashMap 稍慢。

用法：

TreeMap<String, Integer> map = new TreeMap<>();
map.put("Apple", 1);
map.put("Banana", 2);

5. 集合遍历方式

迭代器（Iterator）

特点：
- 提供统一的遍历方式。
- 可以在遍历过程中安全地修改集合。

用法：

List<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    System.out.println(item);
}

增强 for 循环

特点：
- 语法简洁。
- 适用于所有实现了 Iterable 接口的集合。

用法：

List<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");

for (String item : list) {
    System.out.println(item);
}

二.并发编程

1. 多线程基础

1.1 线程的创建

继承 Thread 类：

创建一个继承自 Thread 类的子类，并重写 run 方法。

示例代码：

class MyThread extends Thread {
    @Override
    public void run() {
        System.out.println("Thread is running");
    }
}

public class Main {
    public static void main(String[] args) {
        MyThread thread = new MyThread();
        thread.start();
    }
}

实现 Runnable 接口：

创建一个实现 Runnable 接口的类，并实现 run 方法。

示例代码：

class MyRunnable implements Runnable {
    @Override
    public void run() {
        System.out.println("Thread is running");
    }
}

public class Main {
    public static void main(String[] args) {
        Thread thread = new Thread(new MyRunnable());
        thread.start();
    }
}

1.2 线程状态

新建：线程对象已创建，但尚未开始执行。
就绪：线程已经准备好运行，等待 CPU 调度。
运行：线程正在执行。
阻塞：线程被阻塞，无法继续执行，如等待 I/O 操作完成。
死亡：线程执行完毕或因异常终止。

2. 线程同步

2.1 synchronized 关键字

定义：synchronized 关键字用于实现线程同步，确保同一时间只有一个线程可以访问某个方法或代码块。

使用方式：

同步方法：

public synchronized void method() {
    // 同步代码块
}

同步代码块：

synchronized (this) {
    // 同步代码块
}

2.2 Lock 接口

定义：Lock 接口提供了比 synchronized 更灵活的锁机制，支持可重入、公平锁、非阻塞锁等。
常用实现类：
- ReentrantLock：可重入锁。
- ReentrantReadWriteLock：读写锁。

示例代码：

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Counter {
    private int count = 0;
    private final Lock lock = new ReentrantLock();

    public void increment() {
        lock.lock();
        try {
            count++;
        } finally {
            lock.unlock();
        }
    }

    public int getCount() {
        return count;
    }
}

3. 线程通信

3.1 wait()、notify()、notifyAll() 方法

定义：这些方法用于线程间的通信，通常在同步代码块中使用。
使用方式：
- wait()：使当前线程等待，释放锁。
- notify()：唤醒一个等待的线程。
- notifyAll()：唤醒所有等待的线程。

示例代码：

public class ProducerConsumer {
    private final Object lock = new Object();
    private boolean flag = false;

    public void produce() {
        synchronized (lock) {
            while (flag) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            System.out.println("Producing...");
            flag = true;
            lock.notify();
        }
    }

    public void consume() {
        synchronized (lock) {
            while (!flag) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            System.out.println("Consuming...");
            flag = false;
            lock.notify();
        }
    }
}

4. 线程安全

4.1 常见的线程安全问题

竞态条件：多个线程同时访问和修改同一个共享资源，导致结果不一致。
死锁：两个或多个线程互相等待对方释放资源，导致所有线程都无法继续执行。
活锁：线程反复尝试执行某个操作，但由于条件不满足，始终无法成功。

4.2 解决方法

使用 synchronized 关键字：确保同一时间只有一个线程可以访问共享资源。
使用 Lock 接口：提供更灵活的锁机制，支持可重入、公平锁等。
使用 volatile 关键字：确保变量的可见性和有序性。
使用 Atomic 变量：提供原子操作，避免竞态条件。

5. 并发工具类

5.1 ConcurrentHashMap

定义：线程安全的哈希表，支持高并发读写操作。
使用场景：适用于多线程环境下需要频繁读写的 Map。

示例代码：

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentMapExample {
    private final ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

    public void put(String key, int value) {
        map.put(key, value);
    }

    public Integer get(String key) {
        return map.get(key);
    }
}

5.2 CountDownLatch

定义：计数器，用于等待多个线程完成某个操作后再继续执行。
使用场景：适用于多个线程并行执行，主调线程需要等待所有子线程完成后再继续执行。

示例代码：

import java.util.concurrent.CountDownLatch;

public class CountDownLatchExample {
    public static void main(String[] args) throws InterruptedException {
        CountDownLatch latch = new CountDownLatch(3);

        for (int i = 0; i < 3; i++) {
            new Thread(() -> {
                System.out.println(Thread.currentThread().getName() + " is running");
                latch.countDown();
            }).start();
        }

        latch.await();
        System.out.println("All threads have finished");
    }
}

5.3 CyclicBarrier

定义：循环屏障，用于等待多个线程到达一个屏障点后再继续执行。
使用场景：适用于多个线程需要多次同步的情况。

示例代码：

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;

public class CyclicBarrierExample {
    public static void main(String[] args) {
        CyclicBarrier barrier = new CyclicBarrier(3, () -> {
            System.out.println("All threads have reached the barrier");
        });

        for (int i = 0; i < 3; i++) {
            new Thread(() -> {
                System.out.println(Thread.currentThread().getName() + " is running");
                try {
                    barrier.await();
                } catch (InterruptedException | BrokenBarrierException e) {
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread().getName() + " has passed the barrier");
            }).start();
        }
    }
}

6. 线程池

6.1 Executor 框架

定义：Java 提供的一组线程池管理工具，简化了线程的管理和调度。
常用类：
- Executor：执行提交的任务。
- ExecutorService：扩展了 Executor，提供了管理线程池的方法。
- ThreadPoolExecutor：线程池的核心实现类。
- ScheduledExecutorService：支持定时任务的线程池。

6.2 线程池的创建和使用

创建线程池：

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ThreadPoolExample {
    public static void main(String[] args) {
        ExecutorService executor = Executors.newFixedThreadPool(5);

        for (int i = 0; i < 10; i++) {
            int taskId = i;
            executor.submit(() -> {
                System.out.println("Task " + taskId + " is running on " + Thread.currentThread().getName());
            });
        }

        executor.shutdown();
    }
}

三.JVM 原理

1. JVM 内存结构

1.1 堆（Heap）

定义：堆是 JVM 中最大的一块内存区域，用于存放对象实例。
作用：所有的对象实例和数组都在堆上分配内存。
特点：堆是垃圾收集器管理的主要区域，可以分为新生代和老年代。

1.2 栈（Stack）

定义：每个线程都有一个私有的栈，用于存储局部变量、方法参数、操作数栈等。
作用：方法的调用和返回都在栈上进行。
特点：栈的生命周期与线程相同，栈中的数据是线程私有的。

1.3 方法区（Method Area）

定义：方法区用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。
作用：存储类的结构信息，如运行时常量池、字段和方法数据、构造函数和普通方法的字节码内容。
特点：方法区是全局共享的，JDK 8 之后，方法区被元空间（Metaspace）替代。

1.4 程序计数器（Program Counter Register）

定义：程序计数器是一块较小的内存空间，用于记录当前线程所执行的字节码指令地址。
作用：决定下一条执行的字节码指令。
特点：每个线程都有一个独立的程序计数器，是线程私有的。

2. 垃圾回收

2.1 垃圾回收算法

标记清除（Mark-Sweep）：
- 定义：首先标记出所有需要回收的对象，然后统一回收。
- 特点：会产生内存碎片，影响后续的内存分配。
标记整理（Mark-Compact）：
- 定义：在标记清除的基础上，将存活的对象移动到内存的一端，消除内存碎片。
- 特点：减少了内存碎片，但增加了整理成本。
复制算法（Copying）：
- 定义：将内存分为两个相等的区域，每次只使用其中一个区域，当一个区域用完后，将存活的对象复制到另一个区域。
- 特点：简单高效，但浪费了一半的内存空间。

2.2 垃圾回收器

Serial 收集器：
- 定义：单线程的垃圾收集器，适用于客户端模式下的简单应用。
ParNew 收集器：
- 定义：多线程的垃圾收集器，是 Serial 收集器的多线程版本。
Parallel Scavenge 收集器：
- 定义：注重吞吐量的垃圾收集器，适合科学计算等后台计算密集型应用。
CMS 收集器：
- 定义：低延迟的垃圾收集器，适用于对响应时间要求较高的应用。
G1 收集器：
- 定义：分区收集器，兼顾吞吐量和延迟，适用于大内存的服务器应用。

3. 类加载机制

3.1 类加载过程

加载（Loading）：
- 定义：通过类的全限定名获取其二进制字节流，将字节流转换成方法区的数据结构，在内存中生成一个代表该类的 java.lang.Class 对象。
连接（Linking）：
- 验证（Verification）：确保 Class 文件的字节流中包含的信息符合当前虚拟机的要求。
- 准备（Preparation）：为类的静态变量分配内存，并设置默认初始值。
- 解析（Resolution）：将类中的符号引用替换为直接引用。
初始化（Initialization）：
- 定义：执行类的初始化代码，包括静态变量赋值和静态代码块。

3.2 双亲委派模型

定义：类加载器在加载类时，先委托父类加载器进行加载，如果父类加载器无法加载，则由子类加载器进行加载。
作用：保证类的唯一性，防止类的重复加载，确保类的加载顺序。

4. JVM 原理与调优

4.1 JVM 内存模型

堆：主要存储对象实例，分为新生代和老年代。
栈：存储局部变量、方法参数等，每个线程有一个独立的栈。
方法区：存储类的结构信息，如运行时常量池、字段和方法数据。
程序计数器：记录当前线程所执行的字节码指令地址。

4.2 类加载机制

加载：获取类的二进制字节流，生成 java.lang.Class 对象。
连接：验证、准备、解析。
初始化：执行类的初始化代码。

4.3 垃圾回收

算法：标记清除、标记整理、复制算法。
收集器：Serial、ParNew、Parallel Scavenge、CMS、G1。

4.4 JVM 参数调优

堆内存调优：
- -Xms：设置初始堆内存大小。
- -Xmx：设置最大堆内存大小。
- -Xmn：设置新生代大小。
垃圾回收器选择：
- -XX:+UseSerialGC：使用 Serial 收集器。
- -XX:+UseParNewGC：使用 ParNew 收集器。
- -XX:+UseParallelGC：使用 Parallel Scavenge 收集器。
- -XX:+UseConcMarkSweepGC：使用 CMS 收集器。
- -XX:+UseG1GC：使用 G1 收集器。

4.5 JVM 诊断工具

jstat：监控 JVM 的性能数据，如垃圾回收情况。
jmap：生成堆转储快照，用于分析内存使用情况。
jstack：生成线程转储快照，用于分析线程状态。

四.数据结构与算法

1. 数据结构

1.1 数组

定义：一种线性数据结构，元素按顺序存储在连续的内存空间中。
特点：访问速度快，插入和删除操作较慢。
适用场景：适用于频繁访问元素的场景，如缓存、数据库索引等。

1.2 链表

定义：一种线性数据结构，元素通过指针链接在一起，不连续存储。
特点：插入和删除操作快，访问速度较慢。
适用场景：适用于频繁插入和删除元素的场景，如 LRU 缓存、文件系统等。

1.3 栈

定义：一种只能在一端进行插入或删除的线性表，遵循后进先出（LIFO）原则。
特点：操作简单，适用于回溯、括号匹配等场景。
适用场景：函数调用、表达式求值、浏览器历史记录等。

1.4 队列

定义：一种只能在一端进行插入，在另一端进行删除的线性表，遵循先进先出（FIFO）原则。
特点：操作简单，适用于任务调度、消息传递等场景。
适用场景：打印任务队列、生产者消费者模型等。

1.5 树

二叉树：
- 定义：每个节点最多有两个子节点的树。
- 特点：结构简单，适用于查找、排序等场景。
- 适用场景：文件系统、二叉搜索树等。
平衡树：
- 定义：一种自平衡的二叉搜索树，确保树的高度尽可能小。
- 特点：插入、删除、查找操作的时间复杂度为 O(log n)。
- 适用场景：数据库索引、符号表等。
红黑树：
- 定义：一种自平衡的二叉搜索树，通过颜色标记节点来保持平衡。
- 特点：插入、删除、查找操作的时间复杂度为 O(log n)。
- 适用场景：STL 中的 map 和 set、Linux 内核中的进程调度等。

1.6 图

定义：由顶点和边组成的非线性数据结构。
特点：表示复杂关系，适用于社交网络、地图导航等场景。
适用场景：社交网络、地图导航、网络路由等。

2. 算法

2.1 排序算法

冒泡排序：
- 定义：通过多次遍历数组，将较大的元素逐步移到数组末尾。
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
快速排序：
- 定义：通过递归划分数组，将小于基准值的元素放在左边，大于基准值的元素放在右边。
- 时间复杂度：平均 O(n log n)，最坏 O(n^2)
- 空间复杂度：O(log n)
归并排序：
- 定义：通过递归将数组分成两部分，分别排序后再合并。
- 时间复杂度：O(n log n)
- 空间复杂度：O(n)