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

Хеш колизија разрешена линеарним попуњавањем (interval = 1).

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

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

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

[уреди | уреди извор]

Главни компромиси између ових метода су што линеарни прескок има најбоље хеш перформансе али је најосетљивији на груписање, док двоструко хеширање има лоше перформансе хеша али показује готово никакво груписање; квадратни прескок спада између, у оба подручја. Двоструко хеширање могу такође захтевати више израчунавања од осталих облика претраге. Неке методе отвореног адресирања, као што су last-come-first-served 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 је празно место које може се попуњавати наредним записима у групи. ј је такав наредни запис. К је сирова хеш табела где би ѕапис у ј природно се записао у хеш табели, ако није било судара. Овај тест испитује да ли запис у ј правилно позициониран, испуњавајући захтеве табеле, сада када је и праѕно.

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

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

Референце

[уреди | уреди извор]
  1. ^ Tenenbaum, Langsam & Augenstein 1990, стр. 456–461, 472

Литература

[уреди | уреди извор]