Хеш-табли́ца — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Реализации хеш-таблиц есть практически в каждом языке программирования. Например в языке программирования Python есть реализация хеш-таблиц, которую называют словарями. Поэтому вам вряд ли придётся писать свою реализацию этой структуры данных, но знать, что это такое нужно каждому программисту...

Заметки: Теперь самое интересное. Время: Напомню, что О(1) — не моментальное время, а одинаковое всегда. Поиск в массиве с одним элементом и с миллиардом займет одинаковое время. Мы видим, что поиск в таблицах не уступает массивам, а вставка и удаление быстры как в связанных списках. Но в худшем способе все плохо, поэтому важно избегать коллизий (когда много котиков в одной квартире). Коэффициент заполнения вычисляется по формуле: количество элементов в хеш-таблице делим на общее количество элементов (всех котиков делим на количество квартир в доме)...