12. ADT skup realizovan otvorenim hešovanjem

- Hesh tabela je niz u kome se pozicija nekog elementa odredjuje na osnovu samog elementa. Funkcija koja
izracunava poziciju elementa naziva se hesh funkcija. Hesh funkcija treba da bude brzo i lako izracunljiva.
-Hesh tabelama mogu se realizovati dve bitne apstraktne strukture podataka: skupovi i mape. Hesh tabele
omogucavaju znatno brze pretrazivanje - proveru da li je element u skupu/mapi.
- ADT skup je kolekcija objekata koja ne sadrzi duplikate.
- Operacije sa skupovima:

1. Dodavanje novog elementa u skup.
2. Brisanje elementa iz skupa.
3. Pretrazivanje - provera da li je element u skupu.
4. Operacije unije, preseka, razlike.

- U praksi se koriste samo prve tri operacije:
 - Dodavanje elementa zahteva pretrazivanje, apstraktne
 - Brisanje elementa ukljucuje pretrazivanje.

- ADT skup moze biti reprezentovan prostim nizom, povezanom listom, hesh tabelom.

- Specifikacija ADT-a je apstraktni deo ADT-a, razlicite realazacije ADT-a dele istu specifikaciju ADT-a.


public interface Set<T> {

	boolean insert(T element)   // Dodaje element u skup, vraca false ako element vec postoji u skupu.
	boolean remove(T element)   // Brise element, vraca false ako element ne postoji u skupu
	boolean member(T element)   // provera da li je element u skupu
}

- Hesh funkcija mora biti konzistentna k1 = k2  -> hash(k1) = hash(k2);
- Svaka java klasa implicitno nasledjuje klasu Object.
- Klasa Object definise metod:  int hashCode();

- Ako je velicina hesh tabele M, tada hesh funkcija treba da vrati broj koji je u opsegu[0..M-1];
- Redefinisuci metod hashCode() u nasoj klasi dobijamo hash kod za objekte nase klase.
- 	hash(k1) = hash(k2) -> ovakva situacija smatra se kolizijom.
- Mehanizmi za razresenje kolizija :

1. Otvoreno hesovanje: - hesh tabela je niz jednostruko povezanih listi
					   - liste sadrze objekte sa istom vrednoscu hesh funkcije
					   - ove liste jos zovemo lancima kolizija.
2. Zatvoreno hesovanje: - Hesh tabela je niz, pozicija objekta o u nizu je hash(o)
						- Ukoliko je pozicija zauzeta tada se odredjuje nova pozicija po nekoj strategiji
						- Linearno probavanje: hash(o)+1,hash(o)+2
						- Kvadratno probavanje: hash(o) + 1, hash(o) + 4, hash(o) + 9

- Velicina hesh tabele bira se da bude neki prost broj.

public class OHashSet<T> impelements Set<T> {

	private static final int DEFAULT_TABLE_SIZE = 101;

	private static class Node {   <- Cvor u listi objekata sa istom hash vrednoscu

		Object value;
		Node next;

		public Node(Object value){
			this.value = value;
		}
	}

	private Node[] table;

	public OHashSet(){
		this(DEFAULT_TABLE_SIZE)
	}
	public OHashSet(int size){
		if(size<=0){
			throw new IllegalArgumentException("Velicina hash tabele ne moze biti negativna");
		}
		table new = Node[size];
	}

	private int hash(T o){

		if( o == null){
			throw new IllegalArgumentException("Hash funkcija se ne moze racunati za null objekat");
		}
		return Math.abs(o.hashCode() % table.length;


	}

	private Node[] searchCollisionChain(T element, int hashValue){

		Node current = table[hashValue];
		Node prev = null;

		while(current != null){
			if(current.value.equals(element)){
				Node[] ret = new Node[2];
				ret[0] = current;
				ret[1] = prev;

				return ret;
			}
			prev = current;
			current = current.next;
		}
		return null;

	}

	public boolean member(T element){

		return searchCollisionChain(element,hash(element)) != null;
	}

	public boolean insert(T element) {

		int hashValue = hash(element);
		Node[] n = searchCollisionChain(element,hashValue);
		if( n != null)
			return false;

		Node newElement = new Node(element);
		newElement.next = table[hashValue];
		table[hashValue] = newElement;


		return true;
	}

 REMOVE - 1. Proveri da li element postoji u odgovarajucem lancu kolizija.
		  2. Ako postoji razlikujemo dva slucaja: element koji se brise je na
		  pocetku(1) lanca kolizija ili (2) u sredini/na kraju lanca kolizija.


	public boolean remove(T element){

		int hashValue = hash(element);
		Node[] n = searchCollisionChain(element,hashValue);

		if(n == null){
			return false;
		}
		if(n[0] == table[hashValue){
			table[hashValue] = table[hashValue].next;
		}else{
			n[1].next = n[0].next;
		}
		return true;

	}

13. ADT skup realizovan zatvorenim hešovanjem, operacija insert


- Svaka celija u hesh tabeli ce imati jedno od sledeca tri stanja:

 1. Empty - prazna, slobodna celija.
 2. OCCUPIED - zauzeta celija, celija koja sadrzi element.
 3. DELETED - celija koja je nekada sadrzala element koji je u medjuvremenu obrisan.

- Dodavanje novog elementa n

	- hash = vrednost hesh funkcije za n
	- Ako je table[hash] u stanju Empty tada table[hash] = n, table[hash] prelazi u stanje
	OCCUPIED, inace trazi neko drugo mesto za n.
	- Trazenje nekog drugo mesta za element se jos zove probavanje(probing)

	- Linearno probavanje (hash+i) % M, i=1,2... uzrokuje klastere u hesh tabeli sto
	  usporava pretrazivanje.
	- Kvadratno probavanje (hash+i^2) % M, i=1,2...

- Operacije:

1. Pretrazivanje hesh tabele, pretrazivanje lanca kolizija za dati element
2. Dodavanje novog elementa u hash tabelu, dodavanje na kraj lanca kolizija ili
dodavanje u prvu celiju u statusu DELETED u lancu kolizija.
3. Brisanje elemenata iz hesh tabele, lenjo brisanje - celija tabele koja je
sadrzala element promeni status u DELETED.

- Maksimalna duzina lanca kolizija kod kvadratnog probavanja je (M-1)/2
- Dodavanje novog elementa pri maksimalnoj duzini lanca kolizija u koje su svi
elementi u statusu OCCUPIED je neizvodljivo. Tada prosirujemo tabelu.

- Prosirenje tabele takodje radimo kada je opterecenje hesh tabele vece od 70%.

- Prosirivanje tabele : velicina tabele -> najmanji prost broj koji je barem dva puta veci
nego sto je trenutno velicina tabele.

1. Napravimo kopiju stare tabele i statusa.
2. Realociramo tabelu i postavimo statuse svih celija ne Empty
3. Iteriramo kroz staru tabelu i celije u statusu OCCUPIED dodajemo u novu tabelu.
4. Staru tabelu i statuse postavimo na null vrednosti.


public class CHashSet<T> impelements Set<T> {

	private static final int DEFAULT_TABLE_SIZE = 101;

	private enum Status{
		EMPTY;
		OCCUPIED;
		DELETED;
	}

	private Object[] table;  // tabela
	prvate Status[] status;  // statusi celija
	private int numElements; // broj elemenata(OCCUPIED celija) u tabeli

	public CHashSet(){
		this.(DEFAULT_TABLE_SIZE);
	}
	public CHashSet(int size){
		if(size <=0){
			throw new IllegalArgumentException(
			 "Velicina hash tabele ne moze biti negativna"
			);
		}
		reset(size)
	}

	private void reset(int size){
		table = new Object[size];
		status = new Status[size];
		for(int i=0; i<status.length;i++){
			status[i] = Status.EMPTY;
		}
		numElements = 0;
	}
	private int hash(T o){
		if (o == null)
				throw new IllegalArgumentException(
					"Hash funkcija se ne moze racunati za null objekat"
				);
		return Math.abs(o.hashCode()% table.length);
	}

	public boolean insert(T element){

		int hashValue = hash(element);

		int maxChainLength = (table.length-1)/2;
		int i=0;
		boolean endOfChain = false;
		int firsAvailablePosition = -1;

		while( !endOfChain && i<= maxChainLength){
			int currentPosition = (hashValue + i*i) % table.length;

			if(status[currentPosition) == Status.OCCUPIED){
				if(table[currentPosition].equals(element)){
					return false;
				}
			}else{
					if(firsAvailablePosition == -1){
						firsAvailablePosition = currentPosition;
					}
					if (status[currentPosition] == Status.EMPTY) {
						endOfChain = true;
					}
			}
		i++
		}
		if(firsAvailablePosition == -1 || loadFactor() > 0.7) {
			expand();
			hashValue = hash(element);
			add(element);
		}else{
			status[firsAvailablePosition] = Status.OCCUPIED;
			table[firsAvailablePosition] = element;
			numElements++;
		}
		return true;
	}
	public void add(T element, int hashValue) {
		boolean foundPosition = false;
		int i=0;

		while(!foundPosition){
			int currentPosition = (hashValue + i*i) % table.length;

			if(status[currentPosition] != Status.OCCUPIED){
				status[currentPosition] = Status.OCCUPIED;
				table[currentPosition] = element;
				numElements++;
				foundPosition = true;
			}else{
				i++;
			}
		}
	}


}

14. ADT skup realizovan zatvorenim hesovanjem, operacija member i remove

- Svaka celija u hesh tabeli ce imati jedno od sledeca tri stanja:

 1. Empty - prazna, slobodna celija.
 2. OCCUPIED - zauzeta celija, celija koja sadrzi element.
 3. DELETED - celija koja je nekada sadrzala element koji je u medjuvremenu obrisan.

- Dodavanje novog elementa n

	- hash = vrednost hesh funkcije za n
	- Ako je table[hash] u stanju Empty tada table[hash] = n, table[hash] prelazi u stanje
	OCCUPIED, inace trazi neko drugo mesto za n.
	- Trazenje nekog drugo mesta za element se jos zove probavanje(probing)

	- Linearno probavanje (hash+i) % M, i=1,2... uzrokuje klastere u hesh tabeli sto
	  usporava pretrazivanje.
	- Kvadratno probavanje (hash+i^2) % M, i=1,2...

- Operacije:

1. Pretrazivanje hesh tabele, pretrazivanje lanca kolizija za dati element
2. Dodavanje novog elementa u hash tabelu, dodavanje na kraj lanca kolizija ili
dodavanje u prvu celiju u statusu DELETED u lancu kolizija.
3. Brisanje elemenata iz hesh tabele, lenjo brisanje - celija tabele koja je
sadrzala element promeni status u DELETED.

- Maksimalna duzina lanca kolizija kod kvadratnog probavanja je (M-1)/2
- Dodavanje novog elementa pri maksimalnoj duzini lanca kolizija u koje su svi
elementi u statusu OCCUPIED je neizvodljivo. Tada prosirujemo tabelu.

- Prosirenje tabele takodje radimo kada je opterecenje hesh tabele vece od 70%.

- Prosirivanje tabele : velicina tabele -> najmanji prost broj koji je barem dva puta veci
nego sto je trenutno velicina tabele.

1. Napravimo kopiju stare tabele i statusa.
2. Realociramo tabelu i postavimo statuse svih celija ne Empty
3. Iteriramo kroz staru tabelu i celije u statusu OCCUPIED dodajemo u novu tabelu.
4. Staru tabelu i statuse postavimo na null vrednosti.


public class CHashSet<T> impelements Set<T> {

	private static final int DEFAULT_TABLE_SIZE = 101;

	private enum Status{
		EMPTY;
		OCCUPIED;
		DELETED;
	}

	private Object[] table;  // tabela
	prvate Status[] status;  // statusi celija
	private int numElements; // broj elemenata(OCCUPIED celija) u tabeli

	public CHashSet(){
		this.(DEFAULT_TABLE_SIZE);
	}
	public CHashSet(int size){
		if(size <=0){
			throw new IllegalArgumentException(
			 "Velicina hash tabele ne moze biti negativna"
			);
		}
		reset(size)
	}

	private void reset(int size){
		table = new Object[size];
		status = new Status[size];
		for(int i=0; i<status.length;i++){
			status[i] = Status.EMPTY;
		}
		numElements = 0;
	}
	private int hash(T o){
		if (o == null)
				throw new IllegalArgumentException(
					"Hash funkcija se ne moze racunati za null objekat"
				);
		return Math.abs(o.hashCode()% table.length);
	}



	private int searchCollisionChain(T element, int hashValue){
		int currentPosition = hashValue;
		int i=0;
		int maxChainLength = (table.length-1)/2;

		while(i <= maxChainLength && status[currentPosition] != Status.EMPTY){
			if(status[currentPosition] == Status.OCCUPIED && table[currentPosition].equals(element)){
				return currentPosition;
			}
			i++;
			currentPosition = (hashValue + i * i) % table.length;
		}
		return -1;
	}

	public boolean member(T element){

		return searchCollisionChain(element,hash(element)) >=0;
	}

	public boolean remove (T element){

		int pos = searchCollisionChain(element,hash(element));
		if(pos<0)
			return false;
		status[pos] = Status.DELETED;
		numElements--;

		return true;
	}