Kotlin实现伸展树内存占用过高的优化方案求助

问题背景：用Kotlin实现伸展树，需处理大量增删操作，输出内容达32MB。当前使用MutableList存储层级遍历节点时，最大驻留内存约200MB，改用Array后无改善，需将内存占用控制在128MB以内，且要求每个循环后调整内存使用。

1. 复用集合/数组，避免频繁创建与扩容 #

当前代码每次循环都会重新创建或扩容集合/数组，产生大量内存碎片与临时对象。可以预先计算树的最大层级节点数，复用两个固定大小的数组交替存储当前层与下一层节点，避免重复分配内存：

override fun toString(): String {
    if (ROOT == null) return "_"

    println(ROOT)
    val maxLevelSize = 1 shl (height(ROOT) - 1) // 计算最大层级的节点数（2^(高度-1)）
    var currentLevel = arrayOfNulls<Node>(maxLevelSize)
    var nextLevel = arrayOfNulls<Node>(maxLevelSize)
    currentLevel[0] = ROOT
    var currentCount = 1 // 当前层非null节点数

    for (h in 1 until height(ROOT)) {
        var nextCount = 0
        for (i in 0 until currentCount) {
            val node = currentLevel[i]
            if (node != null) {
                // 处理左子节点
                if (node._LeftChild != null) {
                    nextLevel[nextCount++] = node._LeftChild
                    print("[${node._LeftChild.key} ${node._LeftChild.value} ${node.key}] ")
                } else {
                    print("_ ")
                }
                // 处理右子节点
                if (node._RightChild != null) {
                    nextLevel[nextCount++] = node._RightChild
                    print("[${node._RightChild.key} ${node._RightChild.value} ${node.key}] ")
                } else {
                    print("_ ")
                }
            } else {
                print("_ _ ")
            }
        }
        println()
        // 交换数组复用
        val temp = currentLevel
        currentLevel = nextLevel
        nextLevel = temp
        // 重置下一层数组的填充位置
        nextLevel.fill(null, 0, nextCount)
        currentCount = nextCount
    }
    return " end="
}

• 核心思路：用固定大小的数组替代动态扩容的MutableList，通过数组交换实现复用，避免每次循环创建新集合；用currentCount记录当前层有效节点数，无需存储null节点（仅在输出时处理缺失的子节点）。

2. 减少临时字符串对象开销 #

当前代码频繁调用Node.toString()生成临时字符串，大量临时对象会占用堆内存并增加GC压力。直接在输出时拼接内容，跳过toString()方法：

// 替换原Node.toString()的调用，直接输出
// 原代码：print(ROOTList._LeftChild.toString())
// 修改为：
print("[${node._LeftChild.key} ${node._LeftChild.value} ${node.key}] ")

如果需要生成文件而非控制台输出，改用BufferedWriter批量写入，减少内存中临时字符串的积累：

fun writeTreeToFile(path: String) {
    BufferedWriter(FileWriter(path)).use { writer ->
        // 层级遍历逻辑，将print替换为writer.write()
        writer.write(ROOT.toString())
        // ... 后续遍历的写入逻辑
    }
}

3. 调整JVM参数强制内存限制与优化GC #

通过JVM启动参数直接限制堆内存，并选择适合小内存的垃圾回收器，迫使JVM更积极地回收内存：

/usr/bin/time -v java -Xmx128m -Xms64m -XX:+UseSerialGC -jar outPutFile.jar

• -Xmx128m：设置最大堆内存为128MB
• -Xms64m：设置初始堆内存为64MB
• -XX:+UseSerialGC：使用串行垃圾回收器，适合小内存场景，GC开销更低

4. 优化节点对象内存占用 #

• 给Node类的属性添加@JvmField注解，避免Kotlin自动生成的getter/setter方法带来的微小内存开销：

class Node(val key: Long, var value: String?) {
    @JvmField var _parent: Node? = null
    @JvmField var _RightChild: Node? = null
    @JvmField var _LeftChild: Node? = null
}

• 如果value字符串存在重复，调用value?.intern()将其加入字符串池，减少重复字符串的内存占用。

内容的提问来源于stack exchange，提问作者Sudar Kudr