使用列表的HashMap的Java算法优化问题

Question

如果我有以下内容

postcodeToCompaniesList = new HashMap<String, List<Company>>();

经过一些处理后，hashmap有数千个邮政编码，每个邮政编码被映射到一个包含1个或多个Company对象的列表。

现在我想获得前10个最流行的邮政编码，并打印出邮政编码(即"Postcode SW1A 0AA has 50 companies")处的公司数量。

我所采用的方法(我认为这很幼稚)是创建一个Record对象来保存邮政编码和该邮政编码对应的公司数量。然后，我创建一个RecordList对象，用于管理具有最高count值的10个Record对象的列表(见下文)。

RecordList.addRecord(Record record)方法添加records直到添加10，然后只有当count的值高于当前列表中的最低值时才有条件地添加更多。然后对列表进行排序并删除最小的值，从而保持10个元素的计数。

final class Record implements Comparable<Record> {
public String postcode;
public int count;
public Record(String postcode, int count){
this.postcode = postcode;
this.count = count;
}
@Override 
public int compareTo(Record r){
return Integer.valueOf(this.count).compareTo(Integer.valueOf(r.count));
}
}
final class RecordList{
List<Record> top10 = new ArrayList<Record>();

public void addRecord(Record record){
if (this.top10.size() < 10){
this.top10.add(record);
Collections.sort(this.top10);
} else if (record.count > this.top10.get(0).count){
this.top10.add(record);
Collections.sort(this.top10);
this.top10.remove(0);
}
}
}

接下来，我使用一个简单的循环遍历所有键(邮政编码)，并将它们一次一个地添加到RecordList和companyCount中。

RecordList recordList = new RecordList();
Set<String> postcodes = this.postcodeToCompaniesList.keySet();
for(String postcode : postcodes){
int companyCount = this.postcodeToCompaniesList.get(postcode).size();
recordList.addRecord(new Record(postcode, companyCount));
}
System.out.println(gson.toJson(recordList));

这工作。然而，我有一种感觉，这是一种非常低效的方式。也许流媒体会更好??

社区的想法是什么?有没有更好、更优雅的方法来做到这一点?

Answer 1

为了使事情更简单，我假设List of Company是一个List of Strings。我想这个应该可以了:

HashMap<String, Integer> counter = new HashMap<>(); // postcodes counter
postcodeToCompaniesList.forEach((postcode, company) -> counter.put(postcode, company.size()));
counter.entrySet().stream()
.sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
.limit(10)
.forEach(System.out::println);

Answer 2

您可以对条目进行流式处理，按列表大小反向排序，限制为n个条目(在您的示例中为10个)，并在LinkedHashMap中收集它们:

private static Map<String, List<Company>> topN(Map<String, List<Company>> map, int n) {
return map.entrySet()
.stream()
.sorted(Comparator.comparingInt((Map.Entry<String, List<Company>> e) -> e.getValue().size()).reversed())
.limit(n)
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (x, y) -> y, LinkedHashMap::new));
}

并像下面这样使用它，例如获取前7个邮政编码:

topN(postcodeToCompaniesList, 7)
.forEach((k,v) -> System.out.printf("Postcode %s has %d companies.%n", k, v.size()));