Карты (map) позволяют быстро находить значение по указанному ключу. Рассмотрим как их использовать в программах.
В предыдущем уроке мы подробно разобрали цикл for. Посмотрели как его использовать для выполнения повторяющихся действий в программе.
Сегодня мы откроем для себя карту.
Карта — это структура данных. Часто в литературе ее называют хэш — таблицей (hash table). Встречается еще название — ассоциативный массив.
Задача карты сохранить соответствие между ключом и значением.
Основной операций для карты является поиск значения по его ключу. Эта операция очень быстрая и выполняется за постоянное время. Время практически не зависит от количества хранимых ключей и значений.
Данная структура данных имеет одно заметное преимущество перед срезом.
Для того чтобы найти в срезе конкретное значение, нужно перебирать все элементы и если найдется элемент с нужным значением вернуть его.
Карта в отличие от среза, может сделать поиск значительно более эффективным.
При этом ключи и значения в карте хранятся в неупорядоченном виде.
Поэтому, если в задаче требуется работать со значениями в определенном порядке, то карта здесь не подойдет.
Из этих соображений можно сделать полезный вывод.
Каждая структура данных имеет свои плюсы и минусы.
Задача разработчика выбрать самую оптимальную структуру данных для задачи.
Начнем разбираться с картами по нескольким примерам из жизни.
Пример 1
Представим класс из учеников. Вначале урока учитель опрашивает по имени и фамилии всех учеников. При этом учитель зачитывает имена по списку.
Ученик услышав свое имя и фамилию откликается и говорит - Здесь.
Задача учителя получить список учеников, которых нет в классе.
Рассмотрим вначале неоптимальный подход для решения этой задачи.
Допустим, что учитель решил самостоятельно определять кто есть, а кого нет.
Он выбрал следующий вариант — проходить по всем ученикам в классе в заданном порядке и отмечать присутствующих галочкой.
Учитель будет тратить время на лишние действия:
- Выбрать ученика
- Найти его в своем списке — это очень неэффективная операция!
- Отметить, что ученик присутствует в классе
- Перейти к следующему ученику и так до тех пор, пока мы не пройдем по всему классу.
- Выписать всех учеников, которых нет
Но есть лучшее решение.
Будет эффективнее, если идти по списку и опрашивать учеников. Здесь понадобится два действия:
1) Выбрать ученика из своего списка и огласить его имя и фамилию
2) Если получен отклик, поставить галочку, что ученик в классе. Если отклика нет, сразу занести в список отсутствующих.
Видим что при данном подходе, мы быстрее получим результат, чем в первом варианте.
Пример 2
Теперь у нас появилась библиотека.
Для простоты представим, что в нашей библиотеке только 3 книги.
Не тлеющая классика:
- Мастер и Маргарита
- Преступление и наказание
- Война и мир
Допустим Войну и мир взяли почитать. Следующий человек тоже захотел почитать Войну и мир. Чтобы понять, что эту книгу уже взяли, мы должны пройти по списку книг и определить, что ее в этом списке нет. Операция как известно неэффективная, особенно если представить, что книг может быть гораздо больше чем 3.
В этом случае удобнее иметь какую-то картотеку, где мы сужаем область поиска по алфавиту и еще каким-то признакам.
Но вдруг библиотеке подарили замечательную программу
Программа умеет находить книгу по ее имени и причем делает это, всегда за постоянное время.
Работники библиотеки и ее посетители будут очень рады такому повороту событий.
В обоих наших примерах, использование карты даст значительное преимущество перед другими решениями.
Давайте посмотрим как использовать их в Go.
Объявление
Для того чтобы начать использовать карту, нужно определиться какого типа будет ее ключ и значение. Типы могут не совпадать. Для ключей вводится ограничение:
Тип ключа должен быть сравниваемым
К таким типам относятся большинство встроенных типов. Из исключений можно перечислить следующие:
- срез (slice)
- другая карта (map)
- функция (function)
Допустим, нам нужно определить карту для примера номер 1 - класс учеников. В качестве ключа будем использовать строковый тип. Ключом будет имя и фамилия ученика. Строки можно сравнивать между собой и значит можно использовать в качестве ключа. Для значения возьмем булев (логический) тип — есть или нет ученик в классе.
Карта имеет несколько вариантов объявления. Самый простой:
class := map[string]bool{}
Это пустая карта. В ней нет ни одного ключа и значения.
Карту можно сразу заполнить начальными значениями.
На 8 строке мы определи новую карту class и сразу заполнили ее значениями. Значением является тип bool и он отражает факт того, что человек находится в классе.
Для того чтобы определить есть ли человек в классе, воспользуемся операцией чтения из карты.
Чтение
Для чтения значения по ключу используется следующий синтаксис:
isPresent := class["Alice"]
Если ученика нет в классе, то переменная isPresent будет равна false.
Давайте перейдем с совершенно новому примеру.
Реестр погоды
Допустим мы хотим хранить температуру для крупных городов планеты и потом быстро искать по названию города значение температуры.
Здесь также отлично подходит карта.
Посмотрим пример кода инициализации карты:
Пример практически не отличается от нашего предыдущего варианта с классом.
Давайте найдем температуру в городе Moscow и выведем ее на экран.
Если бы городов было миллион, то время поиска значения в карте практически не изменилось бы.
Помните про это замечательное свойство.
Теперь добавим в наш реестр новый город Sydney.
Запись значения
Сделать это можно с помощью операции записи нового ключа и значения:
Обратите внимание на строку 13. В ней происходит запись температуры в городе Sydney. И она равна 35 градусам.
У нашего примера есть один небольшой минус. Если название городов будет совпадать, то мы можем перетереть старое значение и потерять его. В таком случае можно добавить в ключ название страны, в которой этот город находится. Так как название стран практически уникально.
Использование цикла
Также как у среза, можно получить все ключи и значения с помощью использования цикла for range.
Давайте выведем все города и их температуры.
Видим на 14 строке, что определяются две переменные цикла city и temperature. Для карты цикл for range работает немного по другому принципу.
Важный момент заключается в том, что значения будут выводиться в случайном порядке. Это сделано специально разработчиками Go.
Считаем слова
Напоследок посмотрим на программу, которая демонстрирует еще один случай применения карты — подсчет количества слов в предложении.
Опишем программу по шагам.
Вначале создаем новую карту типа map[string]int. Ключом является слово в предложении, а значением количество таких слов в нем.
Далее используем пакет strings для разбиения строки на отдельные слова по символу пробела. Функция Split возвращает срез строк. Проходим по этому срезу и сохраняем в карте слово и к значению прибавляем единицу.
Следует заметить, что при чтении значения по ключу, которого нет в карте Go вернет значение по умолчанию для заданного типа. В нашем случае это будет 0.
В качестве домашней работы попробуйте набрать данную программу в онлайн — редакторе и запустить. Попробуйте разные вариации предложений.
Резюме
Итак, сегодня мы посмотрели как использование карты сокращает время поиска значения по заданному ключу.
В следующих уроках мы коснемся темы многопоточности, так как Go создавался с прицелом на удобную работу с многопоточными программами.
Практика
Переходи по ссылке и пройди практику по данному уроку в обучающей онлайн — платформе Stepik.