如何将一个项目列表映射到另一个桶列表中，为每个项目提供一个键？

Question

我有一个项目列表，比如List<Item> listOfItems，每个项目都有一个键，比如String cluster_key。我希望将具有相同cluster_key的所有项聚集到一个桶中，并给出结果List<Bucket> listOfBuckets。桶的列表从空开始。

对于如何实现这个优雅的Java，有什么建议吗？也许用哈希？

我可以想到两个不太优雅的实现：

• 蛮力，我们遍历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

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

但是，如果使用HashMap作为bucketList，则可以在恒定时间内将项添加到桶中，这将为您提供一个具有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);
}