SHARE
TWEET

Untitled

a guest Sep 13th, 2017 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. 12. ADT skup realizovan otvorenim hešovanjem
  2.  
  3. - Hesh tabela je niz u kome se pozicija nekog elementa odredjuje na osnovu samog elementa. Funkcija koja
  4. izracunava poziciju elementa naziva se hesh funkcija. Hesh funkcija treba da bude brzo i lako izracunljiva.
  5. -Hesh tabelama mogu se realizovati dve bitne apstraktne strukture podataka: skupovi i mape. Hesh tabele
  6. omogucavaju znatno brze pretrazivanje - proveru da li je element u skupu/mapi.
  7. - ADT skup je kolekcija objekata koja ne sadrzi duplikate.
  8. - Operacije sa skupovima:
  9.  
  10. 1. Dodavanje novog elementa u skup.
  11. 2. Brisanje elementa iz skupa.
  12. 3. Pretrazivanje - provera da li je element u skupu.
  13. 4. Operacije unije, preseka, razlike.  
  14.  
  15. - U praksi se koriste samo prve tri operacije:
  16.  - Dodavanje elementa zahteva pretrazivanje, apstraktne
  17.  - Brisanje elementa ukljucuje pretrazivanje.
  18.  
  19. - ADT skup moze biti reprezentovan prostim nizom, povezanom listom, hesh tabelom.
  20.  
  21. - Specifikacija ADT-a je apstraktni deo ADT-a, razlicite realazacije ADT-a dele istu specifikaciju ADT-a.
  22.  
  23.  
  24. public interface Set<T> {
  25.  
  26.     boolean insert(T element)   // Dodaje element u skup, vraca false ako element vec postoji u skupu.
  27.     boolean remove(T element)   // Brise element, vraca false ako element ne postoji u skupu
  28.     boolean member(T element)   // provera da li je element u skupu
  29. }
  30.  
  31. - Hesh funkcija mora biti konzistentna k1 = k2  -> hash(k1) = hash(k2);
  32. - Svaka java klasa implicitno nasledjuje klasu Object.
  33. - Klasa Object definise metod:  int hashCode();
  34.  
  35. - Ako je velicina hesh tabele M, tada hesh funkcija treba da vrati broj koji je u opsegu[0..M-1];
  36. - Redefinisuci metod hashCode() u nasoj klasi dobijamo hash kod za objekte nase klase.
  37. -   hash(k1) = hash(k2) -> ovakva situacija smatra se kolizijom.
  38. - Mehanizmi za razresenje kolizija :
  39.  
  40. 1. Otvoreno hesovanje: - hesh tabela je niz jednostruko povezanih listi
  41.                        - liste sadrze objekte sa istom vrednoscu hesh funkcije
  42.                        - ove liste jos zovemo lancima kolizija.
  43. 2. Zatvoreno hesovanje: - Hesh tabela je niz, pozicija objekta o u nizu je hash(o)
  44.                         - Ukoliko je pozicija zauzeta tada se odredjuje nova pozicija po nekoj strategiji
  45.                         - Linearno probavanje: hash(o)+1,hash(o)+2
  46.                         - Kvadratno probavanje: hash(o) + 1, hash(o) + 4, hash(o) + 9
  47.                        
  48. - Velicina hesh tabele bira se da bude neki prost broj.
  49.  
  50. public class OHashSet<T> impelements Set<T> {
  51.  
  52.     private static final int DEFAULT_TABLE_SIZE = 101;
  53.    
  54.     private static class Node {   <- Cvor u listi objekata sa istom hash vrednoscu
  55.        
  56.         Object value;
  57.         Node next;
  58.        
  59.         public Node(Object value){
  60.             this.value = value;
  61.         }
  62.     }
  63.    
  64.     private Node[] table;
  65.    
  66.     public OHashSet(){
  67.         this(DEFAULT_TABLE_SIZE)
  68.     }
  69.     public OHashSet(int size){
  70.         if(size<=0){
  71.             throw new IllegalArgumentException("Velicina hash tabele ne moze biti negativna");
  72.         }
  73.         table new = Node[size];
  74.     }
  75.    
  76.     private int hash(T o){
  77.    
  78.         if( o == null){
  79.             throw new IllegalArgumentException("Hash funkcija se ne moze racunati za null objekat");
  80.         }
  81.         return Math.abs(o.hashCode() % table.length;
  82.        
  83.    
  84.     }
  85.    
  86.     private Node[] searchCollisionChain(T element, int hashValue){
  87.        
  88.         Node current = table[hashValue];
  89.         Node prev = null;
  90.        
  91.         while(current != null){
  92.             if(current.value.equals(element)){
  93.                 Node[] ret = new Node[2];
  94.                 ret[0] = current;
  95.                 ret[1] = prev;
  96.                
  97.                 return ret;
  98.             }
  99.             prev = current;
  100.             current = current.next;
  101.         }
  102.         return null;
  103.        
  104.     }
  105.  
  106.     public boolean member(T element){
  107.    
  108.         return searchCollisionChain(element,hash(element)) != null;
  109.     }
  110.    
  111.     public boolean insert(T element) {
  112.    
  113.         int hashValue = hash(element);
  114.         Node[] n = searchCollisionChain(element,hashValue);
  115.         if( n != null)
  116.             return false;
  117.            
  118.         Node newElement = new Node(element);
  119.         newElement.next = table[hashValue];
  120.         table[hashValue] = newElement;
  121.        
  122.        
  123.         return true;
  124.     }
  125.  
  126.  REMOVE - 1. Proveri da li element postoji u odgovarajucem lancu kolizija.
  127.           2. Ako postoji razlikujemo dva slucaja: element koji se brise je na
  128.           pocetku(1) lanca kolizija ili (2) u sredini/na kraju lanca kolizija.
  129.  
  130.  
  131.     public boolean remove(T element){
  132.        
  133.         int hashValue = hash(element);
  134.         Node[] n = searchCollisionChain(element,hashValue);
  135.        
  136.         if(n == null){
  137.             return false;
  138.         }
  139.         if(n[0] == table[hashValue){
  140.             table[hashValue] = table[hashValue].next;
  141.         }else{
  142.             n[1].next = n[0].next;
  143.         }
  144.         return true;
  145.        
  146.     }
  147.  
  148. 13. ADT skup realizovan zatvorenim hešovanjem, operacija insert
  149.  
  150.  
  151. - Svaka celija u hesh tabeli ce imati jedno od sledeca tri stanja:
  152.  
  153.  1. Empty - prazna, slobodna celija.
  154.  2. OCCUPIED - zauzeta celija, celija koja sadrzi element.
  155.  3. DELETED - celija koja je nekada sadrzala element koji je u medjuvremenu obrisan.
  156.  
  157. - Dodavanje novog elementa n
  158.  
  159.     - hash = vrednost hesh funkcije za n
  160.     - Ako je table[hash] u stanju Empty tada table[hash] = n, table[hash] prelazi u stanje
  161.     OCCUPIED, inace trazi neko drugo mesto za n.
  162.     - Trazenje nekog drugo mesta za element se jos zove probavanje(probing)
  163.  
  164.     - Linearno probavanje (hash+i) % M, i=1,2... uzrokuje klastere u hesh tabeli sto
  165.       usporava pretrazivanje.
  166.     - Kvadratno probavanje (hash+i^2) % M, i=1,2...
  167.    
  168. - Operacije:
  169.  
  170. 1. Pretrazivanje hesh tabele, pretrazivanje lanca kolizija za dati element
  171. 2. Dodavanje novog elementa u hash tabelu, dodavanje na kraj lanca kolizija ili
  172. dodavanje u prvu celiju u statusu DELETED u lancu kolizija.
  173. 3. Brisanje elemenata iz hesh tabele, lenjo brisanje - celija tabele koja je
  174. sadrzala element promeni status u DELETED.
  175.  
  176. - Maksimalna duzina lanca kolizija kod kvadratnog probavanja je (M-1)/2
  177. - Dodavanje novog elementa pri maksimalnoj duzini lanca kolizija u koje su svi
  178. elementi u statusu OCCUPIED je neizvodljivo. Tada prosirujemo tabelu.
  179.  
  180. - Prosirenje tabele takodje radimo kada je opterecenje hesh tabele vece od 70%.
  181.  
  182. - Prosirivanje tabele : velicina tabele -> najmanji prost broj koji je barem dva puta veci
  183. nego sto je trenutno velicina tabele.
  184.  
  185. 1. Napravimo kopiju stare tabele i statusa.
  186. 2. Realociramo tabelu i postavimo statuse svih celija ne Empty
  187. 3. Iteriramo kroz staru tabelu i celije u statusu OCCUPIED dodajemo u novu tabelu.
  188. 4. Staru tabelu i statuse postavimo na null vrednosti.
  189.  
  190.  
  191. public class CHashSet<T> impelements Set<T> {
  192.    
  193.     private static final int DEFAULT_TABLE_SIZE = 101;
  194.    
  195.     private enum Status{
  196.         EMPTY;
  197.         OCCUPIED;
  198.         DELETED;
  199.     }
  200.    
  201.     private Object[] table;  // tabela
  202.     prvate Status[] status;  // statusi celija
  203.     private int numElements; // broj elemenata(OCCUPIED celija) u tabeli
  204.    
  205.     public CHashSet(){
  206.         this.(DEFAULT_TABLE_SIZE);
  207.     }
  208.     public CHashSet(int size){
  209.         if(size <=0){
  210.             throw new IllegalArgumentException(
  211.              "Velicina hash tabele ne moze biti negativna"
  212.             );
  213.         }
  214.         reset(size)
  215.     }
  216.    
  217.     private void reset(int size){
  218.         table = new Object[size];
  219.         status = new Status[size];
  220.         for(int i=0; i<status.length;i++){
  221.             status[i] = Status.EMPTY;
  222.         }
  223.         numElements = 0;
  224.     }
  225.     private int hash(T o){
  226.         if (o == null)
  227.                 throw new IllegalArgumentException(
  228.                     "Hash funkcija se ne moze racunati za null objekat"
  229.                 );
  230.         return Math.abs(o.hashCode()% table.length);
  231.     }
  232.    
  233.     public boolean insert(T element){
  234.    
  235.         int hashValue = hash(element);
  236.        
  237.         int maxChainLength = (table.length-1)/2;
  238.         int i=0;
  239.         boolean endOfChain = false;
  240.         int firsAvailablePosition = -1;
  241.        
  242.         while( !endOfChain && i<= maxChainLength){
  243.             int currentPosition = (hashValue + i*i) % table.length;
  244.            
  245.             if(status[currentPosition) == Status.OCCUPIED){
  246.                 if(table[currentPosition].equals(element)){
  247.                     return false;
  248.                 }
  249.             }else{
  250.                     if(firsAvailablePosition == -1){
  251.                         firsAvailablePosition = currentPosition;
  252.                     }
  253.                     if (status[currentPosition] == Status.EMPTY) {
  254.                         endOfChain = true;
  255.                     }
  256.             }
  257.         i++
  258.         }
  259.         if(firsAvailablePosition == -1 || loadFactor() > 0.7) {
  260.             expand();
  261.             hashValue = hash(element);
  262.             add(element);
  263.         }else{
  264.             status[firsAvailablePosition] = Status.OCCUPIED;
  265.             table[firsAvailablePosition] = element;
  266.             numElements++;
  267.         }
  268.         return true;
  269.     }
  270.     public void add(T element, int hashValue) {
  271.         boolean foundPosition = false;
  272.         int i=0;
  273.        
  274.         while(!foundPosition){
  275.             int currentPosition = (hashValue + i*i) % table.length;
  276.            
  277.             if(status[currentPosition] != Status.OCCUPIED){
  278.                 status[currentPosition] = Status.OCCUPIED;
  279.                 table[currentPosition] = element;
  280.                 numElements++;
  281.                 foundPosition = true;
  282.             }else{
  283.                 i++;
  284.             }
  285.         }
  286.     }
  287.        
  288.    
  289. }
  290.  
  291. 14. ADT skup realizovan zatvorenim hesovanjem, operacija member i remove
  292.  
  293. - Svaka celija u hesh tabeli ce imati jedno od sledeca tri stanja:
  294.  
  295.  1. Empty - prazna, slobodna celija.
  296.  2. OCCUPIED - zauzeta celija, celija koja sadrzi element.
  297.  3. DELETED - celija koja je nekada sadrzala element koji je u medjuvremenu obrisan.
  298.  
  299. - Dodavanje novog elementa n
  300.  
  301.     - hash = vrednost hesh funkcije za n
  302.     - Ako je table[hash] u stanju Empty tada table[hash] = n, table[hash] prelazi u stanje
  303.     OCCUPIED, inace trazi neko drugo mesto za n.
  304.     - Trazenje nekog drugo mesta za element se jos zove probavanje(probing)
  305.  
  306.     - Linearno probavanje (hash+i) % M, i=1,2... uzrokuje klastere u hesh tabeli sto
  307.       usporava pretrazivanje.
  308.     - Kvadratno probavanje (hash+i^2) % M, i=1,2...
  309.    
  310. - Operacije:
  311.  
  312. 1. Pretrazivanje hesh tabele, pretrazivanje lanca kolizija za dati element
  313. 2. Dodavanje novog elementa u hash tabelu, dodavanje na kraj lanca kolizija ili
  314. dodavanje u prvu celiju u statusu DELETED u lancu kolizija.
  315. 3. Brisanje elemenata iz hesh tabele, lenjo brisanje - celija tabele koja je
  316. sadrzala element promeni status u DELETED.
  317.  
  318. - Maksimalna duzina lanca kolizija kod kvadratnog probavanja je (M-1)/2
  319. - Dodavanje novog elementa pri maksimalnoj duzini lanca kolizija u koje su svi
  320. elementi u statusu OCCUPIED je neizvodljivo. Tada prosirujemo tabelu.
  321.  
  322. - Prosirenje tabele takodje radimo kada je opterecenje hesh tabele vece od 70%.
  323.  
  324. - Prosirivanje tabele : velicina tabele -> najmanji prost broj koji je barem dva puta veci
  325. nego sto je trenutno velicina tabele.
  326.  
  327. 1. Napravimo kopiju stare tabele i statusa.
  328. 2. Realociramo tabelu i postavimo statuse svih celija ne Empty
  329. 3. Iteriramo kroz staru tabelu i celije u statusu OCCUPIED dodajemo u novu tabelu.
  330. 4. Staru tabelu i statuse postavimo na null vrednosti.
  331.  
  332.  
  333. public class CHashSet<T> impelements Set<T> {
  334.    
  335.     private static final int DEFAULT_TABLE_SIZE = 101;
  336.    
  337.     private enum Status{
  338.         EMPTY;
  339.         OCCUPIED;
  340.         DELETED;
  341.     }
  342.    
  343.     private Object[] table;  // tabela
  344.     prvate Status[] status;  // statusi celija
  345.     private int numElements; // broj elemenata(OCCUPIED celija) u tabeli
  346.    
  347.     public CHashSet(){
  348.         this.(DEFAULT_TABLE_SIZE);
  349.     }
  350.     public CHashSet(int size){
  351.         if(size <=0){
  352.             throw new IllegalArgumentException(
  353.              "Velicina hash tabele ne moze biti negativna"
  354.             );
  355.         }
  356.         reset(size)
  357.     }
  358.    
  359.     private void reset(int size){
  360.         table = new Object[size];
  361.         status = new Status[size];
  362.         for(int i=0; i<status.length;i++){
  363.             status[i] = Status.EMPTY;
  364.         }
  365.         numElements = 0;
  366.     }
  367.     private int hash(T o){
  368.         if (o == null)
  369.                 throw new IllegalArgumentException(
  370.                     "Hash funkcija se ne moze racunati za null objekat"
  371.                 );
  372.         return Math.abs(o.hashCode()% table.length);
  373.     }
  374.  
  375.  
  376.  
  377.     private int searchCollisionChain(T element, int hashValue){
  378.         int currentPosition = hashValue;
  379.         int i=0;
  380.         int maxChainLength = (table.length-1)/2;
  381.        
  382.         while(i <= maxChainLength && status[currentPosition] != Status.EMPTY){
  383.             if(status[currentPosition] == Status.OCCUPIED && table[currentPosition].equals(element)){
  384.                 return currentPosition;
  385.             }
  386.             i++;
  387.             currentPosition = (hashValue + i * i) % table.length;
  388.         }
  389.         return -1;
  390.     }
  391.    
  392.     public boolean member(T element){
  393.        
  394.         return searchCollisionChain(element,hash(element)) >=0;
  395.     }
  396.    
  397.     public boolean remove (T element){
  398.        
  399.         int pos = searchCollisionChain(element,hash(element));
  400.         if(pos<0)
  401.             return false;
  402.         status[pos] = Status.DELETED;
  403.         numElements--;
  404.        
  405.         return true;
  406.     }
RAW Paste Data
Top