17,3 тыс подписчиков

🏃 Самоучитель по Go для начинающих. Часть 8. Строки, руны, байты. Пакет strings. Хеш-таблица (map)

15 февраля 202415 фев 2024

9 мин

Оглавление

Немного о кодировках
Строки
Байты и руны

Ранее в уроке про типы данных мы познакомились со строками, рунами и байтами. В этой статье расширим наши знания об этих типах, рассмотрим пакет strings и подробно изучим хеш-таблицы.

← Часть 7

Массивы и слайсы. Append и сopy. Пакет slices

Немного о кодировках

Как известно, компьютер имеет возможность хранить только биты, поэтому для отображения текстовой информации возникла необходимость перевода нулей и единиц в читабельный алфавит. Так возникли первые кодировки текста – таблицы перевода числовых значений в буквы и символы.

На данный момент стандартом является кодировка Unicode из 1 114 112 позиций, разделенных на 17 блоков по 65 536 символов. Все они записываются в шестнадцатеричном представлении с приставкой «U+». Например, латинская буква «a» имеет код «U+0061», русская буква «я» записана как «U+044F».

Исходный код Go определяется как текст в кодировке UTF-8 (Unicode Transformation Format, 8-bit) – стандарт компактного хранения символов Unicode, обладающий обратной совместимостью с ASCII и переменной длиной. Это дает возможность закодировать определенные символы разным количеством байтов. К примеру, в UTF-8 латинский алфавит закодирован одним байтом, а кириллица – двумя. Данная особенность будет иметь значение при вычислении длины строк, что мы увидим в продолжение статьи.

Для более подробного ознакомления с кодировками рекомендуем прочитать статью «Как работают кодировки текста».

👨‍💻 Библиотека Go разработчика

Больше полезных материалов вы найдете на нашем телеграм-канале«Библиотека Go разработчика»

🎓 Библиотека Go для собеса

Подтянуть свои знания по Go вы можете на нашем телеграм-канале «Библиотека Go для собеса»

🧩 Библиотека задач по Go

Интересные задачи по Go для практики можно найти на нашем телеграм-канале«Библиотека задач по Go»

Строки

Байты и руны

Тип данных byte в Go представляет псевдоним для беззнакового 8-битного целочисленного типа uint8. Он принимает значения от 0 до 255, поэтому используются для представления ASCII-символов. Слайсы байт широко применяются в различных библиотеках за счет своей производительности и гибкости.

Тип данных rune определяется как псевдоним для типа int32. Руна соответствует коду символа в таблице Unicode. Так, тип символа µ есть руна со значением 0x00b5.

Строковые литералы

Прежде чем приступить к изучению строк, рассмотрим понятие строкового литерала.

Строковый литерал – это константа типа string, которая является результатом слияния последовательности символов. Литералы бывают двух типов – интерпретируемые и необработанные (или сырые).

Интерпретируемые литералы - это символы, заключенные в двойные кавычки вида "". Текст внутри кавычек представляет собой кодировку UTF-8 отдельных символов. Например, символ µ и его записи \xc2\xb5, \u00b5, \U000000B5 определяют два байта 0xc2 0xb5 символа U+00B5 (µ) в кодировке UTF-8:

Необработанные (сырые) литералы – это символы, заключенные в двойные кавычки вида ``. Их значением является строка из неявно закодированных в UTF-8 символов. В необработанных строковых литералах, в отличие от интерпретируемых, перевод строки осуществляется явно с использованием enter, а символ \n не имеет специального значения.

Под строками в Go подразумевают интерпретируемые строковые литералы. В дальнейшем будем рассматривать именно их, так как они используются чаще необработанных.

Строки

Строки в Go представляют собой неизменяемую последовательность байтов. Содержимое строки есть не что иное, как слайс байтов ([]byte). Именно по этой причине обращение по индексу строки вернет не символ, а его юникод-значение в десятичной системе счисления:

Срез [i:j] возвращает новую строку, которая состоит из байтов исходной, начиная с индекса i и заканчивая индексом j, но исключая его:

В последней строке вывода можно заметить странный символ. Дело в том, что функция fmt.Println пытается декодировать часть строки str[0:1], но получает один единственный байт 0xd1, который не соответствует ни единому символу в UTF-8. Поэтому в результате будет выведен специальный заменяющий символ с кодом 0xfffd.

Строки поддерживают сравнение, которое производится по длине и по байтам:

Поддерживаются также основные операции со строками – конкатенация и интерполяция.

Конкатенация – это операция слияния нескольких объектов (чаще всего строк) в один.

Интерполяция – это операция замены заполнителей строки соответствующими значениями.

Как и во многих других языках программирования, конкатенация строк в Go реализуется с помощью оператора +:

Интерполяция в Go реализована немного иначе, чем в динамических языках. Она осуществляется с использованием функций пакета fmt:

Статья по теме

🏃 Готовимся к интервью по Golang: массивы, слайсы и строки

Итерация по рунам

Цикл for-range по строке на каждой итерации декодирует одну руну в UTF-8:

На выходе получим Unicode представление каждого символа строки и его индекс:

Заметим, что каждая руна здесь занимает два байта, а так как функция len() возвращает количество байтов, занимаемых строкой, а не количество символов, то длина строки в два раза больше ожидаемой – 10 вместо 5. В начале статьи мы уже упоминали о том, что в UTF-8 кириллица занимает два байта, а так как язык Go использует эту кодировку, то на выходе получаем вполне обоснованный результат.

С латинскими символами всё немного иначе:

На выходе получим ожидаемые значения индексов и длины:

В общем случае для получения корректной длины строки следует предварительно преобразовать её в слайс рун или же воспользоваться функцией utf8.RuneCountInString() из пакета unicode/utf8:

Стоит учитывать, что преобразование строки в слайс рун требует немного больше операций и памяти, чем вызов функции utf8.RuneCountInString(). Поэтому с точки зрения производительности эффективнее использовать второй вариант.

Итерация по байтам (индексам)

Как было рассмотрено ранее, обращение напрямую по индексам строки выдаст байтовое представление символов. Это поведение сохраняется при итерации:

В выводе на верхней строке показано десятичное представление нижних 16-ричных значений символов строки в UTF-8:

Чтобы вывести корректные символы строки, нужно воспользоваться функцией fmt.Printf и спецификатором %c:

Пакет strings

Пакет string стандартной библиотеки содержит полезные функции для работы со строками. Давайте рассмотрим некоторые из них:

Подсчет вхождений символа в строку – strings.Count(s, substr string) int:

Замена символов – strings.Replace(s, old, new string, n int) string:

Разбиение символов по разделителю sep – strings.Split(s, sep string) []string:

Слияние строк с разделителем sep – strings.Join(elems []string, sep string) string:

Преобразование символов к нижнему или верхнему регистру – strings.ToLower(s string) или strings.ToUpper(s string):

Теперь поговорим немного о том, как пакет strings может увеличить производительность. Пусть нам необходимо написать программу для конкатенации большого количества строк. Делать это с помощью оператора + неэффективно, так как при каждой операции будет создаваться новая строка. В этой ситуации стоит воспользоваться структурой Builder из пакета strings:

Хеш-таблица

После знакомства со строками, рунами и байтами изучим еще один способ хранения информации в программах, облегчающий её поиск.

Хеш-таблица – это структура данных, позволяющая хранить пары ключ-значение и реализующая интерфейс ассоциативного массива. Как правило, она выполняет три основные операции: добавление новой пары, удаление и поиск существующей по ключу.

Заполнение хеш-таблицы происходит с помощью применения специальной хеш-функции к каждому элементу, которая преобразует ключ в индекс ячейки для записи значений.

Доступ к элементу таблицы производится с помощью вычисления хеш-функции от его ключа. Это значение и будет индексом ячейки с искомым элементом.

Ситуация, при которой хеш-функция от разных ключей выдает один и тот же индекс, называется коллизией. Чем лучше используемая хеш-функция, тем меньше вероятность возникновения и количество коллизий.

Существует два основных метода разрешения коллизий:

Метод списков

Данный метод заключается в связывании конфликтующих значений в цепочку-список. В таком случае время поиска в худшем случае будет пропорционально длине списка. Наихудшей ситуацией является хеширование всех n ключей к одной ячейке.

Метод открытой адресации

В этом подходе все конфликтующие элементы хранятся в самой хеш-таблице без использования списков. При возникновении коллизии производится поиск свободной ячейки для вставки необходимого элемента.

Хеш-таблица (map) в Go

В рамках данной статьи мы не будем углубляться в детали реализации хеш-таблиц в Go. Для полного погружения в тему рекомендуем прочитать следующие материалы: исходный код map, Effective Go: Maps, Мапы в Go: уровень Pro.

Хеш-таблица в Go (также её называют map, мапа, карта) определяется ключевым словом map и создается одним из следующих способов, где keys_type – тип данных ключей, values_type – тип данных значений:

Предпочтительный способ – с использованием make:

С помощью ключевого слова var создается nil-map:

С этим способом нужно быть предельно аккуратным. Если после такого создания мапы попробовать записать значение по ключу, то возникнет panic:

С указанием элементов в скобках:

При этом стоит помнить, что ключами могут быть только сравнимые (comparable) типы данных: числовые (int, float, complex), string, bool, указатель, интерфейс, канал и структуры или массивы, которые содержат значения только этих типов.

Научились создавать мапу, а теперь рассмотрим основные операции над ней:

Вставка: mp[key] = value
Удаление: delete(mp, key)
Поиск: value := mp[key]

Если в мапе не окажется искомого значения, то вернется нулевое значение типа:

Но стоит помнить, что возвращаемое значение будет nil, если нулевое значение типа также является nil.

Для корректной проверки наличия элемента в мапе используется множественное присваивание. В этом случае возвращается пара – само значение и булевая переменная. Если она равна true, это означает присутствие искомого элемента в мапе, иначе – его отсутствие:

Мапа в Go является неупорядоченной структурой данных. Это значит, что при её обходе в цикле вывод будет разниться от запуска к запуску. Чтобы в этом убедиться, запустите следующий код несколько раз:

Передача мапы в функцию

Давайте разберемся с тем, что происходит при передаче мапы в функцию.

Для примера создадим функцию changeMap, которая будет принимать в качестве параметра мапу и изменять в ней значение:

В результате можем увидеть, что значение по ключу 1 изменило своё значение.

Не стоит думать, что мапа передалась по ссылке, так как в Go такое поведение отсутствует. Всё дело в том, что мапа в Go является указателем на структуру hmap:

Давайте немного изменим код, чтобы map2 в функции changeMap объявлялась с помощью make:

В выводе можно заметить, что map2 в changeMap отличается от mp в main:

В этом случае мапа mp передается по значению в changeMap, поэтому не меняется. Все изменения коснутся её локальной копии map2, так как создание мапы с помощью make приводит к инициализации hmap.

Подведём итоги

В этой части самоучителя мы узнали о кодировках и их особенностях, на основе этих знаний довольно подробно изучили устройство строк в Go и пакет strings, а в блоке про хеш-таблицы познакомились с эффективным способом хранения пар ключ-значение и методами разрешения коллизий, рассмотрели структуру данных map в Go.

В следующей статье перейдем к изучению объектно-ориентированного программирования и его основных составляющих: структур, интерфейсов и указателей.

***