Хеш табела
From Wikipedia, the free encyclopedia
У рачунарству, хеш табела (енгл. ) или хеш мапа (енгл. ) је структура података која користи хеш функцију за ефикасно пресликавање одређених кључева (на пример имена људи) у њима придружене вредности (на пример телефонске бројеве). Хеш функција се користи за трансформисање кључа у индекс (хеш) то јест место у низу елемената где треба тражити одговарајућу вредност.
Идеално, хеш функција би требало да пресликава сваки могући кључ у засебан индекс, али овај циљ је у пракси најчешће недоступан. Већина имплементација хеш табела подразумева да су хеш колизије — парови различитих кључева са истим хеш вредностима — нормална појава, и на неки начин се стара да се овај проблем превазиђе.
У добро димензионисаној хеш табели, просечна цена (број рачунарских инструкција) сваког проналажења је независна од броја елемената ускладиштених у табели. Многе имплементације хеш табела такође омогућавају произвољна уношења и брисања парова кључева и вредности уз константну просечну (амортизовану) цену по операцији.[1][2]
У многим ситуацијама, хеш табеле се показују ефикаснијим од стабала претраге или свих других табеларних структура. Зато су хеш табеле у широкој употреби у свим врстама рачунарског софтвера.