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.