java在O（n）java8流中寻找两个列表的交集

Question

我有两个列表，参考资料和表格参考资料。我想根据一个条件找到两个列表的交集，即subscriberId+“”+tableName，因为两个列表是相同的。我能在O（N^2）时间内实现这一点。我想在O（N）时间内使用Java8流做同样的事情

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class intersectionStream {
    private static class Resource {
        String subscriberId;
        String tableName;
        List<String> buyers;

        public Resource(String subscriberId, String tableName) {
            this.subscriberId = subscriberId;
            this.tableName = tableName;
        }

        @Override
        public String toString() {
            return "TableResource{" +
                    "subscriberId='" + subscriberId + '\'' +
                    ", tableName='" + tableName + '\'' +
                    ", buyers=" + buyers +
                    '}';
        }

        public String getResourceString() {
            return this.subscriberId + "_" + this.tableName;
        }

    }

    private static class TableResource {
        String subscriberId;
        String tableName;

        public TableResource(String subscriberId, String tableName) {
            this.subscriberId = subscriberId;
            this.tableName = tableName;
        }

        public String getTableResource() {
            return this.subscriberId + "_" + this.tableName;
        }

        @Override
        public String toString() {
            return "GlobalTableResource{" +
                    "subscriberId='" + subscriberId + '\'' +
                    ", tableName='" + tableName + '\'' +
                    '}';
        }
    }

    public static void main(String[] args) {
        List<Resource> resources = new ArrayList<>();
        List<TableResource> tableResources = new ArrayList<>();
        HashSet<String> commonResources = new HashSet<>();

        resources.add(new Resource("1", "table1"));
        resources.add(new Resource("2", "table2"));
        resources.add(new Resource("3", "table3"));
        resources.add(new Resource("3", "table4"));
        resources.add(new Resource("3", "table5"));


        tableResources.add(new TableResource("2", "table2"));
        tableResources.add(new TableResource("3", "table3"));
        tableResources.add(new TableResource("5", "table5"));
        tableResources.add(new TableResource("6", "table6"));

        for(Resource resource : resources) {
            for(TableResource tableResource : tableResources) {
                if(tableResource.getTableResource().equals(resource.getResourceString())) {
                    commonResources.add(tableResource.getTableResource());
                }
            }

        }

        System.out.println("Hashset is : " + commonResources);
    }
}

期望的输出是：哈希集是：[2_table2，3_table3]

Answer 1

试试这个：

Set<String> resourceStrings = resources.stream()
                                       .map(Resource::getResourceString)
                                       .collect(toCollection(HashSet::new));

Set<String> commonResources = tableResources.stream()
                                            .map(TableResource::getTableResource)
                                            .filter(resourceStrings::contains)
                                            .collect(toSet());

---

说明：

收集到HashSet需要线性时间O(n)，而HashSet::contains需要恒定时间O(1)。 因此，一旦你有了一个HashSet，你可以在O(n)时间内简单地迭代第二个集合。 总体复杂度为O(n + n)或O(2n)。常量因子被大O符号抑制。因此，由此产生的复杂性被认为是O(n)

Answer 2

你可以试试下面的方法

Set<String> tableResourcesSet = tableResources.stream()
                .map(TableResource::getTableResource)
                .collect(Collectors.toSet());

resources.stream()
        .map(Resource::getResourceString)
        .filter(tableResourcesSet::contains)
        .collect(Collectors.toSet());