一、G1收集器的记忆集为什么选择用哈希表，选择双向的卡表结构来实现

哈希表可以用常数时间回答你，集合里是否存在某一元素。或者在你已知某节点key的情况下，能以常数时间回答你该节点实例的其他字段。或者说叫O(1)。上述两个操作在链表中所需要的平均时间正比与链表的长度。

节点越多，效率越低。或者说叫O(n)

当你有n个节点在长度为m的容器里需要查询，并且n和m都比较大的时候，链表会数量级地慢于哈希表。

G1实现原理之记忆集与卡表

Regio

G1及其后出现的垃圾收集器ZGC、Shenandoah，它们都是基于Region的内存布局形式。它们垃圾收集的目标范围不再是整个新生代（Minor GC）、老年代（Majon GV）、整个堆（Full GC），而是一个一个的Region。因为这样的内存布局，所以G1能做到面向局部收集。

每个Region都可以被标记为E（Eden）、S（Survivor）、O（Old）、H（Humongous），但一个Region同一时刻只能是这四个中的一个。H表示巨型对象，即超过Region大小的一半的对象，会直接进入老年代由多个连续的Region存储。

Region的大小可以通过-XX:G1HeapRegionSize参数指定，如果没有显示指定，则G1会计算出一个合理的大小。Region的取值范围为1M~32M，且应为2的N次幂，所以Region的大小只能是1M、2M、4M、8M、16M、32M。比如-Xmx=16g -Xms=16g，则Region的大小等于16G / 2048=8M。也可以推理出G1推荐的管理的最大堆内存是64G。

RSet（Remembered Set、记忆集）

在垃圾收集过程中，会存在一种现象，即跨代引用，在G1中，又叫跨Region引用。如果是年轻代指向老年代的引用我们不用关心，因为即使Minor GC把年轻代的对象清理掉了，程序依然能正常运行，而且随着引用链的断掉，无法被标记到的老年代对象会被后续的Major GC回收。如果是老年代指向年轻代的引用，那这个引用在Minor GC阶段是不能被回收掉的，那如何解决这个问题呢？

最简单的实现方式当然是每个对象中记录这个跨Region引用记录，GC时扫描所有老年代的对象，显然这是一个相当大的Overhead。为什么呢？因为IBM做过这样的实验，发现绝大多数对象都是“朝生夕灭”，等不到进入老年代，能进入老年代的对象非常多不到5%。JVM的新生代内存比例是8:1:1也是基于这个结论设定的。

最合理的实现方式自然是记录哪些Region中的老年代的对象有指向年轻代的引用。GC时扫描这些Region就行了。这就是RSet存在的意义。RSet本质上是一种哈希表，Key是Region的起始地址，Value是一个集合，里面存储的元素是卡表的索引号（第几个Card的第几个元素）。

Card Table（卡表）

每个Region又被分成了若干个大小为512字节的Card，这些Card都会记录在全局卡表中。Card中的每个元素对应着其标识的内存区域中一块特定大小的内存块，这个内存块被称为卡页。一个卡页的内存中通常不止一个对象，只有卡页中有一个及以上对象的字段存在着跨Region引用，这个对应的元素的值就标识为1。

比如G1默认的Region有2048个，默认每个Region为2M，那每个Region对应的Card的每个元素对应的卡页的大小为2M / 512=4K，即这4K内存中只要有一个或一个以上的对象存在着跨Region对年轻代的引用，这个卡页对应的Card的元素值为1。

延伸阅读：

二、关于G0、G1、G2、G3的名词解释

G0、G1、G2、G3是描述曲面、曲线的连续方式，平滑程度的，一般常用于判断修补曲面时的曲面质量。

G0——点连续：是指曲面或曲线点点连续。曲线无断点，曲面相接处无裂缝。
判定方法：曲线不断，但是有角；曲面没有窟窿或裂缝，但是有楞。
数学解释：曲线或任意平面与该曲面的交线处处连续。
G1——相切连续：是指曲面或曲线点点连续，并且所有连接的线段、曲面片之间都是相切关系。
判定方法：曲线不断，平滑无尖角；曲面连续，没有楞角。
数学解释：曲线或任意平面与该曲面的交线处处连续，且一阶导数连续。
G2——曲率连续：是指曲面或曲线点点连续，并且其曲率分析结果为连续变化。
判定方法：对曲线做曲率分析，曲率曲线连续无断点。对平面做斑马线分析，所有斑马线平滑，没有尖角。
数学解释：曲线或任意平面与该曲面的交线处处连续，且二阶导数连续，需要学习UG编程在QQ群304214709可以给你帮助，学习和辅导。
G3——曲率相切连续：是指曲面或曲线点点连续，并且其曲率曲线或曲率曲面分析结果为相切连续。
判定方法：对曲线做曲率分析，曲率曲线连续，且平滑无尖角。因为对G3连续用到的比较少，目前还不知道什么更好的G3曲面判定方法，请高手补充。
数学解释：曲线或任意平面与该曲面的交线处处连续，且三阶导数连续。

上一篇

为什么C链表节点要用malloc函数动态分配大小?

下一篇

为什么二叉树的根结点常常是指向指针的指针?