java - 优于 O(n²) 复杂度的列表中列表的查找算法

Question

我使用的是 Java 1.6。我有一组项目，每个项目都有一个名称和一组组件。每个组件也有一个名称。

Set<Item>

Class Item
    String name
    Set<Component>

Class Component
    String name

我现在的任务是编写一个方法，输入:项目名称 + 组件名称，输出:项目列表中是否存在这一对。

public boolean hasItemComponentPair(String itemName, String componentName)
{
    for(Item item : getItems())
    {
        if (item.getName() == itemName)
        {
            for(Component component : item.getComponents())
            {
                if (component.getName() == componentName)
                {
                    return true;
                }
            }
        }
    }

    return false;
}

最简单的方法是逐个遍历集合的元素，如果找到匹配则中断。这种方法适用于小集合。

我的项目集通常在 5 到 20 个项目之间，组件集大致相同。所以有 25 到 400 个独特的项目组件对。对于朴素算法来说，这个数量对似乎太大了，效率不高，尤其是在多次调用该方法的情况下。但我也认为分而治之的技术对于给定数量的元素来说过于冗长。

这个问题通常使用什么数据结构和算法，请记住集合的给定大小？

Answer 1

如果你可以改变你的 Item 类，你可以这样做:

class Item {
    String name;
    Map<String, Component> components; 
}

在上面的映射中，键是组件的名称。

比将您的代码更改为:

public boolean hasItemComponentPair(String itemName, String componentName)
{
    for(Item item : getItems())
    {
        if (item.getName().equals(itemName))
        {
            return item.getComponents().containsKey(componentName);
        }
    }

    return false;
}

现在你只需要遍历一个集合。