random_map.py

#!/usr/bin/env python3

import random

from typing import Any, Tuple


class RandomHashMap(object):

    __slots__ = [
        'key_val_mapping',
        'underlying_map',
        'underlying_arr',
        'size',
    ]

    def __init__(self):
        self.key_val_mapping = {}
        self.underlying_map = {}
        self.underlying_arr = []
        self.size = 0

    def insert(self, key: Any, value: Any) -> None:
        if key in self.key_val_mapping:
            return

        if len(self.underlying_arr) == self.size:
            self.underlying_arr.append(key)
        else:
            self.underlying_arr[self.size] = key

        self.underlying_map[key] = self.size
        self.key_val_mapping[key] = value

        self.size += 1

    def lookup(self, key: Any) -> Any:
        return self.key_val_mapping[key]

    def delete(self, key: Any) -> Any:
        index = self.underlying_map[key]

        temp = self.underlying_arr[self.size - 1]
        self.underlying_arr[self.size - 1] = self.underlying_arr[index]
        self.underlying_arr[index] = temp

        self.underlying_map[key] = index

        del self.key_val_mapping[key]
        del self.self.underlying_map[key]

        self.size -= 1

    def random(self) -> Tuple[Any, Any]:
        key = random.choice(self.underlying_arr[:self.size])
        return (key, self.key_val_mapping[key])

    def __repr__(self) -> str:
        return repr((
            list(enumerate(self.underlying_arr[:self.size])),
            self.key_val_mapping
        ))