Квадратно проверавање

Квадратно проверавање (енгл. Quadratic probing) функција са отвореним адресирањем у програмирању за решавање колизија кад нови податак треба убацити у хеш табелу. Квадратно проверавање користи оригинални индекс кључа који се сабира са вредношћу квадрата од к где к узима вредности од 1 до м, где је м величина хеш табеле.

Квадратно проверавање представља алтернативу линеарном попуњавању која решава проблем тзв. ефекта груписања.

За дату хеш вредност, индекси генерисани линеарним попуњавањем гласе:

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

Метод линеарног попуњавања има умањену ефикасност услед потенцијалног стварања ефекта груписања.

Пример квадратног проверавања:

$H+1^{2},H+2^{2},H+3^{2},H+4^{2},...,H+k^{2}$

Квадратним проверавањем се елиминише ефекат груписања кључева који се јавља код линеарног попуњавања, јер се уместо испитивања сукцесивних локација врши квадратно испитивање. То јест, испитују се 1-ва, 4-та, 9-та, 16-та, итд. локација од почетне, природне локације кључа. Ипак, ако два кључа имају исту природну локацију, онда је пробни низ локација опет исти. Ова чињеница доводи до блаже форме груписања кључева која се назива секундарно груписање.

Квадратна функција

Нека је х(к) хеш функција која пресликава елемент к у цео број у интервалу [0,м-1], где је м величина хеш табеле. Нека је и-та позиција квадратне провере за вредност к дата функцијом:

$h(k,i)=(h(k)+c_{1}i+c_{2}i^{2}){\pmod {m}}$

Где је ц₂ ≠ 0. Ако је ц₂ = 0, тада х(к,и) представља функцију линеарног попуњавања. За дату хеш табелу, вредности ц₁ и ц₂ су константне.

Примери:

• Ако је $h(k,i)=(h(k)+i+i^{2}){\pmod {m}}$, тада је секвенца попуњавања (проверавања) $h(k),h(k)+2,h(k)+6,...$
• За м = 2^н, добар избор за константе би био ц₁ = ц₂ = 1/2, зато што су вредности х(к,и) за и из интервала [0,м-1] сви различити. Тада је секвенца попуњавања (проверавања)$h(k),h(k)+1,h(k)+3,h(k)+6,...$ где се вредности увећавају за 1, 2, 3, ...
• За прост број м > 2, већина избора константи ц₁ и ц₂ ће дати различите х(к,и) за и из интервала [0, (м-1)/2]. Ти избори укључују ц₁ = ц₂ = 1/2, ц₁ = ц₂ = 1, и ц₁ = 0, ц₂ = 1. Зато што има отприлике м/2 различитих попуњавања за дати елемент, тешко је гарантовати да ће попуњавања успети ако је број попуњених места у табели веци од м/2.

Уметање елемента у хеш табелу коришћењем квадратног проверавања

Тхе проблем, хере, ис то инсерт а кеy ат ан аваилабле кеy спаце ин а гивен Хасх Табле усинг qуадратиц пробинг.

Алгоритам за уметање кључа у хеш табелу

 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 функција за уметање елемента у хеш табелу

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

Тражење елемента коришћењем квадратног проверавања

Алгоритам који врши претрагу хеш табеле

 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 функција за претрагу елемента у хеш табели

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

Види још

• Двоструко хеширање
• Хеш табела
• Линеарно попуњавање

Спољашње везе

• Туториал/qуадратиц пробинг
• Алгоритми, Миодраг Живковић