Какво е "Хеш таблица"?

Ако вече сте придобили базовите знания за структурите от данни, може би вече имате по-конкретни въпроси към отделните структури от данни. Съществуват множество и най-различни видове структури от данни, всеки от които удовлетворява различни нужди. Едни от най-разпространените типове структури от данни са т.нар. „Хеш таблици“ (или „Hash Tables“). Какво представляват те?

Какво е хеш таблица?

Хеш таблицата (наричана още и „hash map“) е вид структура от данни, в която е въплътена концепцията на асоциативните масиви - структура от данни, която e съставена от два взаимосвързани елемента - ключ (key) и стойност (value). При хеш таблицата имаме хеш функция, която изчислява (генерира) индекс, който също се нарича и „хеш код“ (“hash code” ). По принцип този индекс е уникален и указва слота (или позицията), в която се съхранява дадена информация, но повечето хеш таблици употребяват неперфектни функции, което може да доведе до дублиране на индекси (генериране на един и същи индекс два или повече пъти). Този проблем е познат като „колизия“ (“Collision”) и добрата новина е, че той е отстраним.

Как да отстраним колизия?

Хеш колизиите обикновено са неизбежни, когато хешираме случаен поднабор от широк набор от възможни ключове. Например, ако имаме 2450 ключа, които ще хешираме като индекси и те трябва да се разпределят поравно и на напълно случаен принцип между милион позиции, съществува вероятност от 95% най-малко два от ключовете да бъдат хеширани към един и същи слот.

Именно поради факта, че това е често явление, всички имплементации на хеш таблици имат някакво решение на проблема с колизията. Един от тях е т.нар. „Separate Chaining“. Какво представлява той?

При метода “Separate chaining” всяка позиция/слот е независима и съществува списък от точки на влизане, които имат един и същи индекс. Как тогава програмната логика разбира коя позиция е правилната измежду няколко позиции с един и същи индекс? Тайната е в оперативното време, което е необходимо на таблицата, от влизането през индекса до идентифицирането на търсената позиция. Това време е уникална стойност за всяка отделна позиция (която е константна величина). По този начин хеш таблицата успява да направи точна и ясна разлика между няколко различни позиции, които са „именувани“ с един и същи индекс.

Съществуват и други начини за избягване на колизията, както и други видове структури от данни, с които трябва да се запознаете, ако искате да се научите как да надграждате различни структури от данни с цел оптимизиране решаването на специфични проблеми. Ако вече имате основни познания в имплементацията на линейни и дърворидни структури от данни и основните алгоритми за тяхната реализация и желаете да се запознаете с хеш таблици, red-black trees и avl trees – онлайн курсът „Data Structures Advanced (with Java) - април 2020“ е точно за вас. Не пропускате тази възможност, очакваме ви!