Selecting random key and value sets from a Map in Java

Question

I want to get random keys and their respective values from a Map. The idea is that a random generator would pick a key and display that value. The tricky part is that both key and value will be strings, for example myMap.put("Geddy", "Lee").

Solution 1

HashMap<String, String> x;

Random       random    = new Random();
List<String> keys      = new ArrayList<String>(x.keySet());
String       randomKey = keys.get( random.nextInt(keys.size()) );
String       value     = x.get(randomKey);

Solution 2

This question should be of help to you Is there a way to get the value of a HashMap randomly in Java? and this one also Picking a random element from a set because HashMap is backed by a HashSet. It would be either O(n) time and constant space or it would be O(n) extra space and constant time.

Solution 3

If you don't mind the wasted space, one approach would be to separately keep a List of all keys that are in the Map. For best performance, you'll want a List that has good random-access performance (like an ArrayList). Then, just get a random number between 0 (inclusive) and list.size() (exclusive), pull out the key at that index, and look that key up.

Random rand = something
int randIndex = rand.nextInt(list.size());
K key = list.get(randIndex);
V value = map.get(key);

This approach also means that adding a key-value pair is a good deal cheaper than removing one. To add the key-value pair, you would test to see if the key is already in the map (if your values can be null, you'll have to separately call map.containsKey; if not, you can just add the key-value pair and see if the "old value" it returns is null). If the key is already in the map, the list is unchanged, but if not, you add the key to the list (an O(1) operation for most lists). Removing a key-value pair, though, involves an O(N) operation to remove the key from the list.

If space is a big concern, but performance is less so, you could also get an Iterator over the map's entry set (Map.entrySet()), and skip randIndex entries before returning the one you want. But that would be an O(N) operation, which kinda defeats the whole point of a map.

Finally, you can just get the entry set's toArray() and randomly index into that. That's simpler, though less efficient.

Solution 4

if your keys are integer, or something comparable, you can use TreeMap to do that.

TreeMap<Integer, Integer> treeMap = new TreeMap<>();
int key = RandomUtils.ranInt(treeMap.lastKey());
int value = treeMap.ceilingKey(key);

Solution 5

I would copy the Map into an array and select the entry you want at random. This avoid the need to also lookup the value from the key.

Map<String, String> x = new HashMap<String, String>();
Map.Entry<String,String>[] entries = x.entrySet().toArray(new Map.Entry[0]);
Random rand = new Random();

// call repeatedly
Map.Entry<String, String> keyValue = entries[rand.nextInt(entries.length)];

---

If you want to avoid duplication, you can randomize the order of the entries

Map<String, String> x = new HashMap<String, String>();
List<Map.Entry<String,String>> entries = new ArrayList<Map.Entry<String, String>> (x.entrySet());
Collections.shuffle(entries);
for (Map.Entry<String, String> entry : entries) {
    System.out.println(entry);
}

View more solutions