Loading...

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

avatar Георги Кацаров 2 минути
Какво е "Хеш таблица"?

Ако вече сте придобили базовите знания за структурите от данни, може би вече имате по-конкретни въпроси към отделните структури от данни. Съществуват множество и най-различни видове структури от данни, всеки от които удовлетворява различни нужди. Едни от най-разпространените типове структури от данни са т.нар. „Хеш таблици“ (или „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“ е точно за вас. Не пропускате тази възможност, очакваме ви!

Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.