去年读的电子版写的读书笔记兼目录，放出来温习一下😊

第 1 章 数组及其内存管理

1.1 数组初始化 p11

1.1.1 Java 数组是静态的 p11

  • 数组静态初始化、动态初始化的 sample p11

  • Java 数组是静态的，一旦数组初始化完成，数组元素的内存空间分配即结束，程序只能改变数组元素的值，而无法改变数组的长度。

  • 数组变量也是一种引用类型的变量，指向堆内存的数组对象。

  • JS 的数组可动态改变。

1.1.2 数组一定要初始化吗 p14

  • 只要让数组变量指向有效的数组对象即可。

1.1.3 基本类型数组的初始化 p16

  • 引用变量本质上只是一个指针，只要程序通过引用变量访问属性，或者通过引用变量来调用方法，该引用变量就会由它所引用的对象代替。

1.1.4 引用类型数组的初始化 p18

  • sample p18

1.2 使用数组 p21

1.2.1 数组元素就是变量 p21

1.2.2 没有多维数组 p23

第 2 章 对象及其内存管理

  • Java 内存管理分为两个方面：内存分配和内存回收。

  • 内存分配指创建 Java 对象时 JVM 为该对象在堆内存中所分配的内存空间；

  • 内存回收指当该 Java 对象失去引用变成垃圾时，JVM 的 GC 自动清理该对象，并回收该对象所占用的内存。

2.1 实例变量（非静态变量）和类变量（静态变量） p31

2.1.1 实例变量和类变量的属性 p32

  • 在同一个 JVM 内，每个类只对应一个 Class 对象。因此同一个 JVM 内的一个类的类变量只需一块内存空间；但实例变量有几个就需要几块内存空间。

  • sample p33

2.1.2 实例变量的初始化时机 p35

  • 非静态初始化块总是在构造器执行之前获得执行。

  • JDK 提供的 javap 工具，主要用于帮助开发者深入了解 Java 编译器的机制。 用法见 p38

2.1.3 类变量的初始化时机 p39

  • sample p39

2.2 父类构造器 p41

2.2.1 隐式调用和显式调用 p41

  • Java 对象时的初始化过程 sample p41

2.2.2 访问子类对象的实例变量 p43

  • 构造器只是负责对 Java 对象实例变量执行初始化（也就是赋初始值），在执行构造器代码之前，该对象所占的内存已经被分配出来了。

2.2.3 调用被子类重写的方法 p46

  • sample p46

2.3 父子实例的内存控制 p48

2.3.1 继承成员变量和继承方法的区别 p48

  • 对于一个引用类型的变量而言，当通过该变量访问它所引用的对象的实例变量时，该实例变量的值取决于声明该变量时的类型；当通过该变量来调用它所引用的对象的方法时，该方法行为取决于它所实际引用的对象的类型。

2.3.2 内存中子类实例 p51

  • 当程序创建一个子类对象时，系统不仅会为该类中定义的实例变量分配内存，也会为其父类中定义的所有实例变量分配内存，即使子类定义了与父类同名的实例变量。

2.3.3 父、子类的类变量 p56

2.4 final 修饰符 p57

2.4.1 final 修饰的变量 p57

  • 三个地方对 final 实例变量进行初始化 sample p58

  • 对于一个使用 final 修饰的变量而言，如果定义该 final 变量时就指定初始值，而且这个初始值可以在编译时就确定下来，那么这个 final 变量将不再是一个变量，系统会将其当成“宏变量”处理。

2.4.2 执行“宏替换”的变量 p62

  • 对于 final 实例变量而言，只有在定义该变量指定初始值才会有“宏变量”的效果。

2.4.3 final 方法不能被重写 p66

2.4.4 内部类中的局部变量 p68

  • Java 编译器要求被内部类访问的局部变量必须使用 final 修饰符修饰。

第 3 章 常见 Java 集合的实现细节 p72

3.1 Set 和 Map p73

  • 可以说，Map 集合是 Set 集合的扩展。

3.1.1 Set 和 Map 的关系 p73

  • Map 集合的所有 key 都具有 Set 集合的特征。

3.1.2 HashMap 和 HashSet p78

  • Java 集合实际上是多个引用变量所组成的集合，这些引用变量指向实际的 Java 对象。

  • 通常来说，HashMap 的实际容量总比 initialCapacity 大一些，除非指定的 initialCapacity 参数值恰好是 2 的 n 次方。所以在创建 HashMap 时将 initialCapacity 参数值指定为 2 的 n 次方，这样可以减少系统的计算开销。

  • HashMap 在底层将 key-value 对当成一个整体进行处理，这个整体就是一个 Entry 对象。

  • HashSet 只是封装了一个 HashMap 对象来存储所有的集合元素。所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

  • 测试掌握 HashMap 和 HashSet 集合的功能 sample p86

3.1.3 TreeMap 和 TreeSet p88

  • TreeSet 底层实际使用的存储容器就是 TreeMap。

  • TreeMap 采用一种“红黑树”的排序二叉树来保存 Map 中的每个 Entry——每个 Entry 都被当成红黑树的一个节点来对待。

  • TreeMap 中所有的 key 总是由小到大排列。

3.2 Map 和 List p94

3.2.1 Map 的 values()方法 p94

  • Map 的 values 方法并未返回一个 List 集合。返回的都是内部类的 Values 对象。

3.2.2 Map 和 List 的关系 p100

  • JavaScript 的对象有点类似于 Java 的 Map 的结构，也是由多个 key-value 对组成的。

  • JS 的 sample p101

3.3 ArrayList 和 LinkedList p101

  • List 集合主要有三个实现类：ArrayList、Vector、LinkedList

  • 程序中如果需要栈这种数据结构，推荐使用 Deque 实现类。从 JDK1.6 开始，Java 提供了一个 Deque 接口，并为该接口提供了一个 ArrayDeque 实现类。在无须线程安全的情况下，程序完全可以使用 ArrayDeque 来代替 Stack 类。

  • Deque 接口代表双端队列这种数据结构，双端队列既是队列也是栈。

3.3.1 Vector 和 ArrayList 的区别 p103

  • Vector 其实就是 ArrayList 的线程安全版本。

  • Vector 基本上已经被 ArrayList 所代替。

3.3.2 ArrayList 和 LinkedList 的实现差异 p106

  • LinkedList 本质上就是一个双向链表，但它不仅实现了 List 接口，还实现了 Deque 接口。

  • ArrayList、LinkedList 的一些源码。p106

3.3.3 ArrayList 和 LinkedList 的性能分析及适用场景 p110

3.4 Iterator 迭代器 p110

3.4.1 Iterator 实现类与迭代器模式 p111

  • 对于 Iterator 迭代器而言，它只是一个接口。Java 要求各种集合都提供一个 Iterator()方法，该方法可以返回一个 Iterator 用于遍历该集合中的元素，至于返回的 Iterator 到底是哪种实现类，程序并不关心，这就是典型的“迭代器模式”。

3.4.2 迭代时删除指定元素 p112

第 4 章 Java 的内存回收 p116

4.1 Java 引用的种类 p117

  • Java 内存管理包括内存分配和内存回收两个方面。

4.1.1 对象在内存中的状态 p117

  • 对象的三种状态：可达状态、可恢复状态、不可达状态。

  • 只有当一个对象处于不可达状态时，系统才会真正回收该对象所占有的资源。

4.1.2 强引用 p120

  • 强引用是造成 Java 内存泄漏的主要原因之一。

4.1.3 软引用 p120

  • 通过 SoftReference 类来实现。对于只有软引用的对象而言，当系统内存空间足够时，它不会被系统回收，程序也可使用该对象；当系统内存空间不足时，系统将会回收它。

4.1.4 弱引用 p123

  • 通过 WeakReference 类来实现。对于只有弱引用的对象而言，当系统垃圾回收机制运行时，不管系统内存是否足够，总会回收该对象所占用的内存。

  • 当程序有大量的 Java 对象需要使用弱引用来引用时，可以考虑使用 WeakHashMap 来保存它们。

4.1.5 虚引用 p127

  • 虚引用的主要作用就是跟踪对象被垃圾回收的状态。不能单独使用，必须和引用队列（ReferenceQueue）联合使用。

4.2 Java 的内存泄漏 p128

4.3 垃圾回收机制 p132

4.3.1 垃圾回收的基本算法 p132

  • 对于一个垃圾回收器的设计算法来说，大致有如下可供选择的设计：串行回收和并行回收；并发执行和应用程序停止；压缩/不压缩和复制。

  • 现行的垃圾回收器用分代的方式来采用不同的回收设计。分代的基本思路是根据对象生存时间的长短，把堆内存分成三代：Young,Old,Permanent。

4.3.2 堆内存的分代回收 p134

4.3.3 与垃圾回收相关的附加选项 p136

* 4.3.4 常见的垃圾回收器 p136

  • 1、串行回收器；2、并行回收器；3、并行压缩回收器；4、并发标识-清理回收器（CMS）

4.4 内存管理小技巧 p140

4.4.1 尽量使用直接量 p141

4.4.2 使用 StringBuilder 和 StringBuffer 进行字符串连接 p141

4.4.3 尽早释放无用对象引用 p141

  • 大部分时候程序无须将局部引用变量显式设为 null。

4.4.4 尽量少用静态变量 p142

4.4.5 避免在经常调用的方法、循环中创建 Java 对象 p142

4.4.6 缓存经常使用的对象 p143

  • 开源的缓存实现有 OSCache、Ehcache，它们大都实现了 FIFO、MRU 等常见的缓存算法。

4.4.7 尽量不要使用 finalize 方法 p143

4.4.8 考虑使用 SoftReference p144

第 5 章 表达式中的陷阱 p145

5.1 关于字符串的陷阱 p146

5.1.1 JVM 对字符串的处理 p146

  • 对于 Java 程序中的字符串直接量，JVM 会使用一个字符串池来保存它们。

  • 当程序中需要使用字符串、基本类型包装类实例时，应该尽量使用字符串直接量、基本类型值的直接量，这样能保证较好的性能。

5.1.2 不可变的字符串 p149

  • 当一个 String 对象创建完成后，该 String 类里包含的字符序列就被固定下来，以后永远都不能改变。

  • System 提供的 identifyHashCode()静态方法用于获取某个对象唯一的 hashCode 值，这个方法的返回值与该类是否重写了 hashCode()方法无关。

5.1.3 字符串比较 p151

5.2 表达式类型的陷阱 p153

5.2.1 表达式类型的自动提升 p153

  • 当一个算术表达式包含多个基本类型的值时，整个算术表达式的数据类型将自动提升。

5.2.2 复合赋值运算符的陷阱 p154

  • 复合赋值运算符包含了一个隐式类型转换，a+=5 等价于 a=(a 的类型)(a+5)

  • 复合赋值运算的使用注意点：p156

5.2.3 Java7 新增的二进制整数 p156

5.3 输入法导致的陷阱 p157

5.4 注释字符必须合法 p158

5.5 转义字符的陷阱 p158

5.5.1 慎用字符的 Unicode 转义形式 p158

5.5.2 中止行注释的转义字符 p159

5.6 泛型可能引起的错误 p160

5.6.1 原始类型变量的赋值 p160

  • 把原始类型的变量赋给带泛型类型的变量时的 sample p160

5.6.2 原始类型带来的擦除 p162

  • 将一个 List类型的对象转型为 List，则该 List 对集合元素的类型检查变成了类型变量的上限（即 Object）。

  • 当把一个带泛型信息的 Java 对象赋给不带泛型信息的变量时，Java 程序会发生擦除，这种擦除不仅会擦除使用该 Java 类时传入的类型实参，而且会擦除所有的泛型信息，也就是擦除所有尖括号里的信息。p163

5.6.3 创建泛型数组的陷阱 p164

5.7 正则表达式的陷阱 p166

5.8 多线程的陷阱 p167

5.8.1 不要调用 run 方法 p167

5.8.2 静态的同步方法 p169

  • 任何线程进入同步方法、同步代码块之前，必须先获取同步方法、同步代码块对应的同步监视器。

5.8.3 静态初始化块启动新线程执行初始化 p171

5.8.4 注意多线程执行环境 p176

  • 将线程不安全的类改成线程安全的形式 p179

第 6 章 流程控制的陷阱 p181

6.1 switch 语句陷阱 p182

6.1.1 default 分支永远会执行吗 p182

6.1.2 break 的重要性 p183

  • 输入 javac -X 命令查看支持的全部扩展选项

6.1.3 Java7 增强的 switch 表达式 p185

6.2 标签引起的陷阱 p186

6.3 if 语句的陷阱 p187

6.3.1 else 隐含的条件 p187

  • 使用 if…else 语句有一条基本规则：总是优先把包含范围小的条件放在前面处理。

6.3.2 小心空语句 p190

6.4 循环体的花括号 p191

6.4.1 什么时候可以省略花括号 p191

6.4.2 省略花括号的危险 p192

  • 大部分时候，如果循环体只包含一条语句，那么就可以省略循环体的花括号；但如果循环体只包含一条局部变量定义语句，那依然不可以省略循环体的花括号。

6.5 for 循环的陷阱 p194

6.5.1 分号惹的祸 p194

6.5.2 小心循环计数器的值 p197

6.5.3 浮点数作循环计数器 p197

6.6 foreach 循环的循环计数器 p199

第 7 章 面向对象的陷阱 p202

7.1 instanceof 运算符的陷阱 p203

  • 前一个操作数为引用类型的变量，后一个操作数通常为一个类或接口。

  • 使 null 调用 instanceof 运算符时返回 false 是非常有用的行为。

7.2 构造器的陷阱 p207

7.2.1 构造器之前的 void p207

7.2.2 构造器创建对象吗 p208

  • 构造器并不会创建 Java 对象，构造器只是负责执行初始化。

  • 以下 2 种方式创建 Java 对象无需使用构造器：使用反序列化的方式恢复 Java 对象；使用 clone 方法复制 Java 对象。

  • 为单例类提供 readResolve()方法，保证反序列化时得到已有的 Java 实例。例 p210

7.2.3 无限递归的构造器 p212

7.3 持有当前类的实例 p214

  • 对于一个 Java 类而言，它的一个实例变量持有当前类的另一个实例是被允许的。

7.4 到底调用哪个重载的方法 p215

7.5 方法重写的陷阱 p218

7.5.1 重写 private 方法 p218

7.5.2 重写其他访问权限的方法 p219

7.6 非静态内部类的陷阱 p220

7.6.1 非静态内部类的构造器 p220

  • 非静态内部类必须寄生在外部类的实例中，没有外部类的对象，就不可能产生非静态内部类的对象。因此，非静态内部类不可能有无参数的构造器——即使系统为非静态内部类提供一个默认的构造器，这个默认的构造器也需要一个外部类形参。

  • 系统在编译阶段总会为非静态内部类的构造器增加一个参数，非静态内部类的构造器的第一个形参总是外部类。

7.6.2 非静态内部类不能拥有静态成员 p222

7.6.3 非静态内部类的子类 p223

  • 非静态内部类在外部类的内部派生子类是安全的。

  • 如果条件允许，推荐多使用静态内部类，而不是非静态内部类。对于静态内部类来说，外部类相当于它的一个包。

7.7 static 关键字 p224

7.7.1 静态方法属于类 p224

7.7.2 静态内部类的限制 p226

  • 静态内部类不能访问外部类的非静态成员。

7.8 native 方法的陷阱 p226

  • 对于 native 方法而言，Java 不会为该方法提供实现体。

  • native 方法通常需要借助 C 语言完成，实现步骤：p227

第 8 章 异常处理的陷阱 p229

8.1 正确关闭资源的方式 p230

  • 实例代码 p232

8.1.2 使用 Java7 增强的 try 语句关闭资源 p233

  • 实例代码 p234

8.2 finally 块的陷阱 p235

8.2.1 finally 的执行规则 p235

  • 实例代码：为系统注册了一个关闭钩子，关闭钩子负责在程序退出时回收系统资源。 p236

8.2.2 finally 块和方法返回值 p236

8.3 catch 块的方法 p238

8.3.1 catch 块的顺序 p238

  • 捕捉父类异常的 catch 块都应该排在捕捉子类异常的 catch 块之后（先捕小异常再捕大异常），否则将出现编译错误。

8.3.2 不要用 catch 代替流程控制 p240

8.3.3 只有 catch 可能抛出的异常 p241

8.3.4 做点实际的修复 p244

8.4 继承得到的异常 p246

8.5 Java7 增强的 throw 语句 p247

第 9 章 线性表 p250

9.1 线性表概述 p251

9.1.1 线性表的定义及逻辑结构 p251

9.1.2 线性表的基本操作 p252

9.2 顺序存储结构 p252

  • 简单的顺序结构线性表的源代码。p254

9.3 链式存储结构 p257

  • 链式存储结构的线性表不会按线性的逻辑顺序来保存数据元素，它需要在每一个数据元素里保存一个引用下一个数据元素的引用。

9.3.1 单链表上的基本运算 p258

  • 单链表指的是每个节点只保留一个引用，该引用指向当前节点的下一个节点，没有引用指向头节点，尾节点的 next 引用为 null。

  • 链表和顺序表性能上的差异：顺序表在随机存取时性能很好；链表在插入、删除时性能很好。

9.3.2 循环链表 p264

  • 循环链表是一种首尾相接的链表。循环链表有一个显著特征：从链表的任一节点出发均可找到表中的其他所有节点。

9.3.3 双向链表 p265

  • 双向链表是为每个节点保留两个引用 prev 和 next。

  • 双向链表添加节点、删除节点的指针维护成本更大；在搜索节点、删除指定索引处的节点具有较好的性能。

9.4 线性表的分析 p271

9.4.1 线性表的实现分析 p271

  • 线性表的顺序和链式两种实现的优势 p271

9.4.2 线性表的功能 p272

第 10 章 栈和队列 p274

10.1 栈 p275

  • 栈是一种特殊的线性表，这种线性表只能在固定一端（通常尾端）进行插入、删除操作。

10.1.1 栈的基本定义 p275

  • 栈就是一种后进先出（LIFO）的线性表。

10.1.2 栈的常用操作 p276

  • 栈的标志性方法：入栈、出栈、访问栈顶元素。

  • 栈同样既可采用顺序结构或链式结构存储栈内元素。

10.1.3 栈的顺序存储结构及实现 p276

  • 顺序栈的代码实现 p277

10.1.4 栈的链式存储结构及实现 p281

  • 链栈的代码实现 p282

10.1.5 Java 集合中的栈 p284

  • java.util.Stack：一个普通的顺序栈，底层基于数组实现，线程安全。

  • java.util.LinkedList：一个双端链表。代表栈的链式实现，线程不安全。

10.2 对列 p284

  • 队列使用固定的一端来插入数据元素，另一端只用于删除元素。

10.2.1 队列的基本定义 p284

  • 队列是一种特殊的线性表，只允许在表的前端进行删除，只允许在表的后端进行插入。先进先出（FIFO）的线性表。

10.2.2 队列的常用操作 p285

  • 队列的标志性方法：加入元素、删除元素、访问队列的前端元素。

  • 队列同样既可采用顺序结构或链式结构存储队列内元素。

10.2.3 队列的顺序存储结构及实现 p285

  • 顺序队列的代码实现 p286

10.2.4 循环队列 p289

  • 循环队列是首尾相连的队列：当 front、rear 变量值达到底层数组的 capacity-1 之后，再前进一位就自动变成 0。

  • 循环队列的代码实现 p290

10.2.5 队列的链式存储结构及实现 p293

  • 链队列的代码实现 p294

  • 链队列不会出现队列“满”的情形，因此程序可以不受任何限制地向链队列中添加元素。

10.2.6 Java 集合中的队列 p296

  • 从 JDK1.5 开始，Java 集合框架中提供了一个 Queue 接口，该接口代表了一个队列，实现该接口的类可以当成队列使用。

  • Queue 接口里定义的 6 个方法 p297

  • Dequeue 接口是一个双端队列。

10.3 双端队列 p297

  • 双端队列（Dequeue）可以在两端同时进行插入、删除操作。

  • Dequeue 既可当成队列使用，也可当成栈使用。

  • JDK 为 Dequeue 提供了 ArrayDequeue（顺序存储结构的双端队列）、LinkedList（链式存储结构的双端队列）两个常见的实现类。

  • LinkedList 既可当成线性表、也可当成栈、还可当成队列，但对大部分程序而言，使用 ArrayList、ArrayDequeue 的性能比 LinkedList 更好。

第 11 章 树和二叉树 p299

11.1 树的概述 p300

  • 树是一种非线性结构。

11.1.1 树的定义和基本术语 p300

  • 与树有关的术语 p301

11.1.2 树的基本操作 p301

  • 实现树的数据结构有 2 种选择：1）父节点表示法：每个子节点都记录它的父节点；2）子节点链表示法：每个非叶子节点通过一个链表来记录它所有的子节点。

11.1.3 父节点表示法 p302

  • 采用父节点表示法的代码实现 p303

  • 父节点表示法的特点是：每个节点都可以快速找到它的父节点，但如果要找某个节点的所有子节点就比较麻烦，程序要遍历整个节点数组。

11.1.4 子节点链表示法 p305

  • 子节点链表示法的代码实现 p306

  • 子节点链表示法的特点是：每个节点都可以快速找到它的所有子节点，但如果要找某个节点的父节点则比较麻烦，程序要遍历整个节点数组。

11.2 二叉树 p309

11.2.1 二叉树的定义和基本概念 p309

  • 二叉树指的是每个节点最多只能有两个子树的有序数。

  • 如果一棵二叉树除最后一层外，其余层的所有节点都是满的，并且最后一层或者是满的，或者仅在右边缺少若干连续的节点，则此二叉树就是完全二叉树。

  • 满二叉树是一种特殊的完全二叉树。当完全二叉树最后一层的所有节点都是满的时，这棵完全二叉树就变成了满二叉树。

11.2.2 二叉树的基本操作 p311

  • 要实现二叉树的数据结构，有三种选择：顺序存储；二叉链表存储；三叉链表存储。

11.2.3 二叉树的顺序存储 p312

  • 当使用数组来存储二叉树的所有节点时可能会产生一定的空间浪费，如果该二叉树是完全二叉树，就不会有任何空间浪费了；但如果该二叉树的所有节点都只有右子节点，那么会产生相当大的空间浪费。

  • 顺序存储的二叉树的代码实现 p313

11.2.4 二叉树的二叉链表存储 p315

  • 思想为每个节点增加 left、right 两个指针，分别引用该节点的左右两个子节点。

  • 二叉链表的代码实现 p316

  • 这种二叉链表的存储方式在遍历树节点时效率不高，指定节点访问其父节点时也比较困难。

11.2.5 二叉树的三叉链表存储 p319

  • 三叉链表是在二叉链表上增加了 parent 指针。

  • 三叉链表的代码实现 p319

11.3 遍历二叉树 p322

  • 遍历顺序结构的二叉树直接遍历底层数组即可；遍历链表存储的二叉树有 2 种：深度优先遍历、广度优先遍历。

  • 深度优先遍历算法分为：前序遍历（DLR）、中序遍历(LDR)、后续遍历(LRD)

11.3.1 先序遍历 p323

11.3.2 中序遍历 p323

11.3.3 后序遍历 p324

11.3.4 广度优先（按层）遍历 p325

  • 广度优先遍历的代码实现 p325

11.4 转换方法 p325

11.4.1 森林、数和二叉树的转换 p326

11.4.2 树的链表存储 p327

11.5 哈夫曼数 p327

11.5.1 哈夫曼树的定义和基本概念 p328

  • 带权路径最小的二叉树被称为哈夫曼数或最优二叉树。

11.5.2 创建哈夫曼树 p328

11.5.3 哈夫曼编码 p331

11.6 排序二叉树 p332

  • 排序二叉树的性质：左子树上所有节点的值均小于它的根节点的值；右子数上所有节点的值均大于它的根节点的值；左右子树也分别为排序二叉树。

  • 排序二叉树的代码实现 p335

11.7 红黑树 p340