From Wikipedia, the free encyclopedia
Kvadratno proveravanje (енгл. ) 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:
Metod linearnog popunjavanja ima umanjenu efikasnost usled potencijalnog stvaranja efekta grupisanja.
Primer kvadratnog proveravanja:
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.
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:
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:
The problem, here, is to insert a key at an available key space in a given Hash Table using quadratic probing.[1]
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
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
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);
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.