Od kojih komponenti se sastoji hash tabela?

Hash tabela se sastoji od dva glavna komponenta:

1. Niz (ili lista) ćelija (kace): Ovo je glavna struktura za skladištenje. Svaka ćelija može sadržavati jedan ili više elemenata podataka (parova ključ-vrednost).

2. Hash funkcija: Algoritam koji pretvara ulazni ključ u numerički indeks, koji se koristi za određivanje ćelije gde treba sačuvati ili pronaći odgovarajući element podataka.

Pored toga, za rešavanje kolizija (situacija kada različiti ključevi hash-iraju u isti indeks), koriste se mehanizmi poput:

• Metod lančanica: U svakoj ćeliji se čuva lista (npr. povezani spisak) elemenata koji su hash-irani u taj indeks.
• Metod otvorenog adresiranja: U slučaju kolizije, algoritam traži sledeću slobodnu ćeliju prateći određenu strategiju (linearnu sondiranje, kvadratno sondiranje, dvostruko hashiranje).

# Primer jednostavne hash funkcije
def simple_hash(ključ, veličina_niza):
    # Pretvaranje ključa u broj
    if isinstance(ključ, str):
        vrednost_hash = sum(ord(karakter) for karakter in ključ)
    elif isinstance(ključ, int):
        vrednost_hash = ključ
    else:
        raise TypeError("Nepodržan tip ključa")

    # Vraćanje indeksa unutar veličine niza
    return vrednost_hash % veličina_niza

# Primer komponente niza ćelija za metod lančanica
class HashTable:
    def __init__(self, veličina):
        self.veličina = veličina
        self.array = [[] for _ in range(self.veličina)] # Niz listi (lančanici)

    def ubaci(self, ključ, vrednost):
        indeks = simple_hash(ključ, self.veličina)
        self.array[indeks].append((ključ, vrednost)) # Dodavanje para ključ-vrednost u listu

    def pretraži(self, ključ):
        indeks = simple_hash(ključ, self.veličina)
        for k, v in self.array[indeks]:
            if k == ključ:
                return v
        return None # Ključ nije pronađen