Множество и словарь. Реализация на хеш-таблицах

Редактирование этой статьи в ближайшее время не планируется.

Необходимую информацию о хешировании и хеш-таблицах можно получить из:

• Википедии (кратко, ёмко);
• Статьи RSDN (более подробно);
• Главы 11 книги Кормена (исчерпывающе). Желающие могут посмотреть лекцию;
• Раздела 3.4 книги Седжвика (очень подробно и с авторскими исследованиями; ознакомление лучше проводить с помощью слайдов или сайта);
• Раздела 3.7 и пункта 3.7.1 книги Скиены (две с половиной страницы), а также слайдов.

Реализация множеств и словарей на хеш-таблицах в STL появилась в стандарте C++11. Сведения о контейнерах unordered_set, unordered_multiset, unordered_map и unordered_multimap можно найти в:

• Материалах cplusplus.com [1], [2];
• Новом издании книги Джосьютиса.

Ссылки на задачи

• ACMP #505 — Забор

Ссылки

• Codeforces — Blowing up unordered_map, and how to stop getting hacked on it