import random

class HashMap(object):
    """
    Klasa modeluje heš mapu
    """
    def __init__(self, capacity=8):
        """
        Konstruktor

        Argumenti:
        - `capacity`: inicijalni broj mesta u lookup nizu
        - `prime`: prost broj neophodan heš funkciji
        """
        self._data = capacity * [None]
        self._capacity = capacity
        self._size = 0
        self._prime = 109345121

        # konstante heširanja
        self._a = 1 + random.randrange(self._prime-1)
        self._b = random.randrange(self._prime)

    def _hash(self, x):
        """
        Heš funkcija

        Izračunavanje heš koda vrši se po formuli (ax + b) mod p.

        Argument:
        - `x`: vrednost čiji se kod računa
        """
        hashed_value = (hash(x)*self._a + self._b) % self._prime
        compressed = hashed_value % self._capacity
        return compressed

    def __setitem__(self, key, value):
        compressed_key = self._hash(key)
        found = False
        if self._data[compressed_key] is None:
            self._data[compressed_key] = []
            self._data[compressed_key].append([key, value])
        else:
            for current_element in self._data[compressed_key]:
                if current_element[0] == key:
                    current_element[1] = value
                    found = True
                    break
            if not found:
                self._data[compressed_key].append([key, value])

    def __getitem__(self, item):
        compressed_key = self._hash(item)
        if self._data[compressed_key] is None:
            raise Exception("Ne postoji ovaj key")
        for element in self._data[compressed_key]:
            if element[0] == item:
                return element[1]

    def __delitem__(self, key):
        compresed_key = self._hash(key)



mapa = HashMap()
mapa[2] = 122
mapa[2] = 566
mapa[22] = 5541

print(mapa[2])