如果我来设计 C++ 的 内存堆 ， 我会这样设计 ：                     

进程 首先会跟 操作系统 要 一块大内存区域 ， 我称之为 Division ， 简称 div 。 

然后 ， 将这块 div 作为 堆 ， 就可以开始 从堆里分配 内存 了 。

堆里 未分配 可使用 的 内存区域 称之为 Free Space ， 一开始的时候 ， div 里 只有一个 Free Space ， 就是 整个 div 。

如果 只分配 不回收 的话 ， div 里 永远都只有一个 Free Space 。 随着 分配 和 回收 ， div 里会产生多个 Free Space 。

我们需要建立一张 堆表 来 记录 Free Space ， 这样才能知道 每一次分配 应该 到 哪个 Free Space 里 分配 。

堆表 应该是一个 链表 ， 便于 插入 和 删除 表项 。 表项 就是 Free Space ， 或者说 表项 描述 Free Space 。 所以 表项 会包含 2 个 字段 ， 一个是 Free Space 的 起始地址 ， 另一个是 Free Space 的 结束地址 。

同时 还应该有一个 指针 ， 指向 当前在用的 表项 ， 一次分配 就是 在 当前表项 指向的 Free Space 里分配 ， 如果 当前 Free Space 的 大小 不足以分配本次申请的 内存块大小 ， 则 将指针 指向 当前 Free Space 的 下一个 Free Space 。 如果 下一个 Free Space 的 大小也不够 ， 那么 就继续指向 下一个 Free Space 。 如此循环 。

那如果 最后一个 Free Space 的大小也不够的话 ， 就需要向 操作系统 要 一个 新的 div 。 注意 ， Free Space 只能属于一个 div ， 不能跨 div 。

如果 堆里的 Free Space 比较多 ， 那么 如果 Free Space 大小不够 ， 有可能会连续找多个 Free Space 才找到 足够大小的 Free Space ， 这里就产生了一个 性能问题 。

最坏的情况 ， “从头找到尾” ， 到最后一个 Free Space 才足够大小 。 但 ， 这还不是最坏的 ^^ ， 如果最后一个 Free Space 的大小也不够的话 ， 就要跟操作系统要一个 新的 div ， 这好像要 “更坏” 一点 。  ^^

还有一个重要的问题需要考虑 ， 就是 如果 跟操作系统要了 1 个以上的 div ， 如果长期占用 ， 这是一个不小的空间 。 那么 ， 要怎样在 div 中的内存全部都已经回收 （整个 div 是一个 Free Space） 的时候 ， 将 div 归还操作系统呢 ？  

可以通过一个 计数器 。 可以为每个 div 设置一个 计数器 ， 同时在 堆表项 里增加一个 字段 ： Free Space 所在的 div 。

这样 ， 每次 分配 的时候 就在 计数器 里 加 1 ， 每次 回收 就让 计数器 减 1 ， 如果 减 1 以后 计数器 的 值 是 0 ， 那么就说明 div 已经全部回收 ， 可以将 div 归还 操作系统 。

最后 ， 我很好奇 ， C++ 是怎么解决 内存碎片 的问题的 。 哈哈哈哈

突然发现 堆 的 管理算法 有点 小复杂 ， 如果 堆表 本身占用的内存空间是 固定 的 ， 那么如果 Free Space 的数量超出了 对表 的空间所能存储的数量 ， 这就有问题 ， 如果舍弃一些 比较小的 Free Space ， 会造成 内存泄露 。

如果 堆表 的存储空间也是通过 堆 的方式来分配 ， 那么 ， 当应用程序申请了一块内存 ， 此时产生了一个 新的 Free Space ， 为了记录这个 Free Space ， 需要为描述这个 Free Space 的 堆表项 也 申请一块内存 ， 这样 Free Space 又会发生变化 ， 可能产生 1 个新的 Free Space， 或者 要记录的这个 Free Space 发生变化 ， 需要把这些情况也考虑进去 。

还有一种情况是 归还 内存块 的时候 ， 这个内存块刚好在 2 个 Free Space 中间 ， 那么归还这个内存块就不是简单的在 堆表 里添加一个 堆表项 ， 而是要和 前后 2 个 FreeSpace “合并” 起来 。 这 3 个 Free Space 会 合并成 1 个 Free Space ， 在 堆表 里 会 删除 原来的 2 个 Free Space 表项 ， 同时在 这 2 个 表项 的位置 添加入 合并后的 新表项 。

问题是 ， 要怎么知道 归还的内存块 在 某 2 个 Free Space 中间 ？ 好像只能 遍历 。 但这意味着 每次 归还的时候都要 遍历 。

然后 。

实际上 ， 不仅仅 内存块 在 2 个 Free Space 之间会存在这个问题 ， 只要 归还的内存块 的 任一边（前 或 后） 和 1 个 Free Space 相连 ， 都需要 “合并” 。

如果要快速的找到 和 自己邻近的 Free Space ， 可能需要建立 索引 。 可以建立 不止一个 的 索引 。

比如 可以 按 起始位置 建立索引 ， 同时还可以按 Free Space 的大小 建立索引 。 前者可以快速的寻找 和当前 归还的内存块 相邻的 Free Space 。 后者可以快速的寻找接近指定大小的 Free Space ， 这可以用在 分配 的 时候 ， 寻找接近 申请内存块大小 的 Free Space 进行分配 有利于提高 内存利用率 ， 减少碎片 。

索引 也可以排序 ， 如果要 优先从 小的 Free Space 或者 大的 Free Space 来 分配 的话 ， 索引的 排序作用 也可以派上用场 。

关于索引 ， 我在 《我发起了一个 .Net 开源数据库项目 SqlNet》 https://www.cnblogs.com/KSongKing/p/9501739.html    中有一些论述 。 实际上 ， 我正是考虑 数据库 中 Data Block 的 Free Space 如何管理 ， 所以才继续思考 内存堆 的 管理问题 ， 然后就产生了上面的一些思考结果 。

可以设想一下具体的做法 ：

如果不考虑 堆 的 无限增长 的话 ， 设计起来并不太难 ：）  所谓 无限增长 ， 主要是指 堆表 的无限增长 。 堆表 为什么会无限增长呢 ？ 堆表 是保存 Free Space 的 ， 如果 Free Space 无限增长 ， 那么 堆表 就会无限增长 。 Free Space 的数量是不确定的 ， 但理论上 ， 似乎不能给出一个限制 。 如果我们给定 堆表 的长度是 1万 ， 那么就只能记录 1万 个 Free Space ， 超出 1万 个的 Free Space 会因为不能记录而处于 “遗弃” 的状态 ， 既不能 分配 也不能回收 。 这就造成了 内存泄漏 。

如果在 堆表 达到上限的时候 抛出 异常 “堆表超出最大范围” ， 就像 StackOverflow 或者 OutOfMemory ， 但这可能会限制了应用程序的能力 。

如果按照上文的说法 ， 堆表 的 存储 本身也完全通过 堆分配 进行 ， 这样可以很灵活 ， 看起来只要内存空间足够 ， 那么 ， 堆表 可以无限增长 。

但这种做法 是 “自己描述自己” 的一个 循环 ， 会导致算法复杂 ， 循环 ， 或者 无解 。 所以我们放弃了这种方式 。

问题出在哪里呢 ？ 堆表项 自身对于 内存空间的 占用不能 计算到 堆 的分配里 。 堆表应该是单独占用一块空间 ， 堆表项 及 索引项 的 添加删除 在这个空间也会造成 空闲空间 （Free Space） ， 但这些 Free Space 不能 计算到 堆 里 ， 而应该是 独立 于 堆 的 存在 。 否则就会陷入上述的 “自己描述自己” 的 循环 。 总之情况很复杂 ， 可能无解 。 当然也许有解 ， 但我不想继续思考下去了  ：）  

所以 ， 回到开始 ， 如果不考虑 堆 的 无限增长 的话 ， 就是说 给定一个 堆表 的 固定大小 ， 我们这样来设计 堆 试试看 。 经过上面的论述 ， 实际上 ， 如果要设计 无限增长的 堆表 ， 那么 ， 在 固定大小 的 堆表 基础上 ， 增加一点 ： 当 当前堆表 空间不够时 ， 再申请一块 堆表空间 用于 继续存放 堆表 ， 这样 堆表 就能继续增长了  。 

我们提供一块 连续的 内存空间 来 存储 堆表 ， 这块 内存空间 我们 称之为 堆表空间 。 按照上面说的 ， 我们先尝试实现 一个固定大小 的 堆表空间 的 堆 。

堆表 的内容 包括 Free Space 项 和 索引 。 索引 由 索引项 组成 ， 索引项 最终会指向 堆表项 ， Free Space 项 之间通过 链表 的方式 相连 。 Free Space 项 和 索引项 都 存储在 堆表空间 里  。

堆表 还 包括一个 指针 ， 指向 堆表 的最后一个元素的结束地址的下一个地址 ， 我们将这个指针 称为 “Append 指针” 。

所有 新建 的 堆表项（Free Space 项 和 索引项） 都 添加至 Append 指针 指示的 地址 ， 每添加完一个 堆表项 ， Append 指针 会指向这个 堆表项 的 结束地址 的 下一个地址 。 当 Append 指针指向的 地址 到 堆表 的结束地址 之间的空间 不够 存放新的 堆表项 时 ， 会检查 “堆表空闲空间计数器” ， ——   等   ——     什么是 “堆表空闲空间计数器” ？ 在 堆表 的使用过程中 ， 随着 Free Space 项 和 索引项 的 添加 删除 ， 当然也会出现 “空闲空间” ， 我们会用一个 整数变量 ， 来记录空闲空间有多少（以 Byte 为单位） ， 每次删除 堆表项 （Free Space 项 和 索引项） 的时候 ， 会 将 回收 的 空闲空间 累计 到 这个 整数变量 里 。 这个变量 就是 “堆表空闲空间计数器” 。 注意 ， “堆表空闲空间计数器” 记录的是 Append 指针指向的地址之前 “已使用的空间” 中 因 堆表项 的 删除 而 “空出来” 的 空闲空间 。 这些 空闲空间 平时不会去动它 ， 只有上面说的 “当 Append 指针指向的 地址 到 堆表 的结束地址 之间的空间 不够 存放新的 堆表项 时” ， 才会去关心 它 。 怎么关心呢 ？ 这个时候 ， 会做一次 “垃圾回收” ， 就是把 这些 空闲空间 后面 的数据 向前移动 ， 填补这些 空闲空间 ， 就可以了 。 当然 ， 会先检查 “堆表空闲空间计数器” ， 如果 计数器 值为 0 ， 表明没有空闲空间 ， 不需要 垃圾回收 ， 大于 0 表示 有空闲空间 ， 需要 垃圾回收 。 如果没有要 回收的 空闲空间 ， 或者 回收了 空闲空间 以后 Append 指针指向的 地址 到 堆表 的结束地址 之间的空间 仍然不够 存放新的 堆表项 ， 怎么办呢 ？ 对于 固定大小的 堆表 ， 则 抛出异常 “堆表超出最大范围” ， 就像 StackOverflow 或者 OutOfMemory 。 对于 可以无限增长的 堆表 ， 则 新申请一块 堆表 空间 ， 继续工作 。 新的 堆表空间 和 原来的 堆表 空间之间 通过 链表 的 方式 相连 。

一个 堆表空间 包括 3 个部分 组成 ：

1 一块连续的内存空间

2 Append 指针

3 堆表空闲空间计数器

要 申请新的 堆表空间 ， 需要提前进行 ， 不要等到 空间不够用 的时候再进行 。 这是因为 新的 堆表空间 的申请 同样也是 通过 堆 的方式进行 ， 同样需要在 堆表 里 记录 堆表项 （Free Space 项 和 索引项）。 当某一次 申请 或 回收 需要记录 堆表项（Free Space 项 和 索引项） 而 空间不够时 再去 申请 新的堆表空间 ， 则 本次应用程序的申请或者回收 所产生 的 堆表项 （Free Space 项 和 索引项） 和 申请 新的 堆表空间 所产生 的 堆表项 （Free Space 项 和 索引项） 要放在一起计算 和 存储 ， 这样情况很复杂 。

所以 ， 应用程序的申请和回收 内存块 ， 和 申请 新的 堆表空间 ， 应该是 2 次 独立操作 。 所以需要 提前进行 “未雨绸缪” 。 提前到什么程度呢 ？ 在 原来的 堆表空间 的剩余空间 还 足够 存储 一次 申请内存块 产生的 可能的 最大数量的 堆表项 （Free Space 项 和 索引项） 的时候 。

申请一次 内存块 可能产生多少 堆表项 （Free Space 项 和 索引项） ？ Free Space 项容易理解 ， 上文也分析过 。 那么会产生多少 索引项 ？

上文中提到可以 创建 2 个索引 ： 1 Free Space 起始地址 作为检索条件 的索引 ， 2 Free Space Size（空间大小） 作为检索条件 的 索引 。

索引 1 可以用做 回收时 查询 和 回收的内存块 相邻的 Free Space ， 如果 2 者是 相接 的 ， 则会进行 合并 。

索引 2 可以用做 分配时 查找 Size（空间大小） 最接近 申请内存块大小 的 Free Space 。

但实际上 ， 索引 的 创建 也是 比较消耗时间的 ， 分配 可以采用前文最早提出的 先在 当前 Free Space 中分配 ， 若当前 Free Space 的空间大小不足以分配 ， 则 查找下一个 Free Space 分配 ， 以此递推 。 在 内存空间 充裕的条件下 ， 这种方式比查找 索引 快 ， 同时避免了 创建索引 消耗的时间 。

我们接下来就来 分析 索引的 创建 和 查询 ：  

根据上述 ， 我们只会建立和使用 索引 1  ， 用于 回收 时 合并 相接 的 Free Space 。

索引 1 在 分配时 创建（更新） ， 在 回收时 查询 并 更新 。

索引 1 的 索引项 是 这样 ： 最高位字节 用来保存 索引项的值 ， 只会用到 低位 的 2 位 ，表示 4 种情况 ： 00 , 01 , 10 , 11 。 后面再跟 4 个字节 或 8 个字节 表示 指向的 子索引项 或者 Free Space 项 的 地址 。 如果是 32 位 或 “Any CPU” 应用程序 ， 则是 4 个字节 ， 如果是 64 位 应用程序 ， 则是 8 个字节 。

在 分配 时 ， 用于 分配的 Free Space 的 大小（Size） 和 起始地址 会发生变化 。 对于 索引 1 ， 只需根据 起始地址 来 更新索引 即可 。

Free Space 的 起始地址 字段 表示 空闲空间 的 起始地址 。 同上 ， 如果是 32 位 或 “Any CPU” 应用程序 ， 则是 4 个字节 ， 如果是 64 位 应用程序 ， 则是 8 个字节 。 根据 《我发起了一个 .Net 开源数据库项目 SqlNet》  https://www.cnblogs.com/KSongKing/p/9501739.html    文中对于 索引 的 论述 ， 对于 32 位的数据 ， 会建立 32 / 2 = 16 个索引项   -_-   ， 对于 64 位的数据 ， 会建立 64 / 2 = 32 个索引项   -_-      。

所以 ， 对于 32 位 或 “Any CPU” 应用程序 ， 分配时 Free Space 起始地址 发生变化 需要修改 索引 最多需要 约 16 个索引项 ， 或者说 时间花费是 O(16) 。 因为 检索 1 个 索引项 需要 判断 4 种情况 ： 00 , 01 , 10 , 11  。 所以我们可以假设 1 次操作的时间是 4ns （4 纳秒） ， 那么 O(16) 的时间就是 16 * 4 = 64 ns （64 纳秒） 。 而 回收 需要查找索引找到 和 回收的内存块 相邻的 Free Space ， 同时 回收后 可能更新相邻 Free Space 的 起始地址（合并） ， 或者 产生一个 新的 Free Space ， 对于前者 ， 需要修改索引 ， 对于后者 ， 需要创建索引 ， 但不管是哪种 ， 最多需要检索（修改）的 索引项 约 16 个 ， 可以认为 时间花费 是 O(16) ， 而 回收 时查找索引寻找相邻 Free Space 的 时间花费 也可以认为是 O(16) ， 所以 加起来就是 回收 的 时间花费 是 O(16) + O(16) = O(32) ， 同上 ， 假设 1 次操纵的时间是 4ns ， 则 回收 的时间花费是 32 * 4 = 128 ns （128 纳秒） 。 当然 分配 和 回收 具体花费的时间还会 包括 修改 Free Space 起始地址 ， Next 指针 ， 合并时 删除 多余的 Free Space 项 等 ， 这些先忽略不计 ， 在下面估算的时候会酌情估算进去 。    

一次 分配 的时间是 64ns ， 再加上 分配 时 可能发生的一些遍历 （在 当前 Free Space 的大小不够时 ， 访问下一个 Free Space 尝试分配 ， 以此递推） ， 就按 80ns 算 ，  1 秒钟 大概可以进行  1200万次 分配 。 如何 ？ 还行吧 ， 呵呵 。 不过比起我想象中的 new ， 还是 慢了一点 ， 我想象中的 new 应该是 1ns   new 一个嘛 ！  P：  new 就是 分配 。

一次 回收 的时间是 128ns ， 就按 150ns 算 ， 1 秒钟 大概可以进行 600万次 回收 。 能不能再快一点 ？   ^^

对于 64 位 应用程序 ，  时间花费 是 32 位 的 2 倍 ， 所以 1 秒钟 可以分配 600万次 ， 回收 300万次 。 如何 ？ 哎 ？ 为什么 64 位 反而慢了 ？

上面的 分配 和 回收 的 执行速度 是 针对 1 个 CPU 核 分析的 ， 但对于多核 ， 分配 和 回收 的 执行速度 也是 如此 。 因为 堆 是进程内所有 线程 共享的 ， 堆表 也是共享的 ， 在进行 分配 和 回收 时要修改 堆表 ， 此时需要对 堆表 进行 同步/互斥 （Lock） ， 所以 ， 对于多核 ， 分配 和 回收 的 执行速度 也是 如此 。

从这里可以看出 ， 堆 的这一特性会成为 瓶颈 。 在 高频 高密度 计算的 场合 。 比如 高并发 实时 响应式 系统 。 说的直接一点 ， 就是跟现在的 互联网 大规模 计算 有关 。  

这一类型的 瓶颈 也表现在 其它方面 。 比如 套接字（Socket） ， Socket 对于每个网卡只会有一个 线程 负责从 网卡 读写数据 。 这是我的 推测 。 一个 端口（Port） 的 Socket 由一组线程组成 ： 1 负责从网卡读写数据的线程（1 个网卡 对应 1 个线程） ， 2 处理和分发数据给应用程序的线程们（有若干个线程 ， 线程数 和 CPU 的 核数对应 ， 可以包括 虚拟线程(超线程) 数） 。 在 线程 1 和 线程 2 们 协作 的时候 ， 会有一个共享数据区 ， 线程 1 会把从 网卡 读取到的 数据 放到 共享数据区 ， 线程 2 们 会从 共享数据区 取出数据处理分发 。 显然 ， 线程 1 和 线程 2 们 的协作需要 同步/互斥（Lock） ， 

我们可以看一下这篇文章《面向对象编程的弊端是什么？》 https://www.zhihu.com/question/20275578/answer/136886316?utm_source=com.tencent.tim&utm_medium=social&utm_oi=697587017629851648

文中有一幅图  ：    

如图 红线 所示 ， Mutex（同步 / 互斥 Lock） 的时间是 17ns （17 纳秒） 。 这个时间是一个 不太能忽视 的 时间 。

所以 ， 这会成为 利用 并行计算 大幅提升计算能力的 瓶颈 。 而 利用 并行计算 大幅提升计算能力 正是 当下和未来 的 主题 。

另外就是 ， 一个网卡只有一个 IO 线程 ， 这也可能成为 瓶颈 。 当网络技术发展到 5G 或 6G 的时候 ， 会不会有 NPU（Net Process Unit）出现 ？ 就像 GPU 一样 。  ^^      

实际上 ， 对于 堆表 的无限增长 ， 有一个 “终极” 的解决办法 ， 或者说 更好的办法 。 就是 GC （垃圾回收器） 。

在 现代 ， 或者说 “当代”  的 语言 ， 如 C# , Java 里都有 GC 。 GC 可以将 Free Space 的 数量 控制在 有限 和 很少 的 范围 。 这样就不存在 堆表 的 无限增长 了。  

然后 。

当然 ， GC 要登记 所有变量 ， 并定期遍历 ， 移动数据 ， 这些也要花费时间的 。

堆表 的 无限增长 ， 这是一个问题 。 堆表 增长 ， 表示 Free Space 增多 ， 碎片 也增多 ， 这样 在 分配 时可能会遍历 比较多的 Free Space 。 

对于 64 位 应用程序 ， 64 位 理论上的 寻址空间 可以达到 16eb ， 如果 应用程序 对于 存储空间 的使用是没有限制的 ， 那么 ， 一段时间之后 ， 堆表 ， 或者说 Free Space （包括碎片） 的 数量 可能会达到 很大的 数量 。

假想一下 ， 如果 Free Space 很多 ， 碎片也很多 ， 那么可能要遍历 很多次 才能找到 大小足够的 Free Space 进行分配 。 这个时候 ， 我们可以考虑加入这样的算法 ， 最多遍历 10 个 Free Space ， 遍历了 10 个 Free Space 还找不到大小足够的 Free Space ， 则 向操作系统 申请 1 个 新的 div ， 并将 div 作为 新的 Free Space 插入到当前位置 ， 并从这个 div（新的 Free Space） 中分配 。 分配以后 ， 下一次分配当然也会从这个 div 开始 ， 如果这个 div 的 剩余空间 不够 ， 则 访问下一个 Free Space 。 如果访问了 10 个 Free Space 也找不到足够大小的 Free Space ， 则 重复上述流程 ， 向操作系统 申请 1 个 新的 div ， 并将 div 作为 新的 Free Space 插入到当前位置 ， 并从这个 div（新的 Free Space） 中分配 。 以此递推 。

这种方式 ， 可能会浪费一些空间 ， 或者说 ，  会向 操作系统 申请多一些的 空间（div） ， 但是在 时间 上提高了效率 。 这也算是 “空间换时间” 吧 。 在 现在来讲 ， 硬件容易扩充 ， 提升计算速度 是一个主要目标 。

根据以上 ， 我们再来整理一下 具体的 做法 。

我们 以 64位 应用程序 的 标准 来实现 ：

当进程启动时 ， 会分配一块 固定大小 的 连续空间 ，作为 堆 的 基础元数据区 ， 基础元数据区 包括 5 部分 ：

1  Append 指针 ， 指向 堆表 可插入 堆表项 的 地址 （当前 最后一个 堆表项 之后） ， 插入 堆表项 后 ， Append 指针 会 指向 堆表项 结束地址 的 下一个地址 。 Append 指针 的 初始值 应指向 第 5 个 堆表项 的 起始位置 。 因为会在 堆表 中 预先建立 4 个 1 级 索引项 ， 见 下面 第 4 部分 。   

2  堆表 的 Free Space 项 链表 头指针 ， 指向 Free Space 项 链表 的 头 。 （Free Space 项 之间通过 链表 的方式连接起来）

3  当前 Free Space 项 指针 ， 指向上一次用于 分配 的 Free Space 项 。 下一次 分配 会先尝试在 上一次 分配 的 Free Space 中进行 ， 若 Free Space 的 大小不够 ， 会 访问 下一个 Free Space 尝试分配 。 分配 成功后 ， 当前 Free Space 项 指针 会指向 分配 成功的 Free Space 项 。 当然这里面还有些具体的逻辑 ， 比如 访问 超过 10 个 Free Space 项 仍然找不到 大小足够 的 Free Space ， 则 会向操作系统 申请 新的 div ， 作为 Free Space 加入进来 ， 然后在这个新的 div 中 分配 。

4  堆表  的 初始空间  。 堆表 的 初始空间 可以是   1 MB    。 进程启动 时 ， 会初始化 基础元数据区 ， 此时应在 堆表 的 第 1 ~ 4 个 堆表项 位置 预先建立 1 级 索引项 （00 , 01 , 01 , 11） 。 所谓  初始空间  是指这部分是 固定不变 的 ， 之后 堆表空间 不够用时 ， 会在 堆 中申请新的 堆表 空间 。 这些新申请的 堆表空间 空出来的时候会 归还 堆 ， 但 初始空间 是 不变的 ， 不变是指 一直存在 ， 大小不变 。 且 初始空间 不属于 堆 。

5  Next 指针 ， 指向 下一个 堆表 空间 。 随着 堆 的规模的增长 ， 堆表 大小不够时 ， 会从 堆 里 申请 新的 堆表 空间 ， 新的 堆表空间 会和 初始空间 用 链表 的方式连接起来 ， 可以 申请 多个 堆表空间 ，  如 ：   初始空间 -> 第 1 个新申请空间 -> 第 2 个新申请空间 -> 第 3 个新申请空间 -> …… 第 n 个新申请空间 ->  ……

    当 堆 的规模缩小时 ， 会释放 空闲 的 堆表空间 （归还 堆） 。

    初始空间 不属于 堆 ， 当然永远不会释放 。

接下来 ， 我们这样来定义堆表项 ： 

堆表项 分为 2 种 ：

1  索引项

2  Free Space 项

具体规则是 ： 

1)  索引项 和 Free Space 项 都占用 34 个字节 。 第 1 个字节 是 标识字节 ， 为 1 表示 索引项 ， 为 2 表示 Free Space 项 ， 为 0 表示 已删除 。   

2)  对于 索引项 ， 第 2 个 字节表示 索引值 ， 就是   00 , 01 , 10 , 11   这 4 种值中的一种 ， 实际上这 4 种值只用到了 2 位 ， 不过我们还是用一个字节来存储 。 如果是 十进制 表示这 4 个值 ， 就是   0 , 1 , 2 , 3   。 我们设计的是 4 阶索引 ， 第 3 ~ 10 个字节存储 第 1 个 子索引项 或 Free Space 项 的 地址 （64 位地址 用 8 个字节存储）， 第 11 ~ 18 个字节存储 第 2 个 子索引项 的 地址 ， 第 19 ~ 26 个字节存储 第 3 个 子索引项 的 地址 ， 第 27 ~ 34 个 字节存储 第 4 个 子索引项 的 地址 。 若 8 个字节表示的 64 位地址 （ulong  无符号长整型  uInt64） 为  0 ， 表示 子项 不存在 。 有关 索引 和 4 阶索引 ， 我在 《我发起了一个 .Net 开源数据库项目 SqlNet》  https://www.cnblogs.com/KSongKing/p/9501739.html    一文中有论述 。

      所以 ， 可以看出 ， 索引项 长度 是  1 + 1 + 8 + 8 + 8 + 8 = 34 个字节 。

3)  对于 Free Space 项 ， 第 2 ~ 9 个字节 表示 起始地址 ， 第 10 ~ 17 个字节 表示 结束地址 。 第 18 ~ 25 个字节 表示 所在的 div 的起始地址 。 第 26 ~ 33 个字节 表示 Next 指针 指向 下一项 Free Space 项 （Free Space 项 之间会通过 Next 指针来用 链表 的方式连接起来） 。 Free Space 项 的 长度 是  1 + 8 + 8 + 8 + 8 = 33 个字节 。

      为了便于管理 ， Free Space 项的长度也定义为 34 个字节 ， 和 索引项 一样 。 多出来的 1 个字节 不会用到 。

      将 索引项 和 Free Space 项都定义为 34 位 是 便于管理 ， 或者说 便于算法处理 。 堆表 进行垃圾回收的时候 ， 只需要每隔 34 个字节检查一次 标识字节 ， 就可以知道 堆表项 是否已删除 ， 若 已删除 则将后面的 堆表项 移动上来 ， 填补 已删除 的 空闲空间 。 这就是 堆表 的 垃圾回收 。

div ， 接下来说明 div 的定义规则 。 div 是 进程向 操作系统 申请 的一块 大的 内存区域 ， 用于作为 堆空间 。  

第 1 次 分配 内存块 时 会申请 第 1 块 div 。 如果从来没有 申请 过 内存块 ， 则不会申请 div 。

div 分为 3 个部分 ：

1  结束地址 ， div 的 结束地址 ， 用  8 个字节表示  （ulong 无符号长整型 uInt64）

2  分配计数器  useCount ， 用于记录 分配 的内存块 数量 ， 若 计数器 的值为 0 ， 表示 div 完全空闲 ， 即没有 分配 任何空间 ， 可以 归还 操作系统 。 当然 刚申请到 div 的时候 ， 计数器 的值也是 0 ， 不过那时会接着用于 分配 。 计数器  也用  8 个字节表示 （ulong 无符号长整型 uInt64）

3  剩余的空间 用于 分配 。

接下来说明 运行逻辑 ：

我们先 估算一下 ， 1 MB 的 堆表 空间 够存放多少个 Free Space 项 （包含 索引项）  ？

Free Space 项 的 地址是 64 位地址 ， 要为 64 位地址 建立 索引 ， 需要 64 / 2 = 32 个 索引项 。 每个 索引项 占据的空间是 34 个字节 ， 再加上 Free Space 项 占据 的 34 个 字节 ， 1 个 Free Space 需要的 存储空间 是   (32 + 1) * 34 =  1122    个字节 。 实际中会比   1122  小 ， 因为 索引 的 父节点 存在共用的现象 。 我们可以按  1024  来算 ， 存储一个 Free Space 需要  1024  个字节（包含 索引项） ， 那么  1 MB  可以 存储   1024   个  Free Space（包含 索引项） 。

所以 ， 1 MB 的 堆表 可以记录   1024   个 Free Space ， 如果 应用程序 申请 和 归还 内存块 产生的 Free Space 不超过 1024 个的话 ， 1 MB 的 堆表就够了 。 如果超过 ， 则需要 申请 新的 堆表 空间 。 新的 堆表 空间 在 堆 中申请 。 可以仍然申请   1 MB 。 如果 新申请 的 1 MB 堆表空间 用完了 ， 可以继续申请 1 MB ， 以此递推 。 当然 ， 实际中 不会等到 堆表空间 不够用时才去申请新的 堆表空间 ， 上文分析过 ， 如果这样的话 ， 会陷入 “自己描述自己” 的 循环中 ， 所以 ， 应该在 快用完（至少还足够保存一次申请产生的 最大的 Free Space 变化 ( 包含 索引项 ) ） 的 堆表 空间 时 就申请 新的 堆表空间 。

当 应用程序 第 1 次 申请 内存块 时 ， 堆管理程序 会 检查 基础元数据区 的  第 1 个 div 的 起始地址 ， 若 为 0 （div 不存在） ， 就向 操纵系统 申请 div ， 申请到后将 div 的 起始地址 记录到 基础元数据区 的  “第 1 个 div 的 起始地址” 。

然后 ， 将 div 的 第 3 部分 （用于 分配 的空间） 作为 1 个  Free Space 记录入 堆表 （这是 第 1 个 Free Space） 。 当然 ， 记录的操作 包括 了 建立 索引 。 注意 ， 1 级索引项 （00 , 01 , 10 , 11） 固定存储在 堆表 的 第 1 ~ 4 个 堆表项 位置 。 应用程序启动 ， 初始化 基础元数据区 时应预先建好这 4 个 索引项 。 

接下来 ， 就开始在 堆表 中访问 Free Space 进行分配 ， 当然 现在只有 1 个 Free Space ， 就是上面刚添加进去的 Free Space 。 分配的话 ， 就从 Free Space 的 起始地址 开始分配 。 比如 ， 要 申请 1 KB 的 内存块 ， 那么就把  Free Space 起始地址 ~ Free Space 起始地址 + 1 K - 1    这块内存 分配 给 应用程序 。 如果 申请的 内存块大小 比 这个 第 1 个 Free Space 都大 ， 那么应该抛出异常 “只允许申请大小在 xx 范围内的内存块” 。

分配 的 具体工作 ： 修改当前 Free Space 的 起始地址 ， 修改为 Free Space 起始地址 + 1 K ， 同时 修改索引 ， 根据 Free Space 原来的 起始地址 遍历 索引项 ， 遍历到 和 新的 起始地址 不同 的 索引项 就修改 索引项 。 这么说好像不知道在说什么 。好吧 ， 我们举个具体的例子 ：  

我们的设计是 64 位地址 ， 举例的话 就 简单一点 ， 我们 以 8 位地址 为例 ， 假设 Free Sapce 的 起始地址 是 0  （0000 0000）， 申请 4 个字节大小的内存块 。

申请前 Free Space 的 索引是这样的 ：  00 -> 00 -> 00 -> 00 ， 申请后 Free Sapce 的 起始地址 会变成 4 （0000 0100） ， 相应的 ， 索引会变成 ：  00 -> 00 -> 01 -> 00 ， 可以看到 ， 从 第 3 个索引项 开始 ， 新的索引 和 旧的索引 变得不同 ， 所以 我们 从 第 3 个 索引项 开始修改 为 新的索引项 就可以了 。

整个修改索引的过程 会 遍历 全部的索引项 （包含了 修改） ， 64 位地址 是 32 个 索引项 ， 所以 分配 的 时间复杂度 约大于 O(32)  （还要考虑其它的操作 ， 所以是 约大于） ， 我们上文中就是这样估算的 。

其它还有什么操作呢 ， 好像没有了 。  ^^

分配就 2 步操作 ：  1  修改 Free Space 起始地址  ，  2  修改索引    。

接下来是 归还 ， 归还 分为 4 种情况 ：

1  归还 的 内存块 的 前后 不和 已有的 Free Space 相接 ， 这样 归还 会产生 一个 新的 Free Space 。

2  归还 的 内存块 和 前面 或者 后面 已有的 Free Space 相接 ， 这样 需要 和 相接的 Free Space 合并 。

3  归还 的 内存块 和 前面 和 后面 已有的 Free Space 相接 ， 这样 需要 和 前后 2 个 Free Space 合并 。

4  归还 的 内存块 没有 相邻 的 Free Space ， 这种情况比较特殊 ， 这种情况就是 整个 div 的 内存 完全被 分配 出去的 情况 。

具体 流程 是这样 ：

应用程序 将 内存块 的 起始地址 提供给 堆 来 归还 这块内存块 。 堆 根据 内存块 的 起始地址 查找索引 ， 查找 和 内存块 前相邻 的 Free Space 。 前相邻 ， 是指 相邻 且 在 前面 。 什么是 前面 ？ Free Space 的 起始地址 小于 内存块 的 起始地址 叫 前面 ， 大于 叫 后面 。

根据 索引 查找到 前相邻 的 Free Space ， 还不一定是 真正 的 前相邻 的 Free Space ， 还要加一个 判断条件 ：  Free Space 所在的 div 和 内存块 所在的 div 是 同一个 div ， 这样才是 前相邻 的 Free Space 。

我们这样来 定义 前相邻 后相邻 ：

前相邻 ：  起始地址 小于 内存块 的 起始地址 ， 且 和 内存块 属于同一个 div ， 则为 前相邻 。

后相邻 ：  起始地址 大于 内存块 的 起始地址 ， 且 和 内存块 属于同一个 div ， 则为 前相邻 。

如果 查找不到 前相邻 ， 那么就根据 基础元数据区 里的 Free Space 链表 头指针 找到 头指针 指向 的 Free Space 项 ， 这个 Free Space 项 就是 内存块 的 后相邻 。

如果 Free Space 链表 头指针 为 空 （0） ， 也表示 没有 相邻 （既没有 前相邻 ， 也没有 后相邻） 。

什么情况下 Free Space 链表 头指针 为 空 （0）  呢 ？ 在 应用程序 初始化 后 ， 还没有 分配 的时候 。 以及 分配 以后 ， 整个 div 都被分配出去 。 如果有多个 div ， 所有 div 都被完全的分配出去 ， 头指针 也为 空 （0）  。

头指针 不空 ， 可以找到 起始地址 大于 或 小于 内存块 起始地址 的 Free Space ， 但 Free Space 和 内存块 不在同一个 div 的话 ， 也不是 相邻 。

怎么判断 Free Space 和 内存块 在不在 同一个 div ？  Free Space 项 有一个字段 是 所在 div 的 起始地址 ， div 的 第 1 个 部分 是 div 的 结束地址（见上文对 div 的定义） ， 根据 div 的 起始地址 可以找到 div 的 结束地址 ， 根据 div 的 起始地址 和 结束地址 可以判断 内存块 在不在 div 里 。

找到 前相邻 后 ， 判断 前相邻 的 结束地址 + 1 和 内存块 的 起始地址 是否相等 ， 若相等 ， 则 两者应合并 。 但这里还要进一步的判断 ， 是 情况 2 还是 情况 3 ， 所以 还需要 根据 前相邻 的 Next 指针 找到 下一个 Free Space 项 ， 这就是 后相邻 。 判断 后相邻 的 起始地址 和 内存块 的 结束地址 + 1 是否相等 ， 若相等 ， 表示是 情况 3 ， 若不等 ， 表示是 情况 2 。

如果 没有 相邻的 Free Space ， 就是 情况 4 。 如果有 相邻的 Free Space ， 但既不是 情况 2 ， 也不是 情况 3 ， 就是 情况 1 。

对于 情况 1  ， 需要 新建一个 Free Space 项 ， 插入到 Free Space 项 链表 里 ， 插入位置是 内存块 的 前相邻 之后 ， 或者说 ， 后相邻 之前 。 当然 ， 新建 Free Space 项 需要建立 相应 的 索引 。 索引 有 32 个 索引项 ， 所以 新建 Free Space 的时间复杂度 约大于 O(32) 。再加上 查找 前相邻 的时间复杂度 O(32) ， 所以 情况 1 的 时间复杂度 约大于 O(32) + O(32) = O(64) ， 约大于 O(64) 。 上文就是这样估算的 。

对于 情况 2 ，  如果和 前相邻 相接 ， 就 修改 前相邻 的 结束地址 和 索引 就可以 ， 如果和 后相邻 相接 ， 修改 后相邻 的 起始地址 和 索引 就可以 ， 这个和 分配 的 操作方法 一样 ， 参考上文 分配 的部分 就可以 。

对于 情况 3 ， 可以 修改 前相邻 的 结束地址 和 索引 ， 同时 删除 后相邻 ， 相应的 ， 后相邻 的 索引 也要删除 。 删除索引 的 步骤是 ：  根据 后相邻 的 起始地址 遍历 索引项 ， 对于只有 1 个子索引项 的 索引项 删除 即可 。 只有一个 子索引项 表示 从 当前索引项 开始的 索引路径 仅仅指向 要删除的这个 后相邻 。

对于 情况 4 ， 直接按照 内存块 的 起始地址 结束地址 新建一个 Free Space 项 ， 添加到 Free Space 堆表 ， 当然会建立相应的 索引 。 同时 ， 还要将 Free Space 项 插入 Free Space 项 链表 里 。 插入位置 在 ——    根据 索引 查找出 起始地址 小于 自己 的 Free Space 项 ， 插入到这一项之后就行 。 注 ：  因为不在同一个 div ， 所以 不能叫 前相邻 或者 后相邻 。 如果 查找不到 起始地址 小于自己的 ， 就插入到 头 ， 即 基础元数据区 里的 Free Space 链表 头指针 指向 自己 ， 自己 的 Next 指针 指向 原来 头指针 指向 的 那一项 。 如果 头指针 原来是 空 （0） ， 那就 让 头指针 指向 自己 就可以了 。

Free Space 项 链表 不是一个 独立 的 东西 ， 而是 堆表 里的 Free Space 项 之间会通过 Next 指针来用 链表 的 方式 连接起来 。 因为只有 Next 指针 ， 所以是 单向链表 。 现在看起来 ， 单向链表 够用了 。        -_-  '

每次 申请 和 归还 后会检查是否进行 垃圾回收 ， 当满足以下 2 个条件时进行 垃圾回收 ：

1  Append 指针 到 堆表 结束地址 的 内存空间 小于 1500 个字节时 ，

2  堆表 的 空闲空间 超过 堆表空间 的 2/3 的时候 

每次 垃圾回收 后会检查是否需要 扩充 堆表， 当满足以下条件时 扩充 堆表 ：

Append 指针 到 堆表 结束地址 的 内存空间 小于 1500 个字节时 ，

扩充 堆表 就是 申请新的 堆表空间 和 初始空间 用 链表 的方式 连接起来 ， 当然 ， 随着 堆 的规模的扩大 ， 可以 申请 第 2 个 、 第 3 个 、第 n 个 ……  堆表空间 ， 用 链表 的方式连起来就是  ：    初始空间 -> 第 1 个新申请空间 -> 第 2 个新申请空间 -> 第 3 个新申请空间 -> …… 第 n 个新申请空间 ->  ……

这一点的意义上面已经多次分析过 ， 为了避免陷入 “自己描述自己” 的 陷阱 ， 所以需要在 堆表 空间 快用完时 ， 扩充 堆表 空间 。 堆表 空间最少要能够存储一次 分配 （包含 可能 申请 div 的 情况）  所产生的 Free Space 项 （包含 索引项） 。 一般的 分配 只需 修改 Free Space 项 的 起始地址 和 索引 ， 当有 申请 div 的 情形 时 ， 会新建 Free Space 项 及 完整的 索引 （32 个 索引项） ， 这应该是 分配 时 占用空间 最大的情况 ， 我们按这种情况来计算 。 上面说过 ， 1 个 Free Space （包含 索引项） 会占用 1122 个 字节 ， 我们放宽松一点 ， 在 堆表 剩余空间 只有 1500 个字节 时 就 扩充 堆表 。

那什么时候 “压缩” 或者说 释放 空闲出来的 堆表 空间 呢 ？

在 垃圾整理 后 ， 检查 最后一个 “不空” 的 堆表空间 ， 即 最后一个 存储了至少 1 个 堆表项 的 堆表空间 ， 如果 这个 堆表空间 的 空闲空间 超过 堆表空间 的 2/3 ， 那么将 释放 这个 堆表空间 之后 所有的 堆表空间 。 释放 就是 将 堆表空间 归还 堆 。 上文说了 ， 初始空间 以外 的 堆表空间 都是 从 堆 里申请的 。

初始空间 不属于 堆 ， 显然 ， 永远不会释放 。

说到这里 ， 显然 ， “堆表” 是一个 可扩充的 ， 由若干个 线性表 通过 链表 的 方式 连接起来的 数据结构 。

Append 指针 指向的是 最后一个 堆表项 ， 这个 堆表项 可能在 初始空间 ， 也可能在 新申请 的 第 n 个 堆表空间 。

在 分配 时 ， 会从当前 Free Space 项 指针 指向的 Free Space 项 开始 尝试分配 ， 如果 当前项 大小不够 ， 会 访问 下一个 Free Space 项 ， 如果 访问超过 10 个 Free Space 项 还找不到大小足够的 Free Space ， 则 会向操作系统 申请 新的 div ， 作为 Free Space 加入进来 ， 然后在这个新的 div （新的 Free Space） 中 分配 。 

这主要是从 执行速度 的角度考虑 。 这也算是 “空间换时间”  。

这逻辑真的  乱 ，   烦 。

我们可以用 文件 的方式来模拟实现这个 堆管理 算法 。

就是用 一个文件 模拟 一块内存区域 ， 来实现这个 堆算法 。

我们会先实现一个 EnLargableList 的数据结构 ， EnLargableList 是一个 线性表 通过 链表 的方式连接起来的 可扩充的 数据结构 ， 用来实现 堆表 。

堆 的 复杂来自于 堆表 的 动态增长（无限增长） ， 如果 堆表 是 固定大小 的 ， 那么 堆 并不太难 。

 上面有一个地方的逻辑有漏洞 ， 向操作系统申请了一个 div 之后 ， 除了 将 div 可分配的空间作为一个 Free Space 项 加入 Free Space 项 链表 外 ， 还应该新建一个 “空的” Free Space 项 加入 。 这个 “空的” Free Space 项 的 起始地址 和 结束地址 都是 div 的 可分配空间 的 起始地址 。 因为 起始地址 和 结束地址 相等 ， 所以是 “空的” 。 因为 大小 是 0 ， 总是 小于 申请的内存块的大小 ， 所以 ， 在 分配 的时候不会分配这个 Free Space 。

这个 空的 Free Space 有什么用呢 ？  这是为了解决 整个 div 都被完全的分配出去的情况 ， 上文分析过了 ， 整个 div 都被完全的分配出去的话 ， Free Space 链表 里就没有这个 div 的 Free Space ， 这样 当 这个 div 里的 内存块 归还时 ， 会找不到 前相邻 和 后相邻 ， 从而不知道这个 内存块 是 哪个 div 的 ， 这样 归还 的逻辑就有问题 ， 就算不管是哪个 div 而直接将内存块作为 Free Space 归还 ， 最终也会导致即使这个 div 已经全部空闲（所有 分配 出去的 内存块 都 归还 了） ， 但是无法将 这个 div 归还 操作系统 。 相当于这个 div 处于 “半遗弃” 的状态 。因为 它的 Free Space 仍然可以继续 分配 和 归还 ， 但 这个 div 已经不在 正式名单 上了 ， 无法在 全部空闲 时 归还 操作系统 。 当然 ， 实际中 这样的操作是 不允许的 ， 因为 Free Space 项最后一个字段就是 指向 自己所在 div 的 起始地址 ， 就是说 Free Space 项 应该 知道 自己所在的 div ， 如果不知道 ， 程序不能运行下去 。

所以 ， 每个 div 一定会有一个 空的 Free Space ， 不管 div 的空间如何分配 ， 这个 空的 Free Space 会一直存在下去 ， 直到 div 归还操作系统 ， 这个 空的 Free Space 才会被删除 。

因为我们没有专门的表 来记录 div ， 所以这个 空的 Free Space 相当于 div 的代表 ， 或者 占位 。

上面的做法还是有一点问题 。 用一个 “空的” Free Space 来表示 div 会有一些问题 。 实际上 “空的” Free Space 不是空的 ， 是大小为 1 个字节 的 空间 。 起始地址 和 结束地址 相等 ， Free Space 的大小 = 结束地址 - 起始地址 + 1 = 1 。 所以 ， 在 归还 Free Space 时 ， 如果 归还的 Free Space 和 这个 “空的” Free Space 相接 ， 会和 “空的” Free Space 合并 ， 这又会引出合并后下次分配时 第 1 个字节 不能分配（作为 “空的” Free Space） 之类的判断 ， 会把算法逻辑变复杂 。

所以 ， 我们放弃了这种方式 。 正统的做法应该还是把 div 记录到 堆表 里 ， 也会为 div 建立索引 。 也就是说 ， 增加一种 堆表项 ： div 项 。 标识字节（第 1 个字节） 为 3 表示 div 项 。 div 项的第 2 ~ 9 个字节存储 div 的起始地址 。 当然 div 项的长度也是 34 （和 索引项 Free Space 项 相同） ， 多余的字节不会用到 。

这样 ， 在 归还 内存块 时 ， 如果找不到 前相邻 ， 也找不到 后相邻 ， 说明 div 被完全分配出去了 ， 此时就会根据索引查找 div ， 找到 起始地址 小于 内存块的起始地址 且相邻 的 div ， 这就是 内存块 所在的 div 。

归还 内存块 后 ， div 的 分配计数器 会 减 1 ， 减 1 后检查 计数器值 是否为  0 ， 若为 0 则 div 的空间已完全空闲 ， 于是将 div 归还操作系统 。

但这样的做法还是有问题 ， 要为 div 建立索引 ， 这有一点额外的麻烦 ， 比如 现在的 堆表项 开始的 4 个项位置 存储的是 4 个 1 级索引项 ， 如果要为 div 建立索引 ， 需要专门再为 div 建立 4 个 1 级索引项 ， 这些会增加算法内容 ， 会变得复杂或者麻烦 。

所以 ， 我们还是回到用 一个 “空的” Free Space 来表示 div ， 或者 占位 的做法 。 在 申请一个新的 div 的时候 ， 会创建 2 个 Free Space ， 一个是 “空的” Free Space ，  另一个是 可用的 Free Space 。 div 的开头会用 8 + 8 = 16 个字节分别表示 结束地址 和 分配计数器 use Count ， “空的” Free Space 就是 第 17 个字节 ， 起始地址 和 结束地址 都是 第 17 个字节 ， 从第 18 个字节开始就是 可用空间 了 ， 可用的 Free Space 就是 第 18 个字节 开始到 div 的 结束地址 。

我们可以给 Free Space 项 增加一个 字节 来表示 Free Space 的 “Type” ， 在 标识字节 之后 。 第 1 个字节是 标识字节 ， 我们用 第 2 个字节来表示   Free Space Type ，  0  表示 “空的” Free Space ，  1  表示 普通的 Free Space 。 这样的话 ， Free Space 项 和 索引项 一样 ， 都是 34 个字节了 。

在 分配 和 回收 时 需要判断 Free Space 时 “空的” Free Space 还是 普通的 Free Space 。 上文中定义过 ， 标识字节 为 2 表示 普通的 Free Space 。

在 分配 时 判断 ， 如果 是 “空的” Free Space ， 就不进行分配 ， 而是 访问下一个 Free Space 尝试分配 。

在 回收 时会寻找 前相邻 ， 如果 前相邻 是 “空的” Free Space ， 则不进行 判断是否相接若相接则合并的逻辑 。

EnLargableList （用于 堆表）  会设定这样一些参数：

1  whenRecycleFragment ， 这是一个 整数 ， 表示 碎片数量 超过多少 应开始 碎片回收 ， 可以设置为 1万 ， 碎片数量 是 以 对表项 为 单位 。 假设 堆表空间 是  1MB ， 每个 堆表项 占用 34 个字节 ， 可以存约  3 万个 堆表项 ， 约表示 1024 个 Free Space （每个 Free Space 最多由 33 个 堆表项 表示 ， 包含 32 个 索引项 + 1 个 Free Space 项） 。

    如果 设置 whenRecycleFragment 为  1 万 ， 相当于是 一个 堆表空间 中有 1/3  的 空闲空间 ， 此时回收 。 效果怎么样 ？  不知道 。

    或者说 相当于 一个 堆表 空间中 记录了 600 个 Free Space 项 ， 还有 300 个 Free Space 的位置可以记录 ， 此时回收 。 效果怎么样 ？  不知道 。

    上文中提到 当 Append 指针 到 堆表空间 的 结束位置 的 空间 小于 1500 时 回收 ， 但现在放弃了这种做法 。

    因为 这种做法 好像不太科学 ， 在应对 规模很大 的 堆 时候 ， 好像不太适用 。 堆 的 规模很大 ， 是指可以无限制的 使用 地址空间 ， 内存块 数量 和 Free Space 数量（包含 碎片）  可能 持续增长 。  大小 1MB 的 堆表 可以存约  3 万个 堆表项 ， 以 堆表项 为 单位 遍历 一遍 需要 遍历 3 万个 堆表项 。 3 万 是一个不小的数量 ， 所以我们想 当 碎片（空闲出来的 项位置）  达到  1 万 的时候回收 可能会比较好 。

2  whenEnLarge ， 这是一个整数 ， 表示 append 指针 到 堆表 末尾 的 空间还有多少时 扩充 堆表 容量 ， 扩充 堆表 容量 就是 申请新的 堆表空间 ， 新申请的 堆表 空间 以 链表 的方式连接到 当前 堆表空间 。

3  heapTableSpace ：   就是每一个 堆表 空间的 大小 ， 可以设为 1MB ， 每次申请 新的 堆表空间 就是 申请 heapTableSpace 大小的 一个 内存块 。

EnLargableList  还会 保存这样一些 字段 ：

1  appendPtr ， append 指针 ， 存储一个 64位地址 ， EnLargableList 写入数据时从 append指针 指向的数据开始写 ， 每写入一段数据 ， append 指针会移动到这段数据之后的位置 。

2  currentHeapTableSpace ， 当前 堆表空间 ， 即 append 指针 指向的 位置 所在的 堆表空间 。 这个字段用来 归还 堆表空间 。 归还 是指 ， 当 末尾一个 堆表空间 ， 即 当前 堆表空间 的 空间 全部 空闲出来时候 ， 会将 堆表空间 归还 堆 。 仅仅凭 append 指针 不能知道 append 指针 所在的 堆表空间 ， 所以还需要这个字段来记录 append 指针 所在的 堆表空间 ， 即 当前 堆表空间 。

3  recycleFreeItem ， 碎片回收 时 指向 空闲的项位置 ， 即 “碎片” ， 或者说  “已删除”的项 。

4  recycleScanItem ， 碎片回收 时 会先扫描 “碎片” ， 扫描到一个 “碎片” 之后 ， 会将 recycleFreeItem 指向这个 “碎片” 的位置 。 然后会扫描 堆表项 ， 每扫描一个 堆表项 ， 会检查 堆表项 的 子项 （子索引项  Free Space项） ， 若 子项 的 位置 大于 recycleFreeItem 指向的位置 ， 则将 子项 移动到 recycleFreeItem 指向的位置 ， “填补”这个碎片 ， 同时修改 当前扫描的 堆表项 中保存的 该 子项 的位置 。 这样就完成一个 “碎片” 的 回收 （“填补”） 。

    然后就继续 扫描下一个 “碎片” ， 扫描到 “碎片” 后 ， 又接着扫描 上一次 扫描的 堆表项 。 怎么知道 上一次扫描的 堆表项 ？ 就是 recycleScanItem 指向的堆表项 。 不过这样看起来 ， 还要加一个 字段 ， 来表示 扫描到了 堆表项 里的 哪个子项 ， 如下 ：

5  recycleScanSubItem ， 表示 扫描到的 堆表项 的 子项 。 这个字段只要 8 位整数 就可以了 。

6  fragmentCount ， 表示 “碎片” 数量 ， 每次 删除 堆表项 时 加 1 ， 在 碎片回收 “填补” 碎片 的时候 减 1 ， 这个字段用于上文中 如果 fragmentCount 的数量达到 whenRecycleFragment 的值 的 时候 ， 就开始 碎片回收 。

7  堆表空间 的 useCount ， 这个 字段 是 每个 堆表空间 保存 1 个 ， 就是 堆表空间 的 useCount ， 就是 堆表空间 使用的计数（以 堆表项 为单位） 。 每写入 1 个堆表项 ， 就在 堆表空间 的 useCount 加 1 ， 每删除 1 个 堆表项 ， useCount 就 减 1 。 useCount 为 0 表示 堆表空间 

每次 分配 和 回收 之后会 检查 fragmentCount ， 当 fragmentCount 超过 whenRecycleFragment 时 会开始回收 。 由于不希望回收占用太多时间 ， 可以设定 一个参数比如 recycleItemCount ， 比如 300 ， 表示 不管有没有回收完 ， 只 扫描 300 个堆表项 。 

但这样会有一个问题 ， 本身要 fragmentCount 超过 whenRecycleFragment 时才开始回收 ， 而且每次又不回收完 ， 空闲出来的 碎片空间 得不到重复利用 ， append 指针 只能 一直向后移动 ， 所以可能导致 永远回收 不完 ， 堆表 持续 增长 。

所以        ……

我们这里有了一个 突破 ， 即对于 堆表 的 碎片回收 ， 我们采用了一个 新的算法 ， 就是在 堆表项 里 增加 1 个字段 ：   fragmentNext   。

就是把 已删除的堆表项（碎片） 用链表的方式 连接 起来 ， 这样每次写入 堆表项 的时候从 这个 链表 的 头 取出 一个 碎片 ， 作为 新的堆表项 的 写入位置 。 fragmentNext 表示 下一个 碎片 的 位置 ， 或者说 ， fragmentNext 是一个指针 ， 指向下一个 碎片 。 

实际上 是一个用 链表 实现 的 队列 。

所以 ， 需要在 基础元数据区 里增加 2 个字段  fragmentListHead  ,   fragmentListTail ， 用于保存 碎片链表（队列） 的 头指针  和   尾指针。

每次 删除 堆表项 时 ， 将 被删除的 堆表项 的 标识字节 更新为 0 ， 表示 已删除 ， 同时将 堆表项 添加到 碎片队列 的 尾部 。

如果是 第一次 删除 ， 那么 碎片队列 里 还没有 元素 ， 则 将 头指针 和 尾指针 都指向 堆表项 。

每次写入 堆表项 的时候 ， 会先从 碎片队列 里 取得碎片 ， 作为写入位置 ， 如果 碎片队列 为空 ， 才会将 append 指针 作为写入位置 。

fragmentNext 指针也是一个 64位无符号整数 ( uInt64 ) ， 所以也占用 8 个字节 。 这样的话 ， 索引项 和 Free Space 项 的 大小 都是 34 + 8 = 42 个字节了 。

好的 ， 现在我们再来看看在这种算法下 ， 如何 回收 碎片 。  （这里的 “碎片” 是指 堆表 里的 碎片 ， 不是 堆 里的 碎片）

实际上 ， 在这个算法下 ， 碎片可以得到充分的利用 （每次 写入 都优先 从 碎片队列 中取得 碎片 作为写入位置 ， 碎片队列 为空才会用 append 指针 的方式） ， 所以 看起来 堆表 不会无理增长 。 但又一些特殊的情况 ， 比如 应用程序 先申请了 大量的 小块内存 ， 造成了 大量 的 Free Space ， 为了存储这些 Free Space ， 堆表 会变得很大 ， 之后 应用程序 又归还了 所有 或者 大部分 内存块 ， 也是 Free Space 会变得 很少 ， 此时 堆表 中就会产生大量 空闲空间（碎片） ， 这些 空闲空间 如果 长时间不用又不归还 堆 ， 也是一种浪费 。 

我们可以这样来设计 堆表 的 碎片回收 算法 ：

首先 ， 只有 碎片数量 大于 某个值 的时候 ， 才会开始回收 。 比如 大于 1000 个碎片（约 1 MB） 。

从 初始空间 开始 ， 向后遍历每一个 堆表空间 ， 如果 堆表空间 的 useCount 为 0 ， 则可以考虑 释放 这个 堆表空