基于键在 Java 中加入 2 个集合的最快方法

Question

我正在寻找基于公共 id 键合并两个未排序集合的最快方法。

低于 O(N^2) 实现

    for (Person per : pers) {
      for (Data data : datas) {
          if (per.getId().equals(data.getId())) {
              per.getData().add(data);
          }
        } 
      }

我正在寻找实现此结果的最快可能方式（以及尽可能低的内存占用），可能为 O(N)。应从 per.getData() 中删除重复项。现在，per.getData() 是一个 HashSet

知道如何优化吗？我正在使用 java 11

Answer 1

传递一个人以收集到地图中供以后 O(1) 查找，然后传递一个数据将其添加到人：

Map<Object, Person> people = pers.stream()
  .collect(Collectors.toMap(Person::getId, p -> p));
datas.forEach(d -> people.get(d.getId()).add(d));

如果一个数据可能有匹配的人，过滤掉不匹配的数据：

datas.stream()
  .filter(d -> people.containsKey(d.getId()))
  .forEach(d -> people.get(d.getId()).add(d));

两种方式都是O(m+n)（m个人，n数据），因为所有的map操作都是O(1)。

您提到应该从个人数据中删除重复项。作为 HashSet（或任何类型的 Set），如果 equals() 和 hashCode() 为数据正确编码，重复项将自动删除。

Answer 2

这是一个比 O(n^2) 更好但会占用内存的线性方法 (O(n))。

创建一个 HashMap 然后循环人物并将他们插入到地图中。
循环 Datas 并检查 dataId 是否存在于 HashMap 中。如果存在，则获取 personObject 并将 dataObject 添加到其 HashSet。

HashMap<Integer, Person> mp = new HashMap<>();
for (Person per : pers) {
   mp.put(per.getId(), per);
}
for (Data data : datas) {
   if (mp.get(data.getId()) != null) {
      Person person = mp.get(data.getId());
      person.getData().add(data);
      mp.put(person.getId(), person);
   }
}

请注意，我假设您使用整数作为 ID。您可以更改代码以适合您的情况。

基于键在 Java 中加入 2 个集合的最快方法

Fastest way to join 2 collections in Java based on a key

collections

join

java-11