Java中Tree的序列化

工作中，遇到了在Java里面序列化一颗树、然后反序列化的时候出现Stack Overflow异常的情况。整棵树的层次和在处理每层的当前对象的消耗(在栈上的消耗)累计起来造成了Stack Overflow。
晚上在家里的时候，写了个小程序，实现了Java中对一个Tree的序列化。
这个程序主要想避免层次太深的问题，所以出发点很简单，就是要改变序列化的时候的对象关系，我们要把一个层次的关系变成平的。
这个程序完成了三个版本的序列化方式。先看第一个
第一个版本在写的时候没怎么想：大概的思路是这样的，就是我们对Tree上的每个节点独立序列化，然后我们保存节点间的父子关系，序列化后的结构数据结构是这样的：
NodeCount:4bytes
//每个节点的数据
NodeId:4bytes
Node序列化后的长度:4bytes
Node序列化后的数据:1byte*序列化后的长度
Node的Child个数:4bytes
Child的NodeId:4bytes*Child个数
......表示多个节点数据
其中，NodeId是从0开始自增

完成这个版本后，大概测试了一下，序列化后的长度比Java直接序列化多了14%左右，不爽。

思考了一下，其实NodeId是不需要的，因此，很快的改出了第二个版本，序列化后格式是这样的：
NodeCount:4bytes
//每个节点的数据
Node序列化后的长度:4bytes
Node序列化后的数据:1byte*序列化后的长度
Child的NodeId:4bytes*Child个数
......表示多个节点数据
测试了一下，长度有所减少，但是非常非常不明显，基本上是比Java序列化多了13%，还是不爽。

最后，想了一下，还是把Tree上的所有节点放到一个Array中，都交给Java序列化吧。这个时候，序列化后的格式就变为了
NodeCount:4bytes
Array序列化后的长度:4bytes
Array序列化后的内容
按照宽度优先的方式的每个TreeNode的ChildCount

这次之后，序列化后的数据和直接Java比，相差无几了，比Java直接序列化差不多少1%不到一些。

代码就放附件中了，随便写的，比较乱。

评论

4 楼 vanadies10 2010-09-17  

jameswxx 写道

vanadies10 写道

这个tree2flat的目的，不是为了减小生成的序列化的内容的size，主要是为了避免出现Stack Overflow。把原先的深度变为了广度。

vanadies10兄，你好，不好意思，我还没有明白，stack Overflow应该指的线程栈空间内存不足吧？你说的自定义序列化避免出现Stack Overflow，指的是从序列化数据恢复对象的时候，减少对象数吗？这样子还是为了缩减所占用的内存吧

对于一棵树，我们平时去序列化的时候，是直接序列化这个树的rootNode，而如果要完成rootNode的序列化，那么是要把rootNode的各个成员都序列化好，而去序列化rootNode的各个成员，又需要去把rootNode的各个成员的成员序列化好，这个其实是个深度优先搜索的过程，并且是用递归的方式实现的，所以，在层次很深的时候，有stackoverflow的风险，并且我们是真的遇到了这个问题。
tree2flat是吧一个树变为一个扁平的数组，那么序列化数组的时候，是针对每个元素做序列化，元素之间是互相不影响的。所以，去掉了递归方式的深度优先的搜索，就不会出现stackoverflow的风险了。

3 楼 jameswxx 2010-09-16  

vanadies10 写道

这个tree2flat的目的，不是为了减小生成的序列化的内容的size，主要是为了避免出现Stack Overflow。把原先的深度变为了广度。

vanadies10兄，你好，不好意思，我还没有明白，stack Overflow应该指的线程栈空间内存不足吧？你说的自定义序列化避免出现Stack Overflow，指的是从序列化数据恢复对象的时候，减少对象数吗？这样子还是为了缩减所占用的内存吧

2 楼 vanadies10 2010-09-15  

这个tree2flat的目的，不是为了减小生成的序列化的内容的size，主要是为了避免出现Stack Overflow。把原先的深度变为了广度。

1 楼 jameswxx 2010-09-15  

   我认为即使将tree实现扁平化的序列化，也没有多大的意义，因为其实并没有比tree本身的java默认序列化减少一些字节。
   以TreeMap为例，它的序列化并没有序列化自身，请看TreeMap的writeObject方法
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out the Comparator and any hidden stuff
        s.defaultWriteObject();

        // Write out size (number of Mappings)
        s.writeInt(size);

        // Write out keys and values (alternating)
        for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
            Map.Entry<K,V> e = i.next();
            s.writeObject(e.getKey());
            s.writeObject(e.getValue());
        }
    }

被序列化的数据基本上都是必须的