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

---

一.集合框架

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 {@Overridepublic 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 {@Overridepublic 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)

2.2 搜索算法

• 线性搜索：
  • 定义：从头到尾逐个检查数组中的元素。
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
• 二分搜索：
  • 定义：在有序数组中通过不断缩小搜索范围来查找目标值。
  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

2.3 贪心算法

• 定义：在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的。
• 特点：简单高效，但不一定能得到全局最优解。
• 适用场景：活动选择问题、霍夫曼编码等。

2.4 动态规划

• 定义：通过将问题分解成子问题，并保存子问题的解以避免重复计算，从而解决问题。
• 特点：适用于具有重叠子问题和最优子结构性质的问题。
• 适用场景：背包问题、最长公共子序列等。

2.5 分治算法

• 定义：将问题分解成若干个规模较小的子问题，递归地解决这些子问题，再将子问题的解合并成原问题的解。
• 特点：适用于可以分解成独立子问题的问题。
• 适用场景：快速排序、归并排序等。