Хеш таблица най-просто наричаме data structure от тип „ключ-данни“, която можем да си представим като таблица с 2 колони, чиято цел е да съхранява в едната колона „указатели“, а в другата – „данните, към които тези указатели сочат“.
„Данните“ от втората колона могат да са от всякакъв тип, както и да не са уникални. Но не и „указателите“.
Хеш таблици се използват например от компилаторите на различните програмни езици, и по-точно, когато при компилиране отделните променливи се съхраняват в хеш таблица с „указател“ – името на променливата, а „данни“ – стойността на променливата.
Управлението на хеш таблиците – обхождане, вмъкване на нов елемент, изтриване… са по принцип бавни операции. За олекотяване на тези процеси е измислено т.н. „хеширане“ – с помощта на т.н. „хеш функция“ да се преобразува „указателят“ в адрес в паметта, където са съответните „данни“.
Има 3 операции, които могат да бъдат извършвани върху хеш-таблиците – добавяне на нов елемент, намиране по указател, изтриване по указател.
И трите се извършват по указателя, тоест, каквото и искаме да направим с информацията – можем да го направим само по указателя.
Характерно за хеш-функциите е т.н. „определеност“ или „точност“, тоест, за дадена хеш функция, при различни подавани аргументи, резултатът е винаги различен. Не трябва да имаме еднакъв резултат за различни аргументи. Тоест, хеш-функциите са детерминистични. Което също значи, че ако от една хеш-функция получим различни резултати, то значи и входните им аргументи са различни.
Литература:
https://bg.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88_%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0