Хеширање

Извор: ВикиЕТФ

Хеширање је назив за технику за претраживање података.

Садржај

Како функционише?

Претпоставка је да за сваки податак постоји кључ који тај податак једнозначно одређује (нпр. број индекса једнозначно одређује студента). Питање је како наћи податак чији је кључ дат.

Хеширање је техника која ради на следећи начин: изабере се функција f(K) која кључ трансформише. Вредност ове функције представља улаз у табелу у којој се чува податак.

Функција f(K) назива се хеш функција, а табела се назива хеш табела. Један ред у хеш табели назива се улаз.

Пример: нека је кључ целобројна величина између 0 и 30000, и нека је функција f(K) = K mod 5. За вредност кључа К = 50, вредност f(K) је 0, а за K = 78, f(K) = 3. Хеш табела има пет улаза. Вредност у овим улазима је:

0 50 1 X 2 X 3 78 4 X

Грешка при прављењу умањене слике: Unable to run external programs, passthru() is disabled.
Принцип рада хеширања

Из описа решења и примера може да се закључи:

Сложеност метода

Сложеност када нема колизија је константа, т.ј. не зависи од броја података. Колизије смањују учинковитост овог метода, тако да у најгорем случају (када су сви кључеви у истом улазу) сложеност је линеарна.

Хеш функције

Најчешћа хеш функција је f(K) = K mod n. Њена предност се лако рачуна, број улаза у хеш табелу је n. За остале хеш функције, погледајте посебан чланак Хеш функције.

Колизије

Као што беше речено, колизија је појава да хеш функција мапира два податка с различитим кључевима у исти улаз. Два метода су развијена да би се овај проблем решио: отворено адресирање и уланчавање. О њима, више у чланку Разрешавање колизија.

Личне алатке
Именски простори
Варијанте
Акције
Навигација
Алатке