a) Napiši funkciju def lin_hash(polje_kljuc, hash_table, n, m) koja realizira postupak linearnog isprobavanja.. Ulaz u funkciju su int polje ključeva, int polje hash tabele, , n – veličina hash tabele, m – djelitelj po modulu koji mora biti prost broj (m <= n) . Napomena: Funkcija treba izvršiti izračunavanje adrese za svaki ključ prema hash funkciji koja glasi

h (k) = (127*k + 5) % m i svaki puta ispitati da li je izračunata adresa u koliziji (provjeriti da li je u hash tabeli vrijednost na izračunatoj adresi jednaka 0). Ako nije u koliziji upisuje se vrijednost ključa u hash tabelu na izračunatu adresu (indeks polja), a ako je u koliziji ide se računati nova adresa za novu vrijednost indeksa i koja se povećala za 1. Za svako umetanje ključa ispisati broj kolizija, te na kraju ispisati ukupan broj kolizija.

Napomena: koristite pomoćnu varijablu kolizija koja je jednaka 0 ako nema kolizije ili 1 ako ima kolizije. Na kraju ispisati tabelu ključeva i hash tabelu. Napisati test program za zadanu tabelu ključeva: KEY =[17, 66, 58, 3, 66, 4, 88, 89, 1, 13, 25, 101, 102, 103], veličina hash tabele je n = 23. Odredite broj m (djelitelj po modulu u hash funkciji) takav da bude prvi manji broj od veličine tablice koji je prim broj).

b) Realizirajte funkciju def search_key(hash_table, n, m, key) koja će pronaći zadani ključ (key) u tablici i ispisati njegovu vrijednost i indeks tablice u kojoj se nalazi te ispisati koliko ispitivanja je napravljeno da se nađe traženi ključ (broj ispitivanja i= 0 do m-1). Ako ključ nije pronađen vratiti vrijednost -1 i ispisati da ključ nije pronađen.Voditi računa u implementaciji funkcije za pretraživanje da li je možda traženi ključ bio brisan (pogledajte zadatak c).

c) Realizirajte funkciju def delete_key(hash_table, n, m, delkey) gdje je delkey ključ koji želimo izbrisati. Napomena za brisanje ključa zbog rješavanja kolizija na toj poziciji u tablici ne smije se samo obrisati ključ nego se mora ostaviti flag (zastavica) da je tu bio neki podatak. Zato nakon brisanja ključa na to mjesto upisati broj -999999.

d) U drajver kodu testirati sve implementacije na sljedeći način.

1) Umetnuti zadani niz u hash tabelu i ispisati broj kolizija za svako umetanje ispisati broj kolizija i ukupan broj kolizija. Ispisati cijelu hash tabelu.

        2) Pronaći neki ključ i ispisati ga prema zadatku b). Ključ sami birate.

        3) Obrisati dva ključa (po izboru).

4) Pronaći neki ključ po izboru i jedan od obrisanih ključeva. Ispisati sve prema zadatku b).

5) Ispisati ponovno cijelu hash tabelu.

def lin_hash(polje_kljuc, hash_table, n, m):
    kolizija = 0
    for k in polje_kljuc: 
        kolizije_za_umetanje = 0
        slot = (127 * k + 5) % m 
        while (hash_table[slot] != 0):
            kolizije_za_umetanje = kolizije_za_umetanje + 1
            kolizija = kolizija + 1
            if (slot == n - 1):
                slot = 0
            else:
                slot = slot + 1
        hash_table[slot] = k
        print("Broj kolizija za umetanje kljuca ", k, ": ", kolizije_za_umetanje)
    return kolizija


def search_key(hash_table, n, m, key):
    k = (127*key+5) % m
    for i in range (n-k-1):
        k = (127*key+5) % m + i
        if (hash_table[k] == key):
            print("Vrijednost kljuca je :", hash_table[k])
            print("Broj ispitivanja da se nade trazeni kljuc je :", i)
            return k
    return -1

def delete_key(hash_table, n, m, bris):
    trazi = search_key(hash_table, n , m , bris)
    if (trazi != -1):
        hash_table[trazi] = -99999
        
def isProst(num):
    if num > 1:
        for i in range(2,num):
            if (num % i) == 0:
                return False
            else:
                return True
    else:
        return False   
    
KEY =[17, 66, 58, 3, 66, 4, 88, 89, 1, 13, 25, 101, 102, 103]
hash_table = [0]*23
n=23
m = None
for i in range(n-1, 0, -1):
    if isProst(i):
        m = i
        break
kolizije = lin_hash(KEY, hash_table, n, m)
print("Broj kolizija: ", kolizije)
print("\nTablica kljuceva ", KEY)
print("Hash tablica: ", hash_table)

rez = search_key(hash_table, n , m , 58)
if (rez != -1):
    print ("Indeks kljuca je : ", rez)
if (rez == -1):
    print ("Kljuc nije pronaden")


delete_key(hash_table, n , m , 58)

print ("Tablica nakon brisanja elementa je")
print (hash_table)
Broj kolizija za umetanje kljuca  17 :  0
Broj kolizija za umetanje kljuca  66 :  0
Broj kolizija za umetanje kljuca  58 :  0
Broj kolizija za umetanje kljuca  3 :  1
Broj kolizija za umetanje kljuca  66 :  2
Broj kolizija za umetanje kljuca  4 :  2
Broj kolizija za umetanje kljuca  88 :  3
Broj kolizija za umetanje kljuca  89 :  3
Broj kolizija za umetanje kljuca  1 :  0
Broj kolizija za umetanje kljuca  13 :  0
Broj kolizija za umetanje kljuca  25 :  5
Broj kolizija za umetanje kljuca  101 :  1
Broj kolizija za umetanje kljuca  102 :  1
Broj kolizija za umetanje kljuca  103 :  1
Broj kolizija:  19

Tablica kljuceva  [17, 66, 58, 3, 66, 4, 88, 89, 1, 13, 25, 101, 102, 103]
Hash tablica:  [58, 17, 101, 102, 103, 0, 1, 0, 66, 3, 66, 4, 88, 89, 25, 0, 0, 0, 13, 0, 0, 0, 0]
Vrijednost kljuca je : 58
Broj ispitivanja da se nade trazeni kljuc je : 0
Indeks kljuca je :  0
Vrijednost kljuca je : 58
Broj ispitivanja da se nade trazeni kljuc je : 0
Tablica nakon brisanja elementa je
[-99999, 17, 101, 102, 103, 0, 1, 0, 66, 3, 66, 4, 88, 89, 25, 0, 0, 0, 13, 0, 0, 0, 0]