Хеш табела
У рачунарству, хеш табела (енгл. Hash table) или хеш мапа (енгл. Hash map) је структура података која користи хеш функцију за ефикасно пресликавање одређених кључева (на пример имена људи) у њима придружене вредности (на пример телефонске бројеве). Хеш функција се користи за трансформисање кључа у индекс (хеш) то јест место у низу елемената где треба тражити одговарајућу вредност.
Идеално, хеш функција би требало да пресликава сваки могући кључ у засебан индекс, али овај циљ је у пракси најчешће недоступан. Већина имплементација хеш табела подразумева да су хеш колизије — парови различитих кључева са истим хеш вредностима — нормална појава, и на неки начин се стара да се овај проблем превазиђе.
У добро димензионисаној хеш табели, просечна цена (број рачунарских инструкција) сваког проналажења је независна од броја елемената ускладиштених у табели. Многе имплементације хеш табела такође омогућавају произвољна уношења и брисања парова кључева и вредности уз константну просечну (амортизовану) цену по операцији.[1][2]
У многим ситуацијама, хеш табеле се показују ефикаснијим од стабала претраге или свих других табеларних структура. Зато су хеш табеле у широкој употреби у свим врстама рачунарског софтвера.
Употребе уреди
Асоцијативне табеле уреди
Хеш табеле се обично користе за имплементацију свих врста табела које се чувају у меморији. Користе се за имплементацију асоцијативних низова (низова чији су индекси произвољне ниске или други компликованији објекти), посебно у интерпретираним програмским језицима као што су gawk и perl.
Индекси у базама података уреди
Хеш табеле могу да се користе и за перзистентне структуре података које су смештене на диску, и за индексе база података, мада су балансирана стабла популарнија за ове примене.
Скупови уреди
Осим враћања вредности која одговара датом кључу, многе имплементације хеш табела могу такође да одговоре на питање да ли такав унос постоји или не.
Због тога ове структуре могу да се користе за импелентацију скупа, који просто одговара на питање да ли дати кључ постоји у неком скупу кључева. У овом случају структура може да се поједностави елиминисањем свих делова који се тичу вредности које одговарају кључевима. Хешовање може да се користи за имплементацију било статичких, било динамичких скупова.
Предности уреди
Главна предност хеш табела над другим табеларним структурама података је њена брзина. Ова предност је уочљивија када је број података у табели велики (хиљаде или више). Хеш табеле су посебно ефикасне када максимална количина података може да се предвиди унапред, тако да величина структуре може унапред да се алоцира тако да буде оптимална, и не мора после да се мења.
Ако су сви парови кључева-вредности фиксирани и познати унапред (па додавања и брисања нису дозвољена), просечна цена претраге може да се смањи пажљивим избором хеш функције, величине табеле и унутрашњих структура података. Штавише, тада је могуће направити хеш функцију која не ствара колизије. У овом случају кључеве није потребно чувати у табели.
Референце уреди
- ^ Knuth 1998, стр. 513–558
- ^ Cormen et al. 2001, стр. 221–252.
Литература уреди
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). „11: Hash Tables”. Introduction to Algorithms (2. изд.). -IT Press and McGraw-Hill. стр. 221-252. ISBN 978-0-262-53196-2.
- Knuth, Donald (1998). „6.4: Hashing,”. The Art of Computer Programming'. 3: Sorting and Searching (2nd изд.). Addison-Wesley. стр. 513—558. ISBN 978-0-201-89685-5.
