一个通用树型数据结构表达及其紧凑序列化方法

已于 2023-12-05 16:22:31 修改
阅读量166 收藏
点赞数
文章标签： 数据结构 java
于 2023-12-05 16:02:55 首次发布
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/camelials/article/details/134464402
版权

1. 背景

在面对树型数据结构对象的传输问题中需要对面2个问题：
1、如何表达具备父子关系的树型对象？
2、如何减少该对象在传输过程中的IO？
显然，对于问题1，如果可以定义一个通用的泛型数据结构在将来的类似问题的处理上会更加的方便。对于问题2，显然越小越好。
下面我给出一个完整的实现示例，供大家参考，大家可以copy走本地去调试和体会一番。

2. 树节点泛型对象

  • 树节点泛型对象：TreeNode
package tree.entity;

import lombok.Data;

import java.io.Serializable;
import java.util.LinkedList;
import java.util.List;

/**
 * TreeNode
 *
 * @author chenx
 */
@Data
public class TreeNode<T> implements Serializable {

    private T data;

    private TreeNode<T> parent;

    private List<TreeNode<T>> children;

    public TreeNode(T data) {
        this.data = data;
        this.children = new LinkedList<>();
    }

    /**
     * isRoot
     *
     * @return
     */
    public boolean isRoot() {
        return this.parent == null;
    }

    /**
     * addChild
     *
     * @param child
     * @return
     */
    public TreeNode<T> addChild(T child) {
        TreeNode<T> childNode = new TreeNode<>(child);
        childNode.parent = this;
        this.children.add(childNode);

        return childNode;
    }

    /**
     * getDepth
     *
     * @return
     */
    public int getDepth() {
        return this.isRoot() ? 0 : this.parent.getDepth() + 1;
    }
}
  • 实体对象实例：SyncData
package tree.entity;

import lombok.Data;

import java.io.Serializable;
import java.util.Map;

/**
 * SyncData
 *
 * @author chenx
 */
@Data
public class SyncData implements Serializable {

    private String dn;

    private byte objectClassType;

    private Map<String, String> dataMap;

    public SyncData() {

    }

    public SyncData(String dn, byte objectClassType) {
        this.dn = dn;
        this.objectClassType = objectClassType;
    }

    public SyncData(String dn, byte objectClassType, Map<String, String> dataMap) {
        this.dn = dn;
        this.objectClassType = objectClassType;
        this.dataMap = dataMap;
    }
}

3. 自定义序列化

  • SyncDataCodec
package tree;

import org.apache.commons.collections.MapUtils;
import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.StringUtils;
import tree.entity.SyncData;

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * SyncDataCodec
 *
 * @author chenx
 */
public class SyncDataCodec {

    private SyncDataCodec() {
        // do nothing
    }

    /**
     * serialize
     *
     * @param syncData
     * @return
     */
    public static byte[] serialize(SyncData syncData) throws IOException {
        if (Objects.isNull(syncData)) {
            throw new RuntimeException("the input syncData is null!");
        }

        try (ByteArrayOutputStream out = new ByteArrayOutputStream();
             DataOutputStream outputStream = new DataOutputStream(out)
        ) {
            outputStream.writeUTF(StringUtils.isEmpty(syncData.getDn()) ? "" : syncData.getDn());
            outputStream.writeByte(syncData.getObjectClassType());

            int dataMapSize = MapUtils.isEmpty(syncData.getDataMap()) ? 0 : syncData.getDataMap().size();
            outputStream.writeInt(dataMapSize);

            if (dataMapSize > 0) {
                for (Map.Entry<String, String> entry : syncData.getDataMap().entrySet()) {
                    outputStream.writeUTF(entry.getKey());
                    outputStream.writeUTF(entry.getValue());
                }
            }

            return out.toByteArray();
        }
    }

    /**
     * deserialize
     *
     * @param data
     * @return
     */
    public static SyncData deserialize(byte[] data) throws IOException {
        if (ArrayUtils.isEmpty(data)) {
            throw new RuntimeException("The input bytes data is empty!");
        }

        try (ByteArrayInputStream in = new ByteArrayInputStream(data);
             DataInputStream inputStream = new DataInputStream(in)
        ) {
            String dn = inputStream.readUTF();
            byte objectClassType = inputStream.readByte();
            int dataMapSize = inputStream.readInt();
            Map<String, String> dataMap = new HashMap<>(dataMapSize);
            for (int i = 0; i < dataMapSize; i++) {
                String key = inputStream.readUTF();
                String value = inputStream.readUTF();
                dataMap.putIfAbsent(key, value);
            }

            return new SyncData(dn, objectClassType, dataMap);
        }
    }
}
  • SyncDataTreeCodec
package tree;

import org.apache.commons.lang3.ArrayUtils;
import tree.entity.SyncData;
import tree.entity.TreeNode;

import java.io.*;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * SyncDataTreeCodec
 *
 * @author chenx
 */
public class SyncDataTreeCodec {

    private SyncDataTreeCodec() {
        // just do nothing
    }

    /**
     * serializeSyncDataTree
     *
     * @param syncDataTree
     * @param syncVersion
     * @return
     */
    public static byte[] serialize(TreeNode<SyncData> syncDataTree, long syncVersion) throws IOException {
        if (Objects.isNull(syncDataTree)) {
            throw new RuntimeException("The input syncDataTree is null!");
        }

        try (ByteArrayOutputStream out = new ByteArrayOutputStream();
             DataOutputStream outputStream = new DataOutputStream(out)
        ) {
            outputStream.writeLong(syncVersion);

            // BFS the input treeNode
            Queue<TreeNode<SyncData>> queue = new LinkedList<>();
            queue.add(syncDataTree);

            while (!queue.isEmpty()) {
                int currentLevelNodeSize = queue.size();
                outputStream.writeInt(currentLevelNodeSize);

                for (int i = 0; i < currentLevelNodeSize; i++) {
                    TreeNode<SyncData> currentNode = queue.poll();
                    byte[] currentNodeBytes = SyncDataCodec.serialize(currentNode.getData());
                    outputStream.writeInt(currentNodeBytes.length);
                    outputStream.write(currentNodeBytes);

                    for (TreeNode<SyncData> child : currentNode.getChildren()) {
                        queue.add(child);
                    }
                }
            }

            return out.toByteArray();
        }
    }

    /**
     * deserializeSyncDataTree
     *
     * @param data
     * @return
     */
    public static TreeNode<SyncData> deserialize(byte[] data) throws IOException {
        if (ArrayUtils.isEmpty(data)) {
            throw new RuntimeException("The input bytes data is empty!");
        }

        try (ByteArrayInputStream in = new ByteArrayInputStream(data);
             DataInputStream inputStream = new DataInputStream(in)
        ) {
            // read syncVersion firstly
            inputStream.readLong();

            Queue<TreeNode<SyncData>> queue = new LinkedList<>();
            TreeNode<SyncData> root = null;

            while (inputStream.available() > 0) {
                int currentLevelNodeSize = inputStream.readInt();
                for (int i = 0; i < currentLevelNodeSize; i++) {
                    int currentNodeLength = inputStream.readInt();
                    byte[] currentNodeBytes = new byte[currentNodeLength];
                    if (inputStream.read(currentNodeBytes) != currentNodeLength) {
                        throw new RuntimeException("SyncDataTreeCodec.deserialize() failed: read currentNodeBytes error!");
                    }

                    // Deserialize SyncData
                    SyncData nodeData = SyncDataCodec.deserialize(currentNodeBytes);
                    TreeNode<SyncData> newNode = new TreeNode<>(nodeData);

                    if (root == null) {
                        root = newNode;
                    } else {
                        TreeNode<SyncData> parentNode = queue.peek();
                        if (parentNode != null) {
                            parentNode.addChild(nodeData);
                        }
                    }

                    queue.add(newNode);
                }
            }

            return root;
        }
    }

    /**
     * serializeDefault : just for compare with serialize()
     *
     * @param entryDataTree
     * @param syncVersion
     * @return
     * @throws IOException
     */
    public static byte[] serializeByDefault(TreeNode<SyncData> entryDataTree, long syncVersion) throws IOException {
        if (Objects.isNull(entryDataTree)) {
            throw new RuntimeException("The input entryDataTree is null!");
        }

        try (ByteArrayOutputStream bos = new ByteArrayOutputStream();
             ObjectOutputStream oos = new ObjectOutputStream(bos)) {
            oos.writeLong(syncVersion);
            oos.writeObject(entryDataTree);
            oos.flush();

            byte[] data = bos.toByteArray();

            return data;
        }
    }

    /**
     * deserializeDefault : just for compare with deserialize()
     *
     * @param data
     * @return
     */
    public static TreeNode<SyncData> deserializeByDefault(byte[] data) throws IOException, ClassNotFoundException {
        if (ArrayUtils.isEmpty(data)) {
            throw new RuntimeException("The input data is empty!");
        }

        try (ByteArrayInputStream bis = new ByteArrayInputStream(data);
             ObjectInputStream ois = new ObjectInputStream(bis)) {
            ois.readLong();

            return (TreeNode<SyncData>) ois.readObject();
        }
    }
}

4. 树构造及序列化测试

package tree;

import org.apache.commons.collections.CollectionUtils;
import tree.entity.SyncData;
import tree.entity.TreeNode;

import java.io.IOException;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * Main
 *
 * @author chenx
 */
public class Main {

    public static void main(String[] args) throws IOException {
        TreeNode<SyncData> syncDataTree1 = buildSyncDataTree();
        StringBuilder sb1 = new StringBuilder();
        printSyncDataTreeDnByDFS(syncDataTree1, sb1);
        //printSyncDataTreeDnByBFS(syncDataTree1, sb1);
        System.out.println("==================syncDataTree1==================");
        System.out.println(sb1);

        byte[] data1 = SyncDataTreeCodec.serialize(syncDataTree1, System.currentTimeMillis());
        TreeNode<SyncData> syncDataTree2 = SyncDataTreeCodec.deserialize(data1);
        StringBuilder sb2 = new StringBuilder();
        printSyncDataTreeDnByDFS(syncDataTree2, sb2);
        //printSyncDataTreeDnByBFS(syncDataTree2, sb2);
        System.out.println("==================syncDataTree2==================");
        System.out.println(sb1);

        System.out.println("==================data1.length VS data2.length==================");
        byte[] data2 = SyncDataTreeCodec.serializeByDefault(syncDataTree1, System.currentTimeMillis());
        System.out.println(data1.length + " vs " + data2.length);
    }


    /**
     * buildSyncDataTree
     *
     * @return
     */
    private static TreeNode<SyncData> buildSyncDataTree() {
        AtomicInteger ouIndex = new AtomicInteger(0);
        AtomicInteger personIndex = new AtomicInteger(0);

        int ouDepth = 2;
        int ouBreadthPerNode = 2;
        int personBreadthPerNode = 3;

        SyncData syncData = new SyncData();
        syncData.setDn("OU=根节点,DC=bossFriday,DC=com");
        syncData.setObjectClassType((byte) 1);
        syncData.setDataMap(Map.of("name", "node-0"));

        TreeNode<SyncData> root = new TreeNode<>(syncData);
        recursiveBuildTree(root, ouDepth, ouBreadthPerNode, personBreadthPerNode, ouIndex, personIndex);

        return root;
    }

    /**
     * recursiveBuildTree
     *
     * @param parent
     * @param ouDepth
     * @param ouBreadthPerNode
     * @param personBreadthPerNode
     * @param ouIndex
     * @param personIndex
     */
    private static void recursiveBuildTree(TreeNode<SyncData> parent, int ouDepth, int ouBreadthPerNode, int personBreadthPerNode, AtomicInteger ouIndex, AtomicInteger personIndex) {
        // 末级org节点构建person节点
        if (ouDepth <= 0) {
            for (int i = 0; i < personBreadthPerNode; i++) {
                SyncData currentNode = new SyncData();
                String personName = "用户-" + personIndex.incrementAndGet();
                currentNode.setDn("OU=" + personName + "," + parent.getData().getDn());
                currentNode.setObjectClassType((byte) 2);
                currentNode.setDataMap(Map.of("name", personName));

                parent.addChild(currentNode);
            }

            return;
        }

        for (int i = 1; i <= ouBreadthPerNode; i++) {
            SyncData currentNode = new SyncData();
            String orgName = "部门-" + ouIndex.incrementAndGet();
            currentNode.setDn("OU=" + orgName + "," + parent.getData().getDn());
            currentNode.setObjectClassType((byte) 1);
            currentNode.setDataMap(Map.of("name", orgName));

            TreeNode<SyncData> childNode = parent.addChild(currentNode);

            // 自递归构建下级节点
            recursiveBuildTree(childNode, ouDepth - 1, ouBreadthPerNode, personBreadthPerNode, ouIndex, personIndex);
        }
    }

    /**
     * 深度优先遍历方式打印syncDataTree
     *
     * @param syncDataTree
     * @return
     */
    public static void printSyncDataTreeDnByDFS(TreeNode<SyncData> syncDataTree, StringBuilder stringBuilder) {
        List<TreeNode<SyncData>> children = syncDataTree.getChildren();
        if (CollectionUtils.isEmpty(children)) {
            return;
        }

        for (TreeNode<SyncData> childNode : children) {
            SyncData data = childNode.getData();
            stringBuilder.append(data.getDn() + "\r\n");

            printSyncDataTreeDnByDFS(childNode, stringBuilder);
        }
    }

    /**
     * 广度优先遍历方式打印syncDataTree
     *
     * @param syncDataTree
     * @param stringBuilder
     */
    public static void printSyncDataTreeDnByBFS(TreeNode<SyncData> syncDataTree, StringBuilder stringBuilder) {
        if (Objects.isNull(syncDataTree)) {
            return;
        }

        Queue<TreeNode<SyncData>> queue = new LinkedList<>();
        queue.add(syncDataTree);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode<SyncData> current = queue.poll();
                if (!current.isRoot()) {
                    stringBuilder.append(current.getData().getDn() + "\r\n");
                }

                for (TreeNode<SyncData> child : current.getChildren()) {
                    queue.add(child);
                }
            }
        }
    }
}

5. 运行结果

==================syncDataTree1==================
OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=部门-2,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=用户-1,OU=部门-2,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=用户-2,OU=部门-2,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=用户-3,OU=部门-2,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=部门-3,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=用户-4,OU=部门-3,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=用户-5,OU=部门-3,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=用户-6,OU=部门-3,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=部门-5,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=用户-7,OU=部门-5,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=用户-8,OU=部门-5,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=用户-9,OU=部门-5,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=部门-6,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=用户-10,OU=部门-6,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=用户-11,OU=部门-6,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=用户-12,OU=部门-6,OU=部门-4,OU=根节点,DC=bossFriday,DC=com

==================syncDataTree2==================
OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=部门-2,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=用户-1,OU=部门-2,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=用户-2,OU=部门-2,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=用户-3,OU=部门-2,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=部门-3,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=用户-4,OU=部门-3,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=用户-5,OU=部门-3,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=用户-6,OU=部门-3,OU=部门-1,OU=根节点,DC=bossFriday,DC=com
OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=部门-5,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=用户-7,OU=部门-5,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=用户-8,OU=部门-5,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=用户-9,OU=部门-5,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=部门-6,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=用户-10,OU=部门-6,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=用户-11,OU=部门-6,OU=部门-4,OU=根节点,DC=bossFriday,DC=com
OU=用户-12,OU=部门-6,OU=部门-4,OU=根节点,DC=bossFriday,DC=com

==================data1.length VS data2.length==================
1720 vs 2759

总结

  • ObjectOutputStream.writeObject(obj)本质就是java自带的序列化方式，从上述运行结果可以发现紧凑自定义序列化对比java自带的序列化方式小了很多。在实际的应用中节点实体对象往往信息较多，这里SyncData.dataMap只设置了1对KV，当KV信息越多时自定义紧凑序列化收益将会更加明显。
  • 树的遍历问题中，深度优先（DFS）和广度优先（BFS）是常用的2种方法，由于深度优先（DFS）其实本质就是一个根到子节点的向下自递归过程，因此在自定义序列化时选择了广度优先（BFS）去一个一个去写节点实体数据。对于反序列化而言，其实就是序列化的逆过程：反向一个一个还原节点实体及节点父子关系的过程。
  • 在SyncDataCodec中大家可以参考如何对Map去做自定义紧凑序列化，从代码可以看出，唯一“多写”的信息就是一个Int的dataMapSize，其他的就都是数据信息了。
  • 在Main中的树构造实现中，我用了递归的方式实现了一棵部门节点深度为2/广度为2，末级部门节点人员广度为3的树，而不是通过for - for - for循环嵌套的方式去hard code。

Demo代码不多，不过可能在不参考啥的情况下，自己去实现一个这玩意又会觉得：其实没那么简单。

评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

BossFriday

原创不易，请给作者打赏或点赞!

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值