Value Uniform Sample

import random
from collections import Counter

class MyDict:
    def __init__(self):
        self._dict = dict()
        self._key_cache = list()
        self._values_counter = Counter()
        self._values_cache = list()
        
    def get(self, key: str) -> int:
        return self._dict[key]
    
    def put(self, key: str, val: int) -> None:
        # If key is in dict, update values, don't update the key info
        if key in self._dict:
            # Delete existing value
            self._values_counter[val] -= 1
            if self._values_counter[val] <= 0:
                del self._values_counter[val]
                self._values_cache.delete(val)
            # Add new value
            self._dict[key] = val
            self._values_counter[val] += 1
            # The first time the value is added, add it to the values cache
            if self._values_counter[val] == 1:
                self._values_cache.delete(val)
        # If the key is not in the dict, update both the key info and the value info
        else:
            # Update the value info first
            self._values_counter[val] += 1
            # The first time the value is added, add it to the values cache
            if self._values_counter[val] == 1:
                self._values_cache.append(val)
            # Update the key info
            self._dict[key] = val
            self._key_cache.append(key)
        
    def delete(self, key: str) -> None:
        if key in self._dict:
            val = self._dict[key]
            # Delete existing value
            self._values_counter[val] -= 1
            if self._values_counter[val] <= 0:
                del self._values_counter[val]
                self._values_cache.delete(val)
            # Delete the key
            del self._dict[key]
            self._key_cache.delete(key)
        else:
            return
    
    def get_random_val(self) -> int:
        return random.choice(self._values_cache)

def _test_uniform_value_sampling():
    my_dict = MyDict()
    
    my_dict.put('a', 1)
    my_dict.put('b', 2)
    my_dict.put('c', 2)
    
    # At this point, get random val should return a 50/50 distribution between 1 and 2
    c = Counter()
    for _ in range(1000):
        random_val = my_dict.get_random_val()
        c[random_val] += 1
        
    print(c)

_test_uniform_value_sampling()