Java流按字段分组并按此字段排序计数?

Question

我试图通过在以下实体上使用Java流来获得拥有最大城市的3个国家的国家代码:

城市:

id   | name     | countryCode |
------------------------------
1    | Berlin   | DE          |
2    | Munich   | DE          |
3    | Köln     | DE          |
4    | Paris    | FR          |
5    | Kopenhag | DK          |
...

我尝试了一些东西，但没有像预期的那样工作。那么，获得前3名国家代码(前3名大多是重复的国家代码)的最合适方法是什么?

final Map<String, City> airportCodes2 = airportService.getCities().stream()
.map(City::getCountryCode, Function.identity())
.toMap();

Answer 1

排序

最简单的方法是通过生成Map<String, Long>类型的辅助地图来将数据按countryCode分组，并将每个countryCode与城市数量相关联。

然后在map条目上生成一个流，并按照Value(即:)。

如何实现:

public static List<String> getTopNCodes(List<City> cities,
int limit) {
return cities.stream()
.collect(Collectors.groupingBy( // creates a Map<String, Long>
City::getCountryCode,
Collectors.counting()
))
.entrySet().stream()
.sorted(Map.Entry.<String, Long>comparingByValue().reversed())
.limit(limit) // <- retain top N
.map(Map.Entry::getKey)
.toList();
}

该方法的时间复杂度为O(n * log n)对于排序，这将是一个缺点，如果元素的数量检索它小(像3)，同时数据是巨大的。

我们可以做得更好。

使用Custom Collector

进行部分排序我们可以使用PriorityQueue(这个类是JDK提供的二进制堆的实现)来代替对辅助映射的所有条目进行排序。

为此，可以使用静态工厂方法Collector.of()实现自定义收集器。

PriorityQueue的实例将被用作收集器的可变容器。流中的每个映射项将与堆的根元素进行比较。如果元素更大(条目包含更大的计数)，则将下一个条目添加到队列根。如果超出限制，则应删除根元素。

为了使代码可重用，我们可以对其进行绅士化。第一部分(创建一个中间映射，其中value表示键的频率)保持不变。

public static <T, K> List<K> getTopN(List<T> list,
Function<T, K> keyExtractor,
int limit) {
return list.stream()
.collect(Collectors.groupingBy(
keyExtractor,
Collectors.counting()
))
.entrySet().stream()
.collect(getMaxN(
limit,
Map.Entry.<K, Long>comparingByValue().reversed(),
Map.Entry::getKey
));
}

最小堆式收集器:

public static <T, R> Collector<T, ?, List<R>> getMaxN(int size,
Comparator<T> comparator,
Function<T, R> keyExtractor) {

return Collector.of(
() -> new PriorityQueue<>(comparator),
(Queue<T> queue, T next) -> tryAdd(queue, next, comparator, size),
(Queue<T> left, Queue<T> right) -> {
right.forEach(next -> tryAdd(left, next, comparator, size));
return left;
},
(Queue<T> queue) -> queue.stream().map(keyExtractor).toList(),
Collector.Characteristics.UNORDERED
);
}
public static <T> void tryAdd(Queue<T> queue, T next, Comparator<T> comparator, int size) {
if (queue.size() == size && comparator.compare(queue.element(), next) < 0)
queue.remove(); // if next value is greater than the smallest element in the queue and max size has been exceeded the smallest element needs to be removed from the queue
if (queue.size() < size) queue.add(next);
}