Отворено адресирање
Отворено адресирање, или затворено хеширање, је начин решавања судара у хеш табелама. Са овом методом хеш судар решава прескок, или у претрази алтернативних локација у низу (претраге секвенци) све док се циљни запис не пронађе, или слободан простор, што указује на то да не постоји такав кључ у хеш табели[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.