Getting a random element from a Collection

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 !

Solution

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.