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

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

Хеш колизија разрешена линеарним попуњавањем (interval = 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) је једино могућ у линеарној претрази хеш табела са корачањем за једно место. У случају где многи записи треба да буду избрисани у једној операцији, обележавање места за брисање и касније обнове може бити ефикаснији.

Референце

^ Tenenbaum, Langsam & Augenstein 1990, стр. 456–461, 472

Литература

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

[1] Tenenbaum, Langsam & Augenstein 1990, стр. 456–461, 472

[1]