将一个集合划分为具有相同字段的对象的子集？

Question

我目前正在尝试在 java 中实现一个数据结构，并且想将一组输入对象划分为具有相同字段的不同对象子集。

An example use case:

我们想将一个人的列表划分为特定日期出生的人的子列表。

Input: person1 出生于 1990 年，person2 出生于 2000 年，person3 出生于 1990 年。

Output:

1 -> person1, person3

2 -> 人 2

public Map<Integer, List<Foo>> getIntToFooMap(List<Foo> foos) { 
    Map<Integer, List<Foo>> map = new TreeMap<>(); // need keys to be automatically ordered.
    List<Foo> foosWithSameSetId = new ArrayList<>();
    if (!foos.isEmpty) { 
       for (Foo foo: foos) {
           for (Foo foo2: foos) {
               if (foo.getSetId().equals(foo2.getSetId())) {
                   foosWithSameSetId.add(foo2);
               }
           }
        map.put(foo.getSetId(), foosWithSameSetId);
        foosWithSameSetId.clear();
       }
    }
  return map;
 }

上面的代码不是最优的，时间复杂度是二次的，也不是线程安全的。有人能告诉我更好的方法来将 List 或 Set 划分为具有相等字段的对象子集，在本例中为 setId.

Answer 1

试试散列图，它应该为您处理散列，使您的运行时间接近线性。

Answer 2

首先，不需要嵌套循环。您只需获取或创建当前 foo 的 setId 的集合，然后向其中添加 foo：

for (Foo foo : foos) {
    map.computeIfAbsent(foo.getSetId(), i -> new ArrayList<>()).add(foo);
}

相当于：

for (Foo foo : foos) {
    List<Foo> list = map.get(foo.getSetId());
    if(null == list) list = new ArrayList<>();
    list.add(foo);
}

现在，你需要记住时间complexity for your map implementation。

作为替代方案，groupingBy 流收集器将使您的代码更加简洁：

return foos.stream().collect(
        Collectors.groupingBy(Foo::getSetId, TreeMap::new, Collectors.toList()));

Answer 3

正确清晰。这里有更多代码，一个完整的例子。

首先，为Person定义一个class。

package work.basil.example;

import java.time.LocalDate;
import java.util.Objects;

public class Person
{
    // ----------|  Member fields  |----------------------
    public String name;
    public LocalDate birthdate;

    // ----------|  Constructor  |----------------------
    public Person ( String name , LocalDate birthdate )
    {
        this.name = Objects.requireNonNull( name );
        this.birthdate = Objects.requireNonNull( birthdate );
    }

    // ----------|  Object  |----------------------

    @Override
    public String toString ( )
    {
        return "Person{ " +
                "name='" + name + '\'' +
                " | birthdate=" + birthdate +
                " }";
    }

    @Override
    public boolean equals ( Object o )
    {
        if ( this == o ) return true;
        if ( o == null || getClass() != o.getClass() ) return false;
        Person person = ( Person ) o;
        return name.equals( person.name ) &&
                birthdate.equals( person.birthdate );
    }

    @Override
    public int hashCode ( )
    {
        return Objects.hash( name , birthdate );
    }
}

填充一些示例数据。添加到 Java 9 的 Set.of 语法为我们提供了简单的文字语法。

Set < Person > persons = Set.of(
        new Person( "Alice" , LocalDate.of( 1990 , Month.JANUARY , 23 ) ) ,
        new Person( "Bob" , LocalDate.of( 2000 , Month.FEBRUARY , 24 ) ) ,
        new Person( "Carol" , LocalDate.of( 1990 , Month.MARCH , 25 ) )
);

并发

定义Map we want to populate. You mentioned concurrency as an issue, that is, sharing this map across threads. So we should use one of the two classes bundled with Java that implement the ConcurrentMap接口。

这是我制作的图形 table，显示了与 Java 捆绑在一起的各种 Map 实现的属性。

这里我们选择按一定的顺序使用ConcurrentHashMap. The alternative, ConcurrentSkipListMap might be better if you had large numbers of objects, or if you wanted to maintain the keys (Year。

Map < Year, List < Person > > yearToListOfPersonsMap = new ConcurrentHashMap <>();

数据类型

注意数据类型的适当使用。 Java 提供 Year class 来表示整年。所以我们应该使用它。这样做可以使我们的代码更加自我记录。

在 Person class 上，我们使用 LocalDate 表示出生日期。 class 用于没有时间和时区的仅日期值。

多图

我们将从每个人的生日中提取年份作为地图的键。该值是 List 个 Person 个对象，我们向其中添加了相关人员对象。

如果您想消除任何可能的重复 Person 对象被收集，您可以在此处使用 Set 而不是 List。

Map::computeIfAbsent method added in Java 8 does the work of what is known as a multimap, a map where a key leads to a collection of values rather than a single value. Alternatively, you could use a multipmap implementation from a third-party such as the Google Guava 图书馆。

for ( Person person : persons )
{
    yearToListOfPersonsMap.computeIfAbsent(
            Year.from( person.birthdate ) ,
            ( ( Year key ) -> new ArrayList <>() )
    ).add( person )
    ;
}

转储到控制台。

System.out.println( "yearToListOfPersonsMap = " + yearToListOfPersonsMap );

yearToListOfPersonsMap = {2000=[Person{ name='Bob' | birthdate=2000-02-24 }], 1990=[Person{ name='Alice' | birthdate=1990-01-23 }, Person{ name='Carol' | birthdate=1990-03-25 }]}

将一个集合划分为具有相同字段的对象的子集？

Divide a Set into Subsets of objects having equal field?

java

oop

algorithm

treemap

data-structures

并发

数据类型

多图