Уебсайт за олимпиадно програмиране
Хеш таблицата е много важна структура от данни. Използвайки хеш-таблица, можете ефективно да приложите асоциативен масив (карта).
Хеш таблиците работят въз основа на хеш функции. Нека имаме някакъв набор от обекти A = . Въвеждаме функция f, която присвоява определен номер на всеки обект. Тогава е очевидно, че ако f(a) != f(b), тогава a не съвпада точно с b. Предимството на използването на хеш функции е добре показано при сравняване на низове, числови последователности и т.н. Има обаче ограничения за хеш функцията. Първо, трябва да бъде бърз за изчисляване. Второ, неговите стойности трябва да бъдат равномерно разпределени в обхвата (той е ограничен от типа на върнатата стойност). Еднаквостта на хеш функцията намалява броя на колизиите - съвпадения на стойността на хеш функцията за различни обекти. Имайте предвид, че ако f(a) = f(b), тогава трябва изрично да проверим дали a и b са равни, което отнема много време за едни и същи низове.
Да се върнем на хеш таблиците. Трябва да се научим как да внедряваме структури от данни от тип "set" (набор) с операциите add(x) (добавяне на елемент x към множеството) и contains(x) (проверка дали x се съдържа в множеството) и "речник" (асоциативен масив) с операциите put(x, y) (асоцииране на ключа x със стойността y) и get(x) (връщане на стойността y, свързана с ключа x). Има няколко опции за внедряване на тези структури от данни, както с помощта на хеш функции, така и с други методи и алгоритми (например двоични дървета).
Помислете за верижния метод. Всъщност ние просто модифицираме мултилиста. Да предположим, че имаме хеш функция hash(x) за обекти от някакъв набор A. Сега ще измислим функция index(y), която ще върне номера на главата в мултисписъка по стойността на обичайната хеш функция. Позволи ниH цели, тогава можем да вземем index(y) = abs(y) % H. Освен това всичко е подобно на обичайния мултилист.
Внедряване в Java (без оптимизации):
Имайте предвид, че нашите хеш таблици не могат да премахват елементи. Разбира се, можете да добавите тази функция, но нейното прилагане е изключително рядко. Във всеки случай олимпиадите обикновено използват стандартни хеш-таблици (HashSet и HashMap в Java, в C++, std::set и std::map, базирани на червено-черни дървета, се използват вместо хеш-таблици). В някои (много редки) случаи обаче стандартните реализации не са достатъчни.