目 录CONTENT
以下是
yilee
的文章
-
2、排序和顺序统计量 ## 文章摘要 本文系统介绍了排序与顺序统计量的核心算法，涵盖以下四部分内容： **1. 排序算法概览**：明确了排序问题的输入输出定义，区分了比较排序（如插入、归并、堆、快速排序）与非比较排序（计数、基数、桶排序）。通过决策树模型证明比较排序的最坏时间下界为 $O(n\log n)$，而特定条件下非比较排序可达 $O(n)$。 **2. 堆排序与优先队列**：堆是一种近似完全二叉树结构，分为最大堆和最小堆。核心操作包括 MAX-HEAPIFY（$O(\log n)$）维护堆性质、BUILD-MAX-HEAP（$O(n)$）构建最大堆，HEAPSORT（$O(n\log n)$）通过反复提取最大值实现排序。优先队列基于堆实现了插入、取最大值、删除最大值及关键字增加等操作。 **3. 快速排序**：采用分治策略，通过 PARTITION 划分子数组并递归排序。最坏情况 $O(n^2)$、最好/平均情况 $O(n\log n)$。随机化版本通过随机选取主元有效规避最坏情况。 **4. 线性时间排序与选择**：计数排序通过计数小于每个元素的个数直接定位，时间 $O(n+k)$；基数排序按位进行稳定的子排序，时间 $O(d(n+k))$；桶排序利用均匀分布假设，平均 $O(n)$。顺序统计量问题可通过随机化选择算法在 $O(n)$ 时间内找到第 $i$ 小元素。 -
4、高级设计和分析技术 本文主要介绍了算法设计与分析中的三种高级技术：动态规划、贪心算法和摊还分析。 **动态规划**适用于存在重叠子问题和最优子结构的最优化问题。文章详细剖析了钢条切割、矩阵链乘法、最长公共子序列和最优二叉搜索树四个经典案例，展示了通过“自底向上”或“带备忘的自顶向下”方法将指数级复杂度降至多项式级（如$O(n^2)$或$O(n^3)$）的过程。 **贪心算法**则通过每步做出局部最优选择来期望获得全局最优解，通常效率更高。文章以活动选择问题为例，阐述了其核心性质——贪心选择性质，并通过0-1背包与分数背包的对比，揭示了贪心算法的适用边界。最后，文章还利用贪心思想讲解了赫夫曼编码的构造方法。
-
-
-
12、Java 内存模型与线程 ## 摘要 本章围绕**Java内存模型（JMM）**与**线程机制**展开，核心内容涵盖以下几方面： **1. 硬件背景**：由于处理器与内存速度差异巨大，现代计算机引入高速缓存，但也引入了缓存一致性问题；处理器和JIT编译器还可能进行指令重排序优化。 **2. Java内存模型**：JMM将变量存储在主内存中，每条线程拥有工作内存（主内存副本），线程间通过主内存交互。定义了lock、unlock、read、load、use、assign、store、write共8种原子操作及相应规则，规范了内存访问行为。 **3. volatile关键字**：具备两大语义——保证变量对所有线程的**可见性**和**禁止指令重排序**，但并不保证复合操作的原子性。此外，long/double非原子性协定在实际中几乎不影响开发。 **4. 并发三大特性**：**原子性**（基本读写原子，更大范围靠synchronized）、**可见性**（volatile、synchronized、final）、**有序性**（volatile和synchronized保证）。**先行发生原则**提供了判断操作顺序的规则，是衡量并发安全性的依据。 **5. 线程实现与调度**：Java线程在JDK 1.2后映射为操作系统原生线程（一对一模型），采用**抢占式调度**，可通过优先级"建议"调度但最终由OS决定。线程有新建、运行、无限期等待、限期等待、阻塞、终止六种状态及转换关系。 总之，本章从底层原理出发，系统阐述了JMM如何保证并发安全，以及Java线程的实现机制，为编写高效并发程序奠定了理论基础。
-
11、晚期（运行期）优化 ## 摘要 本章介绍了JVM运行期（晚期）优化的核心机制——即时编译（JIT）。Java程序初始由解释器执行，当虚拟机探测到频繁执行的"热点代码"时，会将其编译为本地机器码以提升效率。 **热点探测**采用基于计数器的方式，通过方法调用计数器和回边计数器分别统计方法调用次数与循环体执行次数，超过阈值则触发编译。 **编译架构**上，HotSpot内置Client编译器（C1，注重编译速度）和Server编译器（C2，注重优化质量），并通过分层编译策略协同工作，在启动速度与执行效率间取得平衡。 **关键优化技术**包括：方法内联（最重要的优化，为其他优化奠定基础）、公共子表达式消除、数组边界检查消除，以及前沿的逃逸分析（据此可实现栈上分配、同步消除和标量替换）。 最后，本章对比了JIT与C/C++静态编译器的优劣：JIT受限于编译时间、动态类型安全和虚方法多态等，但得益于运行期性能监控信息，可进行激进优化，在动态性方面具有独特优势。
-
10、早期（编译期）优化 ## 第十章 早期（编译期）优化 — 摘要 本章系统讲解了 Java 前端编译器（以 Javac 为代表）的编译过程及 Java 语法糖的原理。 **Javac 编译流程**分为三大阶段：①**解析与填充符号表**：通过词法分析将源码字符流转为 Token，再经语法分析构建抽象语法树（AST），最后由 `Enter` 类填充符号表以登记符号地址与信息。②**插入式注解处理**：基于 JSR-269 规范，在编译期间可读取或修改 AST，若语法树被改动则重新循环处理，直至无修改为止。③**语义分析与字节码生成**：包含标注检查（如常量折叠）、数据与控制流分析、解语法糖（将泛型、自动装箱等还原为基础语法）以及最终由 `ClassWriter` 生成 `.class` 文件，同时完成 `<init>` 和 `<clinit>` 方法的收敛。 **语法糖**部分重点分析了泛型的类型擦除机制——运行时泛型信息被擦除，但元数据（如 `Signature` 属性）仍保留泛型签名，支持反射获取；自动装箱存在 `IntegerCache` 缓存陷阱（-128~127 范围内相同值对象相同）；条件编译通过常量 `if` 语句实现，仅限于语句块级别。 **实战**部分演示了编写插入式注解处理器，在编译期自动检查类、方法、字段的命名规范。 > **核心观点**：Javac 作为前端编译器，主要目标是提升编码效率与语法便利性；而真正影响运行性能的是虚拟机内置的后端即时编译器（JIT），它将字节码编译为本地机器码，是衡量 JVM 性能的关键指标。
-
9、类加载及执行于系统的案例与实战 ## 摘要 本文主要介绍了Java虚拟机中**类加载器架构**的两大典型案例及**字节码生成技术**的实际应用。 **1. Tomcat的正统类加载器架构**：为满足Web应用的类库隔离、共享、安全及JSP热部署需求，Tomcat自定义了多个类加载器（Common、Catalina、Shared、WebApp、Jsp），采用双亲委派模型，通过不同目录结构实现访问范围的精细控制。 **2. OSGi的灵活类加载器架构**：每个Bundle可声明导入导出包，加载器之间无固定委派关系，形成运行时确定的网状结构，实现模块级热插拔和精确的可见性控制，但也引入了死锁等风险。 **3. 字节码生成与动态代理**：Spring利用动态代理实现Bean增强，可在运行时动态生成代理类，无需预先编写代理代码，实现灵活的方法拦截。 **4. Retrotranslator跨越JDK版本**：通过ASM框架处理字节码，将JDK 1.5编译产物转换为可在1.4/1.3上运行的版本，主要模拟编译器改进和API增强两类新功能。
-
-
7、虚拟机类加裁机制 ## 摘要 本文系统介绍了Java虚拟机的类加载机制，涵盖类加载的全生命周期、各阶段详细过程及类加载器体系。 类从被加载到卸载经历**加载、连接（验证、准备、解析）、初始化、使用和卸载**七个阶段，其中初始化仅在遇到`new`、访问静态字段、调用静态方法、反射调用、初始化子类及指定主类等五种场景下触发。 - **加载**：通过全限定名获取二进制字节流，转化为方法区运行时数据结构，生成`Class`对象。字节流来源多样（ZIP、网络、动态生成等），非数组类的加载开发者可通过自定义类加载器控制。 - **验证**：包括文件格式、元数据、字节码和符号引用四方面校验，确保Class文件安全合规。 - **准备**：为静态变量分配内存并设零值，但`final static`常量会直接赋指定值。 - **解析**：将常量池中的符号引用替换为直接引用，支持运行时动态绑定。 - **初始化**：执行类构造器`<clinit>()`，合并静态变量赋值和静态代码块，虚拟机保证线程安全且父类先于子类初始化。 类加载器方面，**类与加载器共同确定类的唯一性**。Java采用**双亲委派模型**，加载请求自底向上委派至启动类加载器，保证核心类（如`Object`）的一致性。该模型曾因历史原因、SPI机制及热部署需求（如OSGi）而被"破坏"，分别通过重写`loadClass`、线程上下文类加载器和网状类加载结构来解决。
