比较目录以检查其中一个是否是另一个的子目录

Question

我在类的根目录ArrayList<File> sources中有一个目录数组列表，以及一个在列表中添加新目录的方法addNewSource。

private void addNewSource(File src){
    sources.add(src);
}

现在我需要添加一个新方法来检查新的源是否是列表中现有目录的子目录。假设arraylist有以下目录：

["D:", "E:", "F:"]

现在我将添加两个新目录，一个是"G:"，另一个是"D:Folder"。新方法应为第一个返回false，为第二个

我找到的简单解决方案：

转到父目录并检查它是否存在于列表中，直到我们到达根目录为止。它完成了我的工作，但在处理大列表（1000个目录）时需要花费大量时间，并且新目录位于1500个父目录中。

对于这个问题，你是否有或知道任何更好的、优化的解决方案，不会花费很长的处理时间。请不要使用外部图书馆。

Answer 1

首先，请注意，您不需要查看src的每个"部分"来查看它是否包含在sources中。相反，你可以做一些类似的事情：

ArrayList<File> sources = new ArrayList<>();
boolean addNewSourceToList(File src) throws IOException
{
    Path newPath = src.toPath();
    for(File f : sources)
    {           
        if(newPath.startsWith(f.toPath()))
        {
            return true;            
        }   
    }
    sources.add(src);
    return false;
}

从本质上讲，startsWith()方法为我们进行了逐部分比较

当然，这种算法仍然需要在每次调用方法时查看sources中的每个元素（在最坏的情况下）。因此，如果sources包含1000个项目，则需要进行1000个startsWith()比较。

正如@Holger所建议的，更好的方法是使用Set而不是List。然而，Set.contains()方法是基于元素的.equals()的，并且由于（对于File或Path）没有"子目录"的概念，我们需要做一些特别的事情：我们需要查看src的每个"部分"是否都在sources中。

Set<Path> sourcesSet = new HashSet<>();
boolean addNewSourceToSet(File src) throws IOException
{
    Path newPath = src.toPath();
    // See if contained exactly
    if(sourcesSet.contains(newPath))
    {
        return true;            
    }
    Path parent = newPath.getParent();
    while(parent != null)
    {
        if(sourcesSet.contains(parent))
        {
            return true;
        }
        parent = parent.getParent();                    
    }
    sourcesSet.add(newPath);
    return false;
}

如果我们可以假设src将包含明显少于1000个部分，则该算法将运行得更快，因为它将仅对src的每个部分运行一次contains()方法。