Select a Random Key from a HashMap in Java

1. Overview

Maps are fundamental data structures we might use every day in our code. At the same time, its main benefit, constant time access, in some cases might create problems when we try to combine it with accessing random elements in a map. This is a relatively rare case; at the same time, when we need to achieve this, it’s unclear how to do it efficiently.

In this tutorial, we’ll review several methods for accessing random elements from a map and discuss their advantages and disadvantages. Based on the tradeoffs, we can pick the most suitable approach for us.

2. Using a Random Number

If we consider this task in the context of a simple ArrayList, we won’t encounter any issues with the solution. Thus, we can consider a few options in which picking a random number would be one of the crucial steps.

2.1. Converting to an ArrayList

The most straightforward solution is to get a random key by converting a key set into an ArrayList and accessing an element using a random index:

public <K, V> V getRandomValueUsingList(Map<K, V> map) {
    if (map == null || map.isEmpty()) {
        return null;
    }

    List<K> keys = new ArrayList<>(map.keySet());
    K randomKey = keys.get(ThreadLocalRandom.current().nextInt(keys.size()));
    return map.get(randomKey);
}

While this solution appears simple, it has a significant drawback: it requires additional space. Also, even though the access to a random element in the ArrayList is constant, we have a hidden time complexity. The time complexity cannot be less than the space complexity. We need n iterations to copy or convert a set of length n to an array. However, if we can reuse the same array multiple times and the original set doesn’t change significantly, this solution may show good overall performance.

To use this function, we need to pass an original map and then we can retrieve a random value from it:

private final RandomNumberMap randomNumberMap = new RandomNumberMap();

@Test
public void whenGettingRandomValue_thenValueExistsInMap() {
    Map<String, Integer> map = new HashMap<>();
    map.put("apple", 1);
    map.put("banana", 2);
    map.put("cherry", 3);
    map.put("date", 4);
    map.put("elderberry", 5);

    Integer randomValue = randomNumberMap.getRandomValueUsingList(map);

    assertNotNull(randomValue);
    assertTrue(map.containsValue(randomValue));
}

Since our goal is to randomize the result, we cannot make any assumptions about the values we’re getting. However, the code should return only the values that were present in the original map.

2.2. Using Iteration

For cases where we need to perform this operation rarely or the original set changes frequently, we can use iteration directly on the set. It won’t allow indexed access, but we can skip a specific number of elements:

public <K, V> V getRandomValueUsingOffset(Map<K, V> map) {
    if (map == null || map.isEmpty()) {
        return null;
    }

    int randomOffset = ThreadLocalRandom.current().nextInt(map.size());
    Iterator<Entry<K, V>> iterator = map.entrySet().iterator();
    for (int i = 0; i < randomOffset; i++) {
        iterator.next();
    }

    return iterator.next().getValue();
}

Although this solution appears inferior to the first one, it would actually yield better results for one-off operations. Thus, we should consider how often and where this piece of code would be used, as well as the boundaries on the number of elements. The example of the usage is pretty similar to the previous implementation.

3. Shuffling a Set

Another approach, which might be overkill, is to shuffle the entire array and pick the first element. This approach would still require converting the set into an ordered collection:

public <K, V> K getRandomKeyUsingShuffle(Map<K, V> map) {
    if (map == null || map.isEmpty()) {
        return null;
    }

    List<K> keys = new ArrayList<>(map.keySet());
    Collections.shuffle(keys);

    return keys.get(0);
}

The time complexity of this approach is worse than the previous options. However, this one has a very nice quality: we can deplete the shuffled collection until it’s empty. In this case, we can use this collection as a source of randomized values. However, this would prevent the same values from appearing in the same randomization session, so it might not be appropriate for all cases.

Additionally, although we don’t pass ThreadLocalRandom or Random to the shuffle() function, it would be created internally. Therefore, this approach requires all the features we’ve used in the previous ones and may be desirable only for specific cases and requirements.

4. Custom Wrapper

However, if we require an implementation that works efficiently even when the map is frequently updated and we need proper randomization, we can build a custom solution. We’ll start with a simple wrapper and expose only basic operations:

public class RandomKeyTrackingMap<K, V> {

    private final Map<K, V> delegate = new HashMap<>();
    private final List<K> keys = new ArrayList<>();

    public void put(K key, V value) {
        V previousValue = delegate.put(key, value);
        if (previousValue == null) {
            keys.add(key);
        }
    }

    public V remove(K key) {
        V removedValue = delegate.remove(key);
        if (removedValue != null) {
            int index = keys.indexOf(key);
            if (index >= 0) {
                keys.remove(index);
            }
        }
        return removedValue;
    }

    public V getRandomValue() {
        if (keys.isEmpty()) {
            return null;
        }

        int randomIndex = ThreadLocalRandom.current().nextInt(keys.size());
        K randomKey = keys.get(randomIndex);
        return delegate.get(randomKey);
    }

}

The main issue is the remove() operation, as we need to remove a value from both a map and a list. However, to make this operation performant, we should add another data structure to track the indexes to the keys:

private final Map<K, V> delegate = new HashMap<>();
private final List<K> keys = new ArrayList<>();
private final Map<K, Integer> keyToIndex = new HashMap<>();

public void put(K key, V value) {
    V previousValue = delegate.put(key, value);
    if (previousValue == null) {
        keys.add(key);
        keyToIndex.put(key, keys.size() - 1);
    }
}

We can improve the solution and use swap instead of remove, so we continuously remove the last element, making the operation constant:

public V remove(K key) {
    V removedValue = delegate.remove(key);
    if (removedValue != null) {
        Integer index = keyToIndex.remove(key);
        if (index != null) {
            removeKeyAtIndex(index);
        }
    }
    return removedValue;
}

private void removeKeyAtIndex(int index) {
    int lastIndex = keys.size() - 1;
    if (index == lastIndex) {
        keys.remove(lastIndex);
        return;
    }

    K lastKey = keys.get(lastIndex);
    keys.set(index, lastKey);
    keyToIndex.put(lastKey, index);
    keys.remove(lastIndex);
}

While it adds some code, it makes this approach work in amortized linear time. After the implementation, we can use the map in the following way:

@Test
public void whenGettingRandomValue_thenValueExistsInMap() {
    OptimizedRandomKeyTrackingMap<String, Integer> map = new OptimizedRandomKeyTrackingMap<>();
    map.put("apple", 1);
    map.put("banana", 2);
    map.put("cherry", 3);

    Integer randomValue = map.getRandomValue();

    assertNotNull(randomValue);
    assertTrue(Arrays.asList(1, 2, 3).contains(randomValue));
}

Also, this implementation allows us to remove the values via the wrapper (the previous ones could use a reference to the original map, but it might cause hard-to-debug issues):

@Test
public void whenRemovingValue_thenRandomValueDoesNotContainRemovedEntry() {
    OptimizedRandomKeyTrackingMap<String, Integer> map = new OptimizedRandomKeyTrackingMap<>();
    map.put("apple", 1);
    map.put("banana", 2);
    map.put("cherry", 3);

    map.remove("banana");

    Integer randomValue = map.getRandomValue();

    assertNotNull(randomValue);
    assertTrue(Arrays.asList(1, 3).contains(randomValue));
}

We can expand the wrapper with additional methods and functionalities based on the requirements and the context in which we plan to use this class.

5. Extending a HashMap

A map itself contains information about the internal values and nodes. However, the table is an array of buckets. While we can pick the buckets uniformly, we cannot do this with the elements, since some buckets might be empty or contain multiple elements. The entrySet has the same problem as a Map (it also uses a Map internally), so we cannot get a random value from an unordered collection:

// Rest of HashMap implementation

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;

/**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 * for keySet() and values().
 */
transient Set<Map.Entry<K,V>> entrySet;

// Rest of HashMap implementation

At the same time, we can create a new map implementation. This would allow the class to be seamlessly integrated into the rest of the code. However, this approach requires more code, since we need to satisfy all the Map methods and ensure that we won’t break anything:

public class RandomizedMap<K, V> extends HashMap<K, V> {
    
    private final Map<Integer, K> numberToKey = new HashMap<>();
    private final Map<K, Integer> keyToNumber = new HashMap<>();
    @Override
    public V put(K key, V value) {
        V oldValue = super.put(key, value);
        
        if (oldValue == null) {
            int number = this.size() - 1;
            numberToKey.put(number, key);
            keyToNumber.put(key, number);
        }
        
        return oldValue;
    }
    
    @Override
    public V remove(Object key) {
        V removedValue = super.remove(key);
        
        if (removedValue != null) {
            removeFromTrackingMaps(key);
        }
        
        return removedValue;
    }
    
    public V getRandomValue() {
        if (this.isEmpty()) {
            return null;
        }
        
        int randomNumber = ThreadLocalRandom.current().nextInt(this.size());
        K randomKey = numberToKey.get(randomNumber);
        return this.get(randomKey);
    }
    // Other methods
}

The remove functionality should cover more cases compared to the previous example:

private void removeFromTrackingMaps(Object key) {
    @SuppressWarnings("unchecked")
    K keyToRemove = (K) key;
    
    Integer numberToRemove = keyToNumber.get(keyToRemove);
    if (numberToRemove == null) {
        return;
    }
    
    int mapSize = this.size();
    int lastIndex = mapSize;
    
    if (numberToRemove == lastIndex) {
        numberToKey.remove(numberToRemove);
        keyToNumber.remove(keyToRemove);
    } else {
        K lastKey = numberToKey.get(lastIndex);
        if (lastKey == null) {
            numberToKey.remove(numberToRemove);
            keyToNumber.remove(keyToRemove);
            return;
        }
        
        numberToKey.put(numberToRemove, lastKey);
        keyToNumber.put(lastKey, numberToRemove);
        
        numberToKey.remove(lastIndex);
        
        keyToNumber.remove(keyToRemove);
    }
}

This is a more complex solution that requires aligning it with the Map interface. Therefore, it’s the best option when the class should align with the Map interface in other parts of the code.

6. Conclusion

Object-oriented programming languages (and almost all languages in general) allow us to create customized solutions for the problems we face. For some reason, this quality is often overlooked. When standard libraries don’t provide solutions or features out of the box, developers encounter problems with them. It’s important to remember that if we don’t have a specific functionality, we can always build it from scratch.

As usual, all the code from this tutorial is available over on GitHub.