Getting a random element from a Collection-CodePudding

in java I would like to be able to maintain my Collection of fishes sorted by species at all time (hence the use of a HashMap) while being able to pick a random element from all species except one with constant time complexity. For example the following code does the job but with O(number of elements) complexity :

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);

Any idea how to do this with constant time complexity if possible ? Thanks !

CodePudding user response：

What you are performing is filtering, and when filtering you have to check each element whether they need to be taken out or not. You could try to use alphabetical sorting on the keys and stop filtering once the key is alphabetically larger than your filtering (unwanted) key.

Your code can also be thoroughly shortened by using java streams:

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.

CodePudding user response：

The only way I can think of would consist in maintaining an ArrayList<Fish> as well as the map you already have. There is a drawback though: adding or removing fishes would be slightly more complex:

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);
    }
}