Отворено адресирање

Из Википедије, слободне енциклопедије

Otvoreno adresiranje[уреди]

Hash collision resolved by linear probing (interval=1).

Отворено адресирање, или затворено хеширање, је начин решавања судара у хеш табелама. Са овом методом хаш судар решава прескок, или у претрази алтернативних локација у низу (претраге секвенци) све док се циљни запис не пронађе, или слободан простор, што указује на то да не постоји такав кључ у хеш табели[1] Познати сонде секвенце обухватају

Линеарна претрага 
у којима је интервал претраге фиксиран-углавном је 1.
Квадратна претрага 
у коме се интервал иѕмеђу претрага линеарно повећава (стога, индекси су описани од стране квадратне функције).
Дупло хеширање 
у којем интервал између сонди је фиксна за сваки запис, али се рачуна од стране другог хеш функције.


Карактеристике ових метода[уреди]

Главни компромиси између ових метода су што линеарни прескок има најбоље хеш перформансе али је најосетљивији на груписање, док двоструко хеширање има лоше перформансе хеша али показује готово никакво груписање; квадратни прескок спада између, у оба подручја. Двоструко хеширање могу такође захтевати више израчунавања од осталих облика претраге. Неке методе отвореног адресирања, као што су last-come-first-served hashing и Cuckoo hashing] померају постојеће кључеве у низу како би направили места за нови кључ. Ово даје бољу максималну претрагу од метода на основу сондирања.


Фактор оптерећења[уреди]

Критички утицај на перформансе отвореног адресирања хеш табела је фактор оптерећења, то јест, пропорција места у низу који се користе. Како фактор оптерећења расте ка 100%, број претрага које могу бити потребне да се пронађе или убаци дати кључ, расте драматично. Када се табела напуни, алгоритми ѕа претрагу могу чак престати да се извршавају. Чак и са добрим хеш функцијама, фактори оптерећења су обично ограничени на 80%. Слаба хеш функција може показивати лоше перформансе чак и при веома ниским факторима оптерећења, генерисањем одредјеног груписања. Шта изазива хеш функцију да се гомила, није довољно утврђено, и лако се, ненамерно, напише хеш функција која изазива озбиљне гомилање.

Пример псеудокода[уреди]

Следећи псеудокод је имплементација отвореног адресирања хеш табеле са линеарном претрагом и прескакања за по једно место. Заједнички приступ је ефикасан ако је хеш функција добра. При сваком кораку,функције ѕа постављање и уклањање користе заједничку унутрашњу функцију find_slot да проналази празно место или место које садржи дати кључ.

    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

Други пример показује технику отвореног адресирања. Представљена функција конвертује сваки део интернет адресу протокола, где NOT, XOR, OR и AND су операције над битовима, и << и >> су леве и десне логичких смене:

    // 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

Напомене[уреди]

Напомена1 
Обнова табеле захтева доделу већег спектра и рекурзивно користи задату операцију да убаци све елементе старог низа у нови већи низ. Уобичајено је да се повећа експоненцијално ред величине, на пример дуплирањем стари ред величине.


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
Напомена 2
За све записе у групи, не сме бити никаквих слободних места у њиховом природном положају у хешу и њихове тренутне позиције (у супротном претрага ће се окончати пре него пронађе ѕапис). У овом тренутку у псеудокоду, i је празно место које може се попуњавати наредним записима у групи. ј је такав наредни запис. К је сирова хеш табела где би ѕапис у ј природно се записао у хеш табели, ако није било судара. Овај тест испитује да ли запис у ј правилно позициониран, испуњавајући захтеве табеле, сада када је и праѕно.

Друга техника брисања је једноставно обележавање места као обрисано. То својевремено захтева поновно прављење табеле са отклоњеним обрисаним записима. Ова метода спада у класу О(1) обављањем табеле и брисањем одређених записа.

Метод сложености О (1) је једино могућ у линеарној претрази хеш табела са корачањем за једно место. У случају где многи записи треба да буду избрисани у једној операцији, обележавање места за брисање и касније обнове може бити ефикаснији.


Референце[уреди]

  1. ^ Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Data Structures Using C. Prentice Hall. стр. 456-461, 472. ISBN 978-0-13-200411-4. 

Литература[уреди]