Абстракция отображение

Вы знакомы с такими структурами данных, как массив, односвязный и двусвязный список, дерево. Вы знаете, какая сложность операций поиска, вставки и удаления для этих структур данных.

В первом спринте вы решали задачу, где определяли кружки, которые посещает хотя бы один ученик в классе. Для решения этой задачи больше всего подходит множество. Сложность операций поиска, вставки и удаления в этой структуре данных зависят от реализации.

Если множество реализовано с использованием бинарного дерева, сложность всех операций логарифмическая. Если же реализовать множество с помощью хеш-таблицы, операции поиска, вставки и удаления элемента выполняются за $O(1)$. В первом спринте мы не разбирали подробно решение задачи про школьные кружки с применением множества. Но важно понимать, какая сложность операций для этой структуры данных. Готовы узнать эту тайну?

Тимофей: Разгадка кроется в использовании хеш-таблиц. Но прежде чем узнать, что такое хеш-таблица, познакомимся с понятием отображения. Представьте, что у вас есть список городов.

Скопировать кодPYTHON
cities = ['Moscow', 'Tula', 'London', 'Paris', 'Leon', 'San Francisco', 'New York'] 

Вы можете сказать в какой стране находится каждый город. Эту информацию удобно хранить в такой структуре данных как словарь.

Скопировать кодPYTHON
city_to_country = {
    'Moscow': 'Russia',
    'Tula': 'Russia',
    'London': 'UK',
    'Paris': 'France',
    'Leon': 'France',
    'San Francisco': 'USA',
    'New York': 'USA',
} 

Есть множество городов и множество стран. И каждому объекту первого множества соответствует какой-то объект из второго множества.

Алла: Получается отображение одного множества на другое.

Тимофей: Верно. В примере каждому объекту из множества городов соответствует какой-то объект из множества стран.

Теперь представьте, что вы пишите приложение, которое помогает пользователям узнавать о предстоящих мероприятиях в своём городе. На сайте есть алфавитный указатель для поиска по городам. То есть у вас есть отображение буквы алфавита на список городов, которые с неё начинаются.

Тимофей: В этом примере букве соответствует список городов.

Алла: Но, например, для Ъ или Ь список будет пустым.

Тимофей: Да, не всегда для любого объекта из одного множества можно найти пару из другого.

Оба примера объединяет то, что объекты одного множества связаны с объектами другого множества. Это и есть отображение.

В программировании абстракция отображение реализована при помощи хеш-таблиц.

Алла: А что это такое?

Тимофей: Скоро я расскажу про хеш-функции и хеш-таблицы.