从集合中获取随机元素

Question

在 java 我希望能够始终维护按物种分类的鱼类集合（因此使用 HashMap），同时能够从所有物种中选择一个随机元素，除了一个具有恒定的时间复杂度。例如，下面的代码完成了这项工作，但复杂度为 O（元素数量）：

import java.util.*;

HashMap<String, ArrayList<Fish>> fishesBySpecies = new HashMap<>();

// Insert some fishes...
// Fish has a String attribute that describes its species
// Now we want to pick a random Fish that isn't from the unwantedSpecies

String unwanted = "unwanted species";
ArrayList<Fish> wantedSpecies = new ArrayList<>();
for (String species : fishesBySpecies.keySet()) {
    if (!Objects.equals(species, unwanted)) {
        wantedSpecies.addAll(fishesBySpecies.get(species));
    }
}

// Finally !
int randomIndex = new Random().nextInt(wantedSpecies.size());
Fish randomElement = wantedSpecies.get(randomIndex);

知道如何在可能的情况下以恒定的时间复杂度做到这一点吗？谢谢！

Answer 1

你做的是过滤，过滤的时候要检查每一个元素是否需要去掉。您可以尝试对键使用字母顺序排序，并在键按字母顺序大于您的过滤（不需要的）键后停止过滤。

您的代码也可以通过使用 java 流来彻底缩短：

HashMap<String, ArrayList<Fish>> fishesBySpecies = new HashMap<>();

// Insert some fishes...
// Fish has a String attribute that describes its species
// Now we want to pick a random Fish that isn't from the unwantedSpecies

String unwanted = "unwanted species";

fishesBySpecies.keySet().stream() // Get the keyset and create a stream out of it
        .filter(key -> !key.equalsIgnoreCase(unwanted)) // If key is not equal to unwanted then leave it in else remove it
        .forEach(filteredKey ->
                wantedSpecies.addAll(fishesBySpecies.get(filteredKey))); // For each key that was left in, we fetch the fishes

或

fishesBySpecies.keySet().stream() // Get the keyset and create a stream out of it
        .forEach(key ->
                {
                    if(!key.equalsIgnoreCase(unwanted))
                    {
                        wantedSpecies.addAll(fishesBySpecies.get(unwanted));
                    }
                }
                ); // iterate and filter at the same time. Faster.

Answer 2

我能想到的唯一方法是维护 ArrayList<Fish> 以及您已有的地图。但是有一个缺点：添加或删除鱼会稍微复杂一些：

Map<String, List<Fish>> fishesBySpecies = new HashMap<>();
List<Fish> wantedFishes = new ArrayList<>();

//...

public void addFish(String species, Fish fish) {
    List<Fish> speciesFishes = fishesBySpecies.get(species);
    if (speciesFishes == null) {
        speciesFishes = new ArrayList<>();
        fishesBySpecies.put(species, speciesFishes);
    }
    speciesFishes.add(fish);
    // also maintain the list of wanted fishes
    if (!unwantedSpecies.equals(species)) {
        wantedFishes.add(fish);
    }
}

从集合中获取随机元素

Getting a random element from a Collection

java

sorting

collections

random-access