Back

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




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

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

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

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

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

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

Шта изазива хеш функцију да се гомила, није довољно утврђено, и лако је, ненамерно, написати хеш функцију која изазива озбиљно гомилање.

                                     

1. Пример псеудокода

Следећи псеудокод је имплементација отвореног адресирања хеш табеле са линеарном претрагом и прескакања за по једно место.

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

record pair { key, value } var pair array slot // | i.k.j | // |.j i.k.| or |.k.j i.

| if (i