Каквоехеш-таблица? Структурата от данни хеш-таблица обикновено се реализира с масив. Тя съдържа наредени двойки (ключ, стойност), които са разположени в масива на пръв поглед случайно и непоследователно. В позициите, в които нямаме наредена двойка, имаме празен елемент (null):
Размерът на таблицата (масива), наричаме капацитет(capacity) на хеш-таблицата. Степенназапълненост(loadfactor), наричаме реално число между 0 и 1, което съответства на отношението между броя на запълнените елементи и текущия капацитет. На фигурата имаме хеш-таблица с 3 елемента и капацитет m. Следователно степента на запълване на тази хеш-таблица е 3/m.
Добавянето и търсенето на елементи става, като върху ключа се приложи някаква функция hash(key), която връща число, наречено хеш-код.
Като вземем остатъка при деление на този хеш-код с капацитета m получаваме число между 0 и m-1:
На фигурата е показана хеш-таблица T с капацитет m и хеш-функция hash(key):
Това число ни дава позицията, на която да търсим или добавяме наредената двойка. Ако хеш-функцията разпределя ключовете равномерно, в болшинството случаи на различен ключ ще съответства различна хеш-стойност и по този начин във всяка клетка от масива ще има
най-много един ключ. В крайна сметка получаваме изключително бързо търсене и бързо добавяне. Разбира се, може да се случи различни ключове да имат един и същ хеш-код. Използвайтереализациянаречникчрезхеш-таблици, когатосенуждаетеотмаксималнобързонамираненастойноститепоключ. Капацитетът на таблицата се увеличава, когато броят на наредените двойки в хеш-таблицата стане равен или по-голям от дадена константа, наречена максимална степен на запълване. При разширяване на капацитета (най-често удвояване) всички елементи се преподреждат според своя хеш-код и стойността на новия капацитет. Степента на запълване след преподреждане значително намалява. Операцията е времеотнемаща, но се извършва достатъчно рядко, за да не влияе на цялостната производителност на операцията добавяне.
