Scala不可变Seq追加元素内存过高及与ArrayBuffer差异问题

问题1：不可变Seq追加元素内存未复用的成因与验证方法 #

你碰到的现象核心是Scala默认不可变Seq的实现特性导致的：

• Scala 2中默认的scala.collection.immutable.Seq实现是List，这是一个单向链表结构，它的prepend（+:）操作是O(1)的，会直接复用原有链表的全部节点，仅新增一个头节点，内存开销极小。但append(:+)操作是O(n)的：因为单向链表只能从表头遍历到表尾，要追加元素必须重新构建整个链表的所有节点，所以你看到追加1个元素的内存开销和新建100万元素的Seq完全一致。
• 如果要享受到不可变序列的内存复用+高效追加能力，应该用scala.collection.immutable.Vector，它的底层是分块的前缀树结构，追加操作是均摊O(1)的，绝大多数原有块都会被复用，仅新增少量树节点和数据块，内存增幅会远低于全量拷贝。

验证内存复用的方法：

• 替换Seq为Vector重复测试，你会看到步骤4的内存涨幅会降到KB级别
• 用JOL（Java Object Layout）工具打印序列的内部结构，对比追加元素前后的内部节点内存地址，可直接确认原有数据块被复用
• 对比prepend和append操作的内存开销差异，List的+: 操作内存增幅仅为一个Cons节点的大小（约24字节），和你最初的预期一致。

问题2：ArrayBuffer和Seq内存占用差异的成因 #

这个差异完全是两种数据结构的底层存储设计决定的：

• ArrayBuffer底层是对象数组，每个元素仅存储一个对象引用，64位JVM开启指针压缩的前提下，单个引用占4字节，100万元素的数组内存开销就是1000000 * 4B = 4MB，和你的测试结果完全吻合。
• 前面提到默认的Seq是List，每个元素对应一个::（Cons）节点，每个Cons节点除了存储元素引用，还要存储下一个节点的引用，加上JVM对象头的开销，单个Cons节点在开启指针压缩的64位JVM上的内存占用为24字节（12字节对象头 + 2个4字节引用 + 4字节对齐填充），100万元素的总开销就是1000000 * 24B = 24MB，和你的测试结果完全匹配。

内容的提问来源于stack exchange，提问作者Dr Y Wit