diff --git a/core-java-modules/core-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/OptimizedRandomKeyTrackingMap.java b/core-java-modules/core-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/OptimizedRandomKeyTrackingMap.java
new file mode 100644
index 000000000000..87541f06f9ed
--- /dev/null
+++ b/core-java-modules/core-java-collections-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/core-java-modules/core-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomKeyShuffleMap.java b/core-java-modules/core-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomKeyShuffleMap.java
new file mode 100644
index 000000000000..9c321b4b4d54
--- /dev/null
+++ b/core-java-modules/core-java-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/core-java-modules/core-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomKeyTrackingMap.java b/core-java-modules/core-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomKeyTrackingMap.java
new file mode 100644
index 000000000000..ba6baf5ca625
--- /dev/null
+++ b/core-java-modules/core-java-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/core-java-modules/core-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomNumberMap.java b/core-java-modules/core-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomNumberMap.java
new file mode 100644
index 000000000000..d1b6dcc9f00b
--- /dev/null
+++ b/core-java-modules/core-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();
+    }
+}
\ No newline at end of file
diff --git a/core-java-modules/core-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomizedMap.java b/core-java-modules/core-java-collections-maps-9/src/main/java/com/baeldung/map/randommapkey/RandomizedMap.java
new file mode 100644
index 000000000000..fe9214f7cacd
--- /dev/null
+++ b/core-java-modules/core-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);
+        }
+    }
+}
\ No newline at end of file
diff --git a/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/OptimizedRandomKeyTrackingMapUnitTest.java b/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/OptimizedRandomKeyTrackingMapUnitTest.java
new file mode 100644
index 000000000000..d620cc3269c8
--- /dev/null
+++ b/core-java-modules/core-java-collections-maps-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/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomKeyShuffleMapUnitTest.java b/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomKeyShuffleMapUnitTest.java
new file mode 100644
index 000000000000..c737522b0c90
--- /dev/null
+++ b/core-java-modules/core-java-collections-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);
+    }
+}
+
diff --git a/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomKeyTrackingMapUnitTest.java b/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomKeyTrackingMapUnitTest.java
new file mode 100644
index 000000000000..122aec2ad544
--- /dev/null
+++ b/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomKeyTrackingMapUnitTest.java
@@ -0,0 +1,56 @@
+package com.baeldung.map.randommapkey;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Arrays;
+
+import org.junit.Test;
+
+public class RandomKeyTrackingMapUnitTest {
+
+    @Test
+    public void whenGettingRandomValue_thenValueExistsInMap() {
+        RandomKeyTrackingMap<String, Integer> map = new RandomKeyTrackingMap<>();
+        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() {
+        RandomKeyTrackingMap<String, Integer> map = new RandomKeyTrackingMap<>();
+        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() {
+        RandomKeyTrackingMap<String, Integer> map = new RandomKeyTrackingMap<>();
+        map.put("apple", 1);
+
+        Integer valueBeforeRemoval = map.getRandomValue();
+        assertEquals(Integer.valueOf(1), valueBeforeRemoval);
+
+        map.remove("apple");
+
+        Integer valueAfterRemoval = map.getRandomValue();
+        assertNull(valueAfterRemoval);
+    }
+}
+
diff --git a/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomNumberMapUnitTest.java b/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomNumberMapUnitTest.java
new file mode 100644
index 000000000000..cfab3a377ecc
--- /dev/null
+++ b/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomNumberMapUnitTest.java
@@ -0,0 +1,99 @@
+package com.baeldung.map.randommapkey;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+import org.junit.Test;
+
+public class RandomNumberMapUnitTest {
+
+    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));
+    }
+
+    @Test
+    public void whenGettingRandomValueMultipleTimes_thenAllValuesAreFromMap() {
+        Map<String, Integer> map = new HashMap<>();
+        map.put("apple", 1);
+        map.put("banana", 2);
+        map.put("cherry", 3);
+
+        Set<Integer> retrievedValues = new HashSet<>();
+        for (int i = 0; i < 100; i++) {
+            Integer value = randomNumberMap.getRandomValueUsingOffset(map);
+            retrievedValues.add(value);
+        }
+
+        assertTrue(map.values().containsAll(retrievedValues));
+    }
+
+    @Test
+    public void whenMapIsEmpty_thenReturnsNull() {
+        Map<String, Integer> emptyMap = new HashMap<>();
+
+        Integer result = randomNumberMap.getRandomValueUsingList(emptyMap);
+
+        assertNull(result);
+    }
+
+    @Test
+    public void whenMapIsNull_thenReturnsNull() {
+        Integer result = randomNumberMap.getRandomValueUsingList(null);
+
+        assertNull(result);
+    }
+
+    @Test
+    public void whenMapHasSingleElement_thenReturnsThatElement() {
+        Map<String, Integer> singleEntryMap = new HashMap<>();
+        singleEntryMap.put("only", 42);
+
+        Integer result = randomNumberMap.getRandomValueUsingList(singleEntryMap);
+
+        assertEquals(Integer.valueOf(42), result);
+    }
+
+    @Test
+    public void whenUsingOffsetWithSingleElement_thenReturnsThatElement() {
+        Map<String, Integer> singleEntryMap = new HashMap<>();
+        singleEntryMap.put("only", 42);
+
+        Integer result = randomNumberMap.getRandomValueUsingOffset(singleEntryMap);
+
+        assertEquals(Integer.valueOf(42), result);
+    }
+
+    @Test
+    public void whenUsingOffset_thenValueExistsInMap() {
+        Map<String, Integer> map = new HashMap<>();
+        map.put("apple", 1);
+        map.put("banana", 2);
+        map.put("cherry", 3);
+        map.put("date", 4);
+
+        Integer randomValue = randomNumberMap.getRandomValueUsingOffset(map);
+
+        assertNotNull(randomValue);
+        assertTrue(map.containsValue(randomValue));
+    }
+}
+
diff --git a/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomizedMapUnitTest.java b/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomizedMapUnitTest.java
new file mode 100644
index 000000000000..759177900e9c
--- /dev/null
+++ b/core-java-modules/core-java-collections-maps-9/src/test/java/com/baeldung/map/randommapkey/RandomizedMapUnitTest.java
@@ -0,0 +1,64 @@
+package com.baeldung.map.randommapkey;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Arrays;
+
+import org.junit.Test;
+
+public class RandomizedMapUnitTest {
+
+    @Test
+    public void whenGettingRandomValue_thenValueExistsInMap() {
+        RandomizedMap<String, Integer> map = new RandomizedMap<>();
+        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() {
+        RandomizedMap<String, Integer> map = new RandomizedMap<>();
+        map.put("apple", 1);
+        map.put("banana", 2);
+        map.put("cherry", 3);
+
+        map.remove("banana");
+
+        for (int i = 0; i < 20; i++) {
+            Integer randomValue = map.getRandomValue();
+            assertNotNull(randomValue);
+            assertFalse(randomValue.equals(2));
+        }
+    }
+
+    @Test
+    public void whenMapIsEmpty_thenReturnsNull() {
+        RandomizedMap<String, Integer> map = new RandomizedMap<>();
+
+        Integer randomValue = map.getRandomValue();
+
+        assertNull(randomValue);
+    }
+
+    @Test
+    public void whenClearingMap_thenRandomValueReturnsNull() {
+        RandomizedMap<String, Integer> map = new RandomizedMap<>();
+        map.put("apple", 1);
+        map.put("banana", 2);
+
+        map.clear();
+
+        Integer randomValue = map.getRandomValue();
+        assertNull(randomValue);
+    }
+}
+