Нахождение пересечения двух списков в потоке O (n) java8

Question

У меня есть два списка, ресурсы и таблицы ресурсов. Я хочу найти пересечение двух списков на основе условия, т.е. subscriberId + "_" + tableName для обоих списков одинаковы. Я могу достичь этого за O (N ^ 2) раз. Я хочу сделать то же самое, используя поток Java8 в O (N) времени.

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);
    }
}

Требуемый выход: Hashset: [2_table2, 3_table3]

Answer 1

Вы можете попробовать, как показано ниже,

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

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

Answer 2

Попробуйте:

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).