eugenp · maibin · Nov 17, 2025 · Nov 7, 2025 · Nov 11, 2025
diff --git a/...ons-maps-9/src/main/java/com/baeldung/map/randommapkey/OptimizedRandomKeyTrackingMap.java b/...ons-maps-9/src/main/java/com/baeldung/map/randommapkey/OptimizedRandomKeyTrackingMap.java
@@ -0,0 +1,57 @@
+package com.baeldung.map.randommapkey;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.ThreadLocalRandom;
+
+public class OptimizedRandomKeyTrackingMap<K, V> {
+
+    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);
+        }
+    }
+
+    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);
+    }
+
+    public V getRandomValue() {
+        if (keys.isEmpty()) {
+            return null;
+        }
+
+        int randomIndex = ThreadLocalRandom.current().nextInt(keys.size());
+        K randomKey = keys.get(randomIndex);
+        return delegate.get(randomKey);
+    }
+}
+
diff --git a/...a-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomKeyShuffleMap.java b/...a-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomKeyShuffleMap.java
@@ -0,0 +1,21 @@
+package com.baeldung.map.randommapkey;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+
+public class RandomKeyShuffleMap {
+
+    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);
+    }
+}
+
diff --git a/...-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomKeyTrackingMap.java b/...-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomKeyTrackingMap.java
@@ -0,0 +1,43 @@
+package com.baeldung.map.randommapkey;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.ThreadLocalRandom;
+
+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);
+    }
+
+}
+
diff --git a/...-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomNumberMap.java b/...-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomNumberMap.java
@@ -0,0 +1,35 @@
+package com.baeldung.map.randommapkey;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.concurrent.ThreadLocalRandom;
+
+public class RandomNumberMap {
+
+    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);
+    }
+
+    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();
+    }
+}
diff --git a/...re-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomizedMap.java b/...re-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomizedMap.java
@@ -0,0 +1,101 @@
+package com.baeldung.map.randommapkey;
+
+import java.util.HashMap;
+import java.util.Map;
+import java.util.concurrent.ThreadLocalRandom;
+
+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 void putAll(Map<? extends K, ? extends V> m) {
+        for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
+            put(entry.getKey(), entry.getValue());
+        }
+    }
+
+    @Override
+    public V remove(Object key) {
+        V removedValue = super.remove(key);
+
+        if (removedValue != null) {
+            removeFromTrackingMaps(key);
+        }
+
+        return removedValue;
+    }
+
+    @Override
+    public boolean remove(Object key, Object value) {
+        boolean removed = super.remove(key, value);
+
+        if (removed) {
+            removeFromTrackingMaps(key);
+        }
+
+        return removed;
+    }
+
+    @Override
+    public void clear() {
+        super.clear();
+        numberToKey.clear();
+        keyToNumber.clear();
+    }
+
+    public V getRandomValue() {
+        if (this.isEmpty()) {
+            return null;
+        }
+
+        int randomNumber = ThreadLocalRandom.current().nextInt(this.size());
+        K randomKey = numberToKey.get(randomNumber);
+        return this.get(randomKey);
+    }
+
+    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);
+        }
+    }
+}
diff --git a/...-9/src/test/java/com/baeldung/map/randommapkey/OptimizedRandomKeyTrackingMapUnitTest.java b/...-9/src/test/java/com/baeldung/map/randommapkey/OptimizedRandomKeyTrackingMapUnitTest.java
@@ -0,0 +1,51 @@
+package com.baeldung.map.randommapkey;
+
+import java.util.Arrays;
+
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+import org.junit.Test;
+
+public class OptimizedRandomKeyTrackingMapUnitTest {
+
+    @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));
+    }
+
+    @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));
+    }
+
+    @Test
+    public void whenRemovingAllEntries_thenRandomValueReturnsNull() {
+        OptimizedRandomKeyTrackingMap<String, Integer> map = new OptimizedRandomKeyTrackingMap<>();
+        map.put("apple", 1);
+
+        map.remove("apple");
+
+        Integer valueAfterRemoval = map.getRandomValue();
+        assertNull(valueAfterRemoval);
+    }
+}
+
diff --git a/...tions-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomKeyShuffleMapUnitTest.java b/...tions-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomKeyShuffleMapUnitTest.java
@@ -0,0 +1,45 @@
+package com.baeldung.map.randommapkey;
+
+import java.util.HashMap;
+import java.util.Map;
+
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+import org.junit.Test;
+
+public class RandomKeyShuffleMapUnitTest {
+
+    private final RandomKeyShuffleMap randomKeyShuffleMap = new RandomKeyShuffleMap();
+
+    @Test
+    public void whenGettingRandomKeyUsingShuffle_thenKeyExistsInMap() {
+        Map<String, Integer> map = new HashMap<>();
+        map.put("apple", 1);
+        map.put("banana", 2);
+        map.put("cherry", 3);
+        map.put("date", 4);
+
+        String randomKey = randomKeyShuffleMap.getRandomKeyUsingShuffle(map);
+
+        assertNotNull(randomKey);
+        assertTrue(map.containsKey(randomKey));
+    }
+
+    @Test
+    public void whenMapIsEmpty_thenReturningNull() {
+        Map<String, Integer> map = new HashMap<>();
+
+        String randomKey = randomKeyShuffleMap.getRandomKeyUsingShuffle(map);
+
+        assertNull(randomKey);
+    }
+
+    @Test
+    public void whenMapIsNull_thenReturningNull() {
+        String randomKey = randomKeyShuffleMap.getRandomKeyUsingShuffle(null);
+
+        assertNull(randomKey);
+    }
+}
+