java - 缓慢构建路径列表

Question

我正在构建一个哈希列表，表示树中从根到节点的路径。我的函数可以工作，但在大型树结构上它们非常慢 - 有更好的方法吗？我尝试在一个函数中构建列表，但我得到了我不想要的唯一哈希值。

public ArrayList<Integer> makePathList(AbstractTree<String> tree){
    StringBuilder buffer = new StringBuilder();
    ArrayList<Integer> pl = new ArrayList<Integer>();
    ArrayList<StringBuilder> paths = getPaths(tree, buffer);
    for(StringBuilder sb : paths){
        pl.add(sb.toString().hashCode());
    }

    return pl;
}

public ArrayList<StringBuilder> getPaths(AbstractTree<String> tree, StringBuilder parent){
        ArrayList<StringBuilder> list = new ArrayList<StringBuilder>(); 
        parent.append("/");
        parent.append(tree.getNodeName());
        list.add(new StringBuilder(parent));

        if (!tree.isLeaf()){    
            int i = 0;
            Iterator<AbstractTree<String>> child = tree.getChildren().iterator();
            while (i < tree.getChildren().size()){  
                list.addAll(getPaths(child.next(), new StringBuilder(parent)));
                i++;
            }  
        }
        return list;
}

更新:

Marcin 建议在树遍历期间进行散列给出了错误的答案，但也许这就是我所做的方式？

public ArrayList<Integer> getPaths(AbstractTree<String> tree, StringBuilder parent){
    ArrayList<Integer> list = new ArrayList<Integer>();

    parent.append("/");
    parent.append(tree.getNodeName());
    list.add(new StringBuilder(parent).toString().hashCode());

    if (!tree.isLeaf()){    
        int i = 0;
        Iterator<AbstractTree<String>> child = tree.getChildren().iterator();
        while (i < tree.getChildren().size()){

            list.addAll(getPaths(child.next(), new StringBuilder(parent)));
            i++;
        }  
    }
    return list;
}

Answer 1

我认为您的主要问题是您生成的重复数据量:对于树的每个叶子，您将复制通向该叶子的整个路径并计算该路径的哈希值。即，如果一个顶级节点下有 50,000 个叶子节点，则该节点的路径名将被复制 50,000 次，其哈希值将被计算 50,000 次。

如果您可以组织数据，以便将共享路径前缀重新用作叶之间的引用，并且缓存和重新使用这些前缀的哈希计算，则可以大大减少实际需要完成的工作量。