复制 (Copying GC) 算法最早由 Marvin Lee Minsky 于1963年在 A LISP Garbage Collector Algorithm Using Serial Secondary Storage 中提出。

复制算法的基本思想很简单，就是把整个堆空间一分为二，每次只使用一半的空间用于分配：

• 正在使用的空间叫做 From 空间，空置的另一半称为 To 空间；
• 执行 GC 时，将 From 空间的活动对象都复制到 To 空间，然后对整个 From 空间进行回收；
• 复制完成后，将 From 空间和 To 空间交换，即原来的 From 空间变成了 To 空间，原来的 To 空间变成了 From 空间，直到下一次 GC，两个空间再次交换。

复制算法的一大特点就是它关注的是活动对象，而不像之前提到的标记-清除算法及引用计数法，都是遍历查找非活动对象。

什么是垃圾？不可能再被任何途径使用的对象。

由此很容易想到采用引用计数的方法：让对象记录下有多少其他对象引用自己。当引用数为0时，对象就被该作为垃圾回收了。

引用计数法

引用计数法的基本实现很简单，它不像标记-清除算法那样有明确的 GC 操作，而是在创建对象时和对指针进行更新时同时完成引用计数器的更新。

在介绍JVM中提供的垃圾收集器之前，我觉得有必要先补充一下关于垃圾回收（以下简称 GC）的理论知识 —— 垃圾回收算法（以下简称 GC 算法）。

GC 算法的基本类型并不多，概括起来大概就以下三种：

• 标记-清除算法 (Mark-Sweep) - 由 John McCarthy 1960 年在论文 Recursive functions of symbolic expressions and their computation by machine 中提出的标记-清除算法。
• 引用计数法 (Reference Counting) - 由 George E. Collins 1960 年在论文 A method for overlapping and erasure of lists 提出的引用计数法。
• 复制算法 (Copying) - 由 Marwin L.Minsky 1963 年在论文 A Lisp garbage collector algorithm using serial secondary storage 中提出的复制算法。

在这之后还出现了各种各样的 GC 算法，但究其根本都可以归纳为以上三种算法的组合和应用。

“你是什么垃圾？” ¯\_(ツ)_/¯

最近垃圾分类的话题那是相当火热，作为紧跟时代的程序员，我们不仅要开创格子衫的天下，还要走在时尚的最前沿～于是，我决定趁此机会，理一理Java中的内存管理与垃圾回收机制～

「辣鸡系列」正式开坑～(⊙v⊙)

在日常的 Java 开发中，有 JVM 的自动内存管理机制，我们一般也不怎么关注 Java 的内存分配和垃圾回收，因为不太容易出现内存泄漏和溢出的问题。不太容易并不代表不会，如果对 JVM 的内存管理不了解的话，一旦出现问题，debug 就不那么美妙了。

作为本系列的开篇，自然要从垃圾的来源 —— Java 的运行时数据区 (Run-Time Data Area) 讲起。

作为Java泛型系列的最后一篇笔记，我们来看看泛型(Generics)与数组(Array)和可变长参数(Varargs)之间的“恩怨情仇”～

关于三者，我们可以先列出如下事实：

• Java中不可以创建泛型数组
• Java可变长参数底层采用数组实现
• Java可变长参数可以为泛型类型

咦，好像有哪里怪怪的？

要弄清楚三者的关系，我们还得从泛型与数组的关系入手～

之前我们聊到了Java泛型的定义和应用，本篇笔记就来介绍一下Java中实现泛型的机制——类型擦除。

类型擦除主要做了以下几件事：

• 将所有泛型的类型参数替换成它们的bounds，如果是参数是unbounded，那么就替换成Object。这样生成的二进制码中就只有一般的类、接口和方法了
• 在必要时插入强制类型转换来保证类型安全
• 生成桥接方法来保证多态性

实际上，通过类型擦除，在编译过后的字节码文件中就不存在泛型类了，它们都被替换为原生类型(Raw Type)，并在相应的地方插入了强制转换。因此，对于Java而言在运行期ArrayList<Integer>和ArrayList<String>就是同一个类。

可以说，Java中的泛型更像一颗语法糖，而基于类型擦除实现的泛型又被称为“伪泛型”。

围观面试，正好有聊到Java泛型，自己的记忆也有点模糊，于是翻出了很久之前的零散笔记，重新整理了一波。

在引入泛型之前，在Java中使用Collections是一种非常容易出错的操作。举个例子：

1
2
3
4
5
6
7
8
9

List numbers = new ArrayList();
numbers.add(new Integer(10));
numbers.add("foo");    // 在不使用泛型的情况下，List中每个元素的类型都是Object，这意味着你可以往里面扔任何类型的对象
Integer sum = 0;
for (int i = 0; i < numbers.size(); i++) {
    Integer n = (Integer) numbers.get(i); // 必须使用强制转换将元素转换为我们想要的类型
    sum++;
}
System.out.println(sum);

那么问题来了，上面这段代码在编译时是不会报错的，然而，因为我们在List中插入了String类型，而在循环中我们默认每个元素都应该为Integer类型并做了强制转换，在运行时，程序就会抛出java.lang.ClassCastException异常。

我们都知道，错误越早发现，修复所需的代价越小，能在编译时发现错误就不要让它潜伏到运行时；而且，在没有泛型时，但凡使用Collections都逃不开强制转换，这也是一件非常痛苦的事情。

所幸，Java在5.0版本就引入了泛型。

赶在正月的尾巴上更一篇强行新年主题的笔记好了～

问题：新年到啦，又到了收获红包的节日，可是小猪猪的口袋有限，最多只能装下总重量不超过$W$的红包们。假设今年七大姑八大姨们一共准备了$n$个红包，每个红包的重量为$w_{i}$，价值为$v_{i}$。小猪猪应该挑哪些红包才能最合理地利用口袋的容量，获得价值最高的红包总额呢？

如果用数学公式来描述这个问题，可以将其转换为如下定义：

给定两个长度为$n$的正整数数组，分别为$\left[w_1, w_2, …, w_n \right]$和$\left[v_1, v_2, …, v_n \right]$, 以及一个最大容积$W\gt0$，我们想
$$最大化 \sum_{i=0}^n v_{i}x_{i}, 且有 \sum_{i=0}^n w_{i}x_{i} \leq W, x_{i} \in \lbrace0, 1 \rbrace$$

对于这$n$个物品，每个都有两个状态，放进背包或者被舍弃，$x_{i}=0$表示舍弃，$x_{i}=1$则表示获取。0-1 Knapsack中的0-1也是由此而来啦～

那么，要如何求解呢？

9102年来啦，怎么还是随手一戳就是盲点呢(:з」∠)

问题：给定一个链表(Linked List)，请判断这个链表中是不是有环(Cycle)。

在第一次遇到这个问题时，最容易想到的无脑解法就是挨个遍历节点，并将访问过的节点放入一个集合中，如果下一个访问的节点已经在这个集合中存在了，那么就说明环存在，绕回来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * 链表节点的定义
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public ListNode detectCycle(ListNode head) {
    ListNode cursor = head;
    Set<Integer> nodes = new HashSet<>();
    while(cursor != null) {
        if (nodes.contains(cursor)) return true;
        nodes.add(cursor);
        cursor = cursor.next;
    }
    return false;
}

🎄圣诞快乐～( ´▽｀)

在JDBC二三事中我们提到了使用Java提供的JDBC API进行数据操作。不难发现，在使用这种相对底层的接口编码时，会出现很多类似的代码，几乎每次查询操作我们都要执行获取连接、执行查询、释放连接、处理异常、管理事务的提交与回滚一套流程，稍有不慎就会导致数据库连接泄露啊，违反了事务ACID原则啊等等。
因此，在实际的应用开发中，我们一般都会借助框架提供的更可靠更抽象的方式的进行数据访问，让框架帮我们处理这些程式化的操作，解放自己来专注于核心业务逻辑。在这篇笔记里，我们就一起来看看如何使用Spring进行数据访问吧～

Spring整合了多种持久化技术，你可以：

• 使用Spring JDBC简化JDBC API操作；
• 与JPA、Hibernate、MyBatis等ORM(Object-relational Mapping)框架集成；
• 使用Spring提供的对NoSQL数据库的支持访问MongoDB、Redis等非关系型数据库。