java - 给定每个项目的键，如何将项目列表映射到另一个存储桶列表？

Question

我有一个项目列表，比如说 List<Item> listOfItems每个项目都有一个键，比如 String cluster_key .我想用相同的 cluster_key 对所有项目进行聚类放入桶中，给出结果 List<Bucket> listOfBuckets .桶列表一开始是空的。

关于如何优雅地使用 Java 做这件事有什么建议吗？也许用哈希？

我能想到 2 个不够优雅的实现:

• 蛮力，我们遍历listOfItems ，并且对于每个项目，遍历存储桶列表直到找到匹配项。如果我们找到匹配项，则将该项目添加到存储桶中。否则，

.

for item in listOfItems {
    for bucket in listOfBuckets {
        if item.getKey() equals bucket.getKey()
            add item to bucket
        else
            create new bucket
            add item to bucket
            add bucket to listOfBuckets
    }
}

• 排序，然后聚类:

.

sort listOfItems by their cluster_key;
get first item from listOfItems;
create a bucket, currentBucket, with key: firstItem.getKey()
add first item to bucket
for item in listOfItems, starting at the second item {
    if item.getKey() equals currentBucket.getKey()
        add item to currentBucket
    else
        create new bucket
        add item to new bucket
        add new bucket to listOfBuckets
        set new bucket to currentBucket
}

Answer 1

按相同键对项目进行分组的最快方法是遍历列表并将每个项目添加到正确的存储桶(在需要时创建存储桶)，这与您的第一个示例类似。

但是，如果您对 bucketList 使用 HashMap，则可以在常数时间内将项目添加到您的存储桶，这将为您提供 O(n) 而不是 O(n^2) 复杂度的算法。

没有测试，但你明白了

HashMap<String,ArrayList<Item>> bucketList = new HashMap();

for (Item i : listOfItems) {
    if(!bucketList.containsKey(i.getKey()) {
        bucketList.put(i.getKey(),new ArrayList());
    }

    buckList.get(i.getKey()).add(item);
}