Фон

Кодирование строк, вероятно, не будет тем, о чем вас спросят прямо на собеседовании по проектированию системы. Но это может возникнуть как побочный вопрос. Допустим, вы хотите отправить длинную строку по сети и распечатать ее по частям на другом конце. Интервьюер может спросить, есть ли что-то, на что вам нужно обратить внимание, если набор символов не является ASCII. Ответ положительный. Например, нельзя произвольно сегментировать массив байтов, потому что символ может быть закодирован в несколько байтов. В этом случае ваша сегментация должна уважать границы символов; в противном случае содержимое может быть повреждено.

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

Юникод, чтобы управлять ими всеми

Мир строкового кодирования сложен в основном по историческим причинам. Многие региональные, юрисдикционные и языковые схемы кодирования строк приходили и уходили, процветали и исчезали. Но если и есть один настоящий король из моря схем кодирования, то это Юникод. Большинство современных языков программирования и инструментов поддерживают Unicode. А Unicode охватывает все символы в мире (это слишком упрощенное утверждение, но пока достаточно подумать об этом таким образом). Итак, если вы знаете Unicode, у вас есть путь вперед в вопросах кодировки строк.

Чтобы устранить первое заблуждение, которое часто возникает у людей: Unicode не является схемой кодирования как таковой. Он не определяет, как символы хранятся в байтах. Здесь задействован двухэтапный процесс. Unicode определяет взаимно-однозначное отображение символа в кодовую точку (считайте это магическим числом). Например, A - 0x41; Ǽ равно 0x01FC; ⌘ - это 0x2318. 🚒 - это 0x01f692. Это первый шаг. Второй шаг - сохранить кодовую точку в байтах. Unicode допускает чуть более миллиона возможных уникальных символов. Интуитивно вы можете сохранить числовое значение каждой кодовой точки как int32. Фактически это кодировка фиксированной длины UTF-32.

UTF-32 - это хорошо и просто, но это расточительно, если ваши символы в основном состоят из ASCII, который находится в диапазоне от 0 до 127. Вот где UTF-8 пригодится. Чтобы устранить вторую распространенную путаницу: UTF-8 не всегда составляет 1 байт на символ. Он пытается уместить кодовую точку в 1 байт, что подходит для всех символов ASCII. Кстати, поскольку значения кодовой точки Unicode для символов ASCII совпадают со значениями кодировки ASCII (конечно, это сделано по дизайну), ASCII и UTF-8 совместимы для символов ASCII. Когда кодовая точка не помещается в 1 байт, UTF-8 использует 2, 3, до 4 байтов (до 6 байтов до изменения стандарта в 2003 году). Другими словами, UTF-8 - это кодировка переменной длины.

Теперь вам нужен способ узнать, сколько байтов используется для символа. UTF-8 резервирует старшие биты для обозначения этого. Шаблон 0xxxxxxx для 1 байта. 110xxxxx 10xxxxxx для 2 байтов. 1110xxxx 10xxxxxx 10xxxxxx для 3 байтов. И 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx для 4 байтов. Пятна x могут иметь значение 0 или 1 и используются для кодирования значения кодовой точки. Например, A кодируется как 01000001; Ǽ кодируется как 11000111 10111100, ⌘ кодируется как 11101100 10001100 10011000. 🚒 кодируется как 11110000 10011111 10011010 10010010.

Наивысшая кодовая точка, которая может быть представлена ​​2 байтами UTF-8, - это 0x7FF (2¹²-1), так как из первого байта доступно 5 бит, а из второго байта - 6. Когда у вас много символов, кодовые точки которых выше 0x7FF, вы в конечном итоге используете много 3 или 4 байта. Переход на UTF-16 сэкономит вам несколько байтов. UTF-16 по умолчанию использует 2 байта для хранения кодовой точки и при необходимости удваивает ее до 4 байтов. Поскольку у него меньше вариаций длины, он может освободить больше битов для фактического использования и, таким образом, может хранить больше кодовых точек в 2 байтах, чем UTF-8. Например, ⌘ в UTF-16 равно 00100011 00011000, используя только 2 байта вместо 3, как в UTF-8. Детали кодировки UTF-16 немного сложнее. Я бы сказал, что это выходит за рамки минимума.

И последнее: вы, возможно, слышали о концепции метки порядка байтов (BOM) для Unicode. Иногда его включают в начало потока байтов, чтобы указать порядок байтов данных. Он менее полезен для UTF-8, поскольку UTF-8 ориентирован на байты. Вы читаете по 1 байту за раз. Но это очень полезно для UTF-16 и UTF-32, потому что в этих случаях вам нужно будет читать 1 «слово» - 2 байта и 4 байта соответственно. Метка порядка байтов - это магическое число, порядок байтов которого говорит вам, нужно ли вам перевернуть байты внутри каждого слова, чтобы соответствовать порядку байтов в вашей хост-системе.

Пишите код с кодировкой строк в уме

Теперь, когда вы понимаете самый минимум Unicode, давайте посмотрим, как это работает, когда вы фактически пишете код. В конце концов, вам может потребоваться написать код или, по крайней мере, поговорить о написании кода на собеседовании по проектированию системы. Минимум, который вам нужно знать о кодировке строк при написании кода, состоит из двух частей: (1) как строки кодируются в исходном коде (строковый литерал); (2) как они представлены в памяти. Давайте рассмотрим несколько языков программирования, чтобы получить конкретные примеры.

Голанг

Я начну с голанга, потому что это веселый язык. Исходный код Golang должен быть в кодировке UTF-8. А тип string в Golang - это просто массив байтов. Поэтому, когда вы пишете var str string = "hello world" в Golang, кодировка "hello world" UTF-8 сохраняется в массиве str байтов.

Golang также поддерживает escape-кодовые точки Unicode в строковых литералах. Например, вы можете написать var str string = "\u2318" на голанге. Вы можете проверить, что строка содержит единственный символ ⌘, а базовый массив байтов - 11101100 10001100 10011000, что совпадает с кодировкой ⌘ UTF-8.

Java

Исходный код Java должен быть написан символами Unicode. Но язык не требует конкретной кодировки. Когда вы компилируете исходный код в классы, вы можете указать необязательный аргумент -encoding для javac, если вам нужно что-то другое, кроме системного по умолчанию.

Объекты Java String всегда представлены в UTF-16 в внутренней памяти. Вы можете создать объект String, используя байты различных схем кодирования. Вы также можете получить байты из объекта String в различных схемах кодирования. См. Следующий фрагмент в качестве иллюстрации.

// Java also supports escape Unicode points.
// Can use "\u2318" as well.
String str = "⌘";
// String.getBytes() uses the system default encoding,
// which is usually UTF_8.
// It prints out 0xE28C98, which is
// 11101100 10001100 10011000.
for (byte b : str.getBytes()) {
  System.out.printf("%x", b);
}
// String(bytes), again, uses the system default encoding.
String str1 = new String(str.getBytes());
// String.getBytes(Charset) returns bytes
// encoded with the given Charset.
// Using UTF_16BE instead of plain UTF_16
// to specify the endianness. Otherwise the returned
// bytes contain the byte order mark.
// It prints out 0x2318, which is 00100011 00011000.
for (byte b : str.getBytes(StandardCharsets.UTF_16BE)) {
  System.out.printf("%x", b);
}
// String(bytes, Charset) uses the given Charset
// to interpret the input bytes.
String str2 = new String(
    str.getBytes(StandardCharsets.UTF_16BE),
    StandardCharsets.UTF_16BE
);
// All the same.
if (str.equals(str1) && str.equals(str2)) {
  System.out.println("All the same");
}

C++

Подобно Java, кодировка символов исходного кода в C ++ имеет различные варианты, а значение по умолчанию определяется реализацией - обычно UTF-8. В отличие от Java, где строковые литералы всегда кодируются как UTF-16, C ++ имеет концепцию кодировки символов выполнения. Это также определяется реализацией. Компилятор C ++ переводит строковые либералы из кодировки символов исходного кода в кодировку символов выполнения. Поэтому, когда вы пишете const char[] str = "hello world";, строковый литерал "hello world" во время выполнения кодируется в кодировке символов выполнения. Вы также можете исправить кодировку строкового литерала времени выполнения на UTF-8 независимо от реализации по умолчанию, добавив перед строковым литералом u8, например const char[] str = u8"hello word";. Вы можете добавить еще несколько префиксов: L, u, U. Соответствующие им вариации типа char - wchar_t, char16_t и char32_t. Соответствующие схемы кодирования - это кодировка, определяемая реализацией, UTF-16 и UTF-32. Подобно Golang, std::string в C ++ - это просто оболочка вокруг байтового массива. Его совершенно не волнует кодировка.

Кодировка строк в инструментах

Для полноты картины давайте также кратко обсудим кодировку строк в инструментах, которые вы будете использовать в повседневной работе. Все современные IDE позволяют настраивать кодировку файла исходного кода. Например, в VS Code это можно изменить в нижней панели (ссылка). В Intellij вы можете настроить это аналогичным образом (ссылка). Как вы могли догадаться, по умолчанию для обоих используется UTF-8. В большинстве браузеров выбор кодировки / декодирования символов представляет собой комбинацию проверки тега <meta> в <header>, по умолчанию используется UTF-8, и некоторого отката к другим схемам.

Эпилог

Это конец этого небольшого сообщения в блоге. Я надеюсь, что теперь вы чувствуете себя более уверенно в кодировке строк. Простая стратегия в собеседовании по проектированию систем: придерживайтесь Unicode и просто признайтесь, что вы мало знаете о других схемах кодирования, когда вас спросят. Это должно, по крайней мере, помочь вам преодолеть препятствия при кодировании строк, чтобы вы могли перейти к другим интересным обсуждениям дизайна в интервью. Если вы хотите видеть больше сообщений в блоге с интервью по системному дизайну, ознакомьтесь с этим списком.