Otvoreno adresiranje

Heš kolizija razrešena linearnim popunjavanjem (interval = 1).

Otvoreno adresiranje, ili zatvoreno heširanje, je način rešavanja sudara u heš tabelama. Sa ovom metodom heš sudar rešava preskok, ili u pretrazi alternativnih lokacija u nizu (pretrage sekvenci) sve dok se ciljni zapis ne pronađe, ili slobodan prostor, što ukazuje na to da ne postoji takav ključ u heš tabeli Poznati sonde sekvence obuhvataju

Linearno popunjavanje

u me je interval pretrage fiksiran-uglavnom je 1.

Kvadratno popunjavanje

u kome se interval pretrage linearno povećava (stoga, indeksi su opisani od strane kvadratne funkcije).

Duplo heširanje

u kojem je interval pretrage fiksan za svaki zapis, ali se računa od strane druge heš funkcije.

Karakteristike ovih metoda

Glavni kompromisi između ovih metoda su što linearni preskok ima najbolje heš performanse ali je najosetljiviji na grupisanje, dok dvostruko heširanje ima loše performanse heša ali pokazuje gotovo nikakvo grupisanje; kvadratni preskok spada između, u oba područja. Dvostruko heširanje mogu takođe zahtevati više izračunavanja od ostalih oblika pretrage. Neke metode otvorenog adresiranja, kao što su last-come-first-served hashing i kukavičje heširanje pomeraju postojeće ključeve u nizu kako bi napravili mesta za novi ključ. Ovo daje bolju maksimalnu pretragu od metoda na osnovu sondiranja.

Faktor opterećenja

Kritičan uticaj na performanse otvorenog adresiranja heš tabela je faktor opterećenja, to jest, proporcija mesta u nizu koji se koriste. Kako faktor opterećenja raste ka 100%, broj pretraga koje mogu biti potrebne da se pronađe ili ubaci dati ključ, raste dramatično.

Kada se tabela napuni, algoritmi ѕa pretragu mogu čak prestati da se izvršavaju. Čak i sa dobrim heš funkcijama, faktori opterećenja su obično ograničeni na 80%. Slaba heš funkcija može pokazivati loše performanse čak i pri veoma niskim faktorima opterećenja, generisanjem određenog grupisanja.

Šta izaziva heš funkciju da se gomila, nije dovoljno utvrđeno, i lako je, nenamerno, napisati heš funkciju koja izaziva ozbiljno gomilanje.

Primer pseudokoda

Sledeći pseudokod je implementacija otvorenog adresiranja heš tabele sa linearnom pretragom i preskakanja za po jedno mesto.

Zajednički pristup je efikasan ako je heš funkcija dobra. Pri svakom koraku, funkcije ѕa postavljanje i uklanjanje koriste zajedničku unutrašnju funkciju find_slot da pronalazi prazno mesto ili mesto koje sadrži dati ključ.

    record pair { key, value }
var pair array slot[0..num_slots-1]

    function find_slot(key)
    i := hash(key) modulo num_slots
    // search until we either find the key, or find an empty slot.
    while (slot[i] is occupied) and ( slot[i].key ≠ key )
        i = (i + 1) modulo num_slots
    return i

    function lookup(key)
    i := find_slot(key)
    if slot[i] is occupied   // key is in table
        return slot[i].value
    else                     // key is not in table
        return not found

     function set(key, value)
    i := find_slot(key)
    if slot[i] is occupied   // we found our key
        slot[i].value = value
        return
    if the table is almost full
        rebuild the table larger (note 1)
        i = find_slot(key)
    slot[i].key   = key
    slot[i].value = value

Drugi primer pokazuje tehniku otvorenog adresiranja. Predstavljena funkcija konvertuje svaki deo internet adresu protokola, gde NOT, XOR, OR i AND su operacije nad bitovima, i << i >> su leve i desne logičkih smene:

    // key_1,key_2,key_3,key_4 are following 3-digit numbers - parts of ip address xxx.xxx.xxx.xxx
function ip(key parts)
    j := 1
    do
        key := (key_2 << 2)
        key := (key + (key_3 << 7))
        key := key + (j OR key_4 >> 2) * (key_4) * (j + key_1) XOR j
        key := key AND _prime_    // _prime_ is a prime number
        j := (j+1)
    while collision
    return key

Napomene

Napomena1

Obnova tabele zahteva dodelu većeg spektra i rekurzivno koristi zadatu operaciju da ubaci sve elemente starog niza u novi veći niz. Uobičajeno je da se poveća eksponencijalno red veličine, na primer dupliranjem starog reda veličine.

function remove(key)

     i := find_slot(key)
     if slot[i] is unoccupied
         return   // key is not in the table
     j := i
     loop
         mark slot[i] as unoccupied
        r2: (note 2)
         j := (j+1) modulo num_slots
         if slot[j] is unoccupied
             exit loop
         k := hash(slot[j].key) modulo num_slots
         // k lies cyclically in ]i,j]
         // |    i.k.j |
         // |....j i.k.| or  |.k..j i...

| if ( (i<=j) ? ((i<k)&&(k<=j)) : ((i<k)||(k<=j)) )

             goto r2;
         slot[i] := slot[j]
         i := j

Napomena 2

Za sve zapise u grupi, ne sme biti nikakvih slobodnih mesta u njihovom prirodnom položaju u hešu i njihove trenutne pozicije (u suprotnom pretraga će se okončati pre nego pronađe ѕapis). U ovom trenutku u pseudokodu, i je prazno mesto koje može se popunjavati narednim zapisima u grupi. j je takav naredni zapis. K je sirova heš tabela gde bi ѕapis u j prirodno se zapisao u heš tabeli, ako nije bilo sudara. Ovaj test ispituje da li zapis u j pravilno pozicioniran, ispunjavajući zahteve tabele, sada kada je i praѕno.

Druga tehnika brisanja je jednostavno obeležavanje mesta kao obrisano. To u nekom trenutku zahteva ponovno pravljenje tabele sa otklonjenim obrisanim zapisima. Ova metoda spada u klasu O(1) obavljanjem tabele i brisanjem određenih zapisa.

Metod složenosti O(1) je jedino moguć u linearnoj pretrazi heš tabela sa koračanjem za jedno mesto. U slučaju gde mnogi zapisi treba da budu izbrisani u jednoj operaciji, obeležavanje mesta za brisanje i kasnije obnove može biti efikasniji.

Literatura

• Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Data Structures Using C. Prentice Hall. str. 456—461,472. ISBN 978-0-13-200411-4.