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