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 linearnom popunjavanju koja rešava problem tzv. efekta grupisanja.

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

H + 1 , H + 2 , H + 3 , H + 4 , ... , H + k

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

Primer kvadratnog proveravanja:

H + 1^2 , H + 2^2 , H + 3^2 , H + 4^2 , ... , H + k^2

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:

h(k,i) = ( h(k) + c_1 i + c_2 i^2 )  \pmod{m}

Gde je c2 ≠ 0. Ako je c2 = 0, tada h(k,i) predstavlja funkciju linearnog popunjavanja. Za datu heš tabelu, vrednosti c1 i c2 su konstantne.

Primeri:

  • Ako je h(k,i) = (h(k) + i + i^2) \pmod{m}, tada je sekvenca popunjavanja (proveravanja) h(k), h(k)+2, h(k)+6, ...
  • Za m = 2n, dobar izbor za konstante bi bio c1 = c2 = 1/2, zato što su vrednosti h(k,i) za i iz intervala [0,m-1] svi različiti. Tada je sekvenca popunjavanja (proveravanja)h(k), h(k)+1, h(k)+3, h(k)+6, ... gde se vrednosti uvećavaju za 1, 2, 3, ...
  • Za prost broj m > 2, većina izbora konstanti c1 i c2 će dati različite h(k,i) za i iz intervala [0, (m-1)/2]. Ti izbori uključuju c1 = c2 = 1/2, c1 = c2 = 1, i c1 = 0, c2 = 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.[1]

Algoritam za umetanje ključa u heš tabelu[уреди]

 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

C funkcija za umetanje elementa u heš tabelu[уреди]

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);
}

Traženje elementa korišćenjem kvadratnog proveravanja[уреди]

Algoritam koji vrši pretragu heš tabele[уреди]

 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

C funkcija za pretragu elementa u heš tabeli[уреди]

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);
}

Vidi još[уреди]

Reference[уреди]

  1. ^ Horowitz, Sahni, Anderson-Freed (2011). Fundamentals of Data Structures in C. University Press. ISBN 978-81-7371-605-8. 

Spoljašnje veze[уреди]