Изворни код странице Kvadratno proveravanje


'''Kvadratno proveravanje''' ({{јез-енг|Quadratic probing}}) funkcija sa otvorenim adresiranjem u [[Програмирање|programiranju]] za rešavanje kolizija kad novi podatak treba ubaciti u [[Хеш табела|heš tabelu]]. Kvadratno proveravanje koristi originalni indeks ključa koji se sabira sa vrednošću kvadrata od k gde k uzima vrednosti od 1 do m, gde je m veličina heš tabele. 

Kvadratno proveravanje predstavlja alternativu [[Linearno popunjavanje|linearnom popunjavanju]] koja rešava problem tzv. [[efekat gupisanja|''efekta grupisanja'']].

Za datu heš vrednost, indeksi generisani linearnim popunjavanjem glase:

<math>H + 1 , H + 2 , H + 3 , H + 4 , ... , H + k</math>

Metod linearnog popunjavanja ima umanjenu efikasnost usled potencijalnog stvaranja efekta grupisanja. 

Primer kvadratnog proveravanja:

<math>H + 1^2 , H + 2^2 , H + 3^2 , H + 4^2 , ... , H + k^2</math>

Kvadratnim proveravanjem se eliminiše efekat grupisanja ključeva koji se javlja kod linearnog popunjavanja, jer se umesto ispitivanja sukcesivnih lokacija vrši kvadratno ispitivanje. To jest, ispituju se 1-va, 4-ta, 9-ta, 16-ta, itd. lokacija od početne, prirodne lokacije ključa. Ipak, ako dva ključa imaju istu prirodnu lokaciju, onda je probni niz lokacija opet isti. Ova činjenica dovodi do blaže forme grupisanja ključeva koja se naziva [[sekundarno grupisanje]]. 

== Kvadratna funkcija ==


Neka je h(k) heš funkcija koja preslikava element k u ceo broj u intervalu [0,m-1], gde je m veličina heš tabele. Neka je i-ta pozicija kvadratne provere za vrednost k data funkcijom: 
:<math>h(k,i) = ( h(k) + c_1 i + c_2 i^2 )  \pmod{m}</math>
Gde je c<sub>2</sub> ≠ 0. Ako je c<sub>2</sub> = 0, tada h(k,i) predstavlja funkciju linearnog popunjavanja. Za datu heš tabelu, vrednosti c<sub>1</sub> i c<sub>2</sub> su konstantne.

'''Primeri:'''
* Ako je <math>h(k,i) = (h(k) + i + i^2) \pmod{m}</math>, tada je sekvenca popunjavanja (proveravanja) <math>h(k), h(k)+2, h(k)+6, ...</math>
* Za m = 2<sup>n</sup>, dobar izbor za konstante bi bio c<sub>1</sub> = c<sub>2</sub> = 1/2, zato što su vrednosti h(k,i) za i iz intervala [0,m-1] svi različiti. Tada je sekvenca popunjavanja (proveravanja)<math>h(k), h(k)+1, h(k)+3, h(k)+6, ...</math> gde se vrednosti uvećavaju za 1, 2, 3, ...
* Za prost broj m > 2, većina izbora konstanti c<sub>1</sub> i c<sub>2</sub> će dati različite h(k,i) za i iz intervala [0, (m-1)/2]. Ti izbori uključuju c<sub>1</sub> = c<sub>2</sub> = 1/2, c<sub>1</sub> = c<sub>2</sub> = 1, i c<sub>1</sub> = 0, c<sub>2</sub> = 1. Zato što ima otprilike m/2 različitih popunjavanja za dati element, teško je garantovati da će popunjavanja uspeti ako je broj popunjenih mesta u tabeli veci od m/2.

== Umetanje elementa u heš tabelu korišćenjem kvadratnog proveravanja ==

The problem, here, is to insert a key at an available key space in a given Hash Table using quadratic probing.<ref>{{cite book|last=Horowitz, Sahni, Anderson-Freed|title=Fundamentals of Data Structures in C|year=2011|publisher=University Press|isbn=978-81-7371-605-8|pages=}}</ref>

=== Algoritam za umetanje ključa u heš tabelu ===

<code>
  1. Get the key k
  2. Set counter j = 0
  3. Compute hash function h[k] = k % SIZE
  4. If hashtable[h[k]] is empty
          (4.1) Insert key k at hashtable[h[k]]
          (4.2) Stop
     Else
         (4.3) The key space at hashtable[h[k]] is occupied, so we need to find the next available key space
         (4.4) Increment j
         (4.5) Compute new hash function h[k] = ( k + j * j ) % SIZE
         (4.6) Repeat Step 4 till j is equal to the SIZE of hash table
  5. The hash table is full
  6. Stop
</code>

=== C funkcija za umetanje elementa u heš tabelu ===
<source lang="c">

int quadratic_probing_insert(int *hashtable, int key, int *empty)
{
    /* hashtable[] is an integer hash table; empty[] is another array which indicates whether the key space is occupied;
       If an empty key space is found, the function returns the index of the bucket where the key is inserted, otherwise it 
       returns (-1) if no empty key space is found */

    int j = 0, hk;
    hk = key  % SIZE;
    while(j < SIZE) 
    {
        if(empty[hk] == 1)
        {
            hashtable[hk] = key;
            empty[hk] = 0;
            return (hk);
        }
        j++;
        hk = (key + j * j) % SIZE;
    }
    return (-1);
}

</source>

== Traženje elementa korišćenjem kvadratnog proveravanja ==

=== Algoritam koji vrši pretragu heš tabele ===

<code>
  1. Get the key k to be searched
  2. Set counter j = 0
  3. Compute hash function h[k] = k % SIZE
  4. If the key space at hashtable[h[k]] is occupied
          (4.1) Compare the element at hashtable[h[k]] with the key k.
          (4.2) If they are equal
          (4.2.1) The key is found at the bucket h[k]
          (4.2.2) Stop
     Else
          (4.3) The element might be placed at the next location given by the quadratic function
          (4.4) Increment j
          (4.5) Compute new hash function h[k] = ( k + j * j ) % SIZE
          (4.6) Repeat Step 4 till j is greater than SIZE of hash table
  5. The key was not found in the hash table
  6. Stop
</code>

=== C funkcija za pretragu elementa u heš tabeli ===

<source lang="c">
int quadratic_probing_search(int *hashtable, int key, int *empty)
{
    /* If the key is found in the hash table, the function returns the index of the hashtable where the key is inserted, otherwise it 
       returns (-1) if the key is not found */ 

    int j = 0, hk;
    hk = key  % SIZE;
    while(j < SIZE) 
    {
        if((empty[hk] == 0) && (hashtable[hk] == key))
            return (hk);
        j++;
        hk = (key + j * j) % SIZE;
    }
    return (-1);
}
</source>

== Vidi još ==
* [[Dvostruko heširanje]]
* [[Хеш табела|Heš tabela]]
* [[Linearno popunjavanje]]

== Reference ==
{{reflist}}

== Spoljašnje veze ==
* [http://research.cs.vt.edu/AVresearch/hashing/quadratic.php Tutorial/quadratic probing]
* [http://poincare.matf.bg.ac.rs/~ezivkovm//nastava/algoritmi.pdf Algoritmi], Miodrag Živković

{{normativna kontrola}}

[[Категорија:Seminarski radovi/MATF mart 2014.]]
[[Категорија:Хеширање]]