lesson3

4.3 Хеш-таблица

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

В Go map представляет собой ссылку на хеш-таблицу, а тип отображения записывается как map[K]V, где K и V являются типами его ключей и значений. Все ключи в данной map имеют один и тот же тип, как и все значения имеют один и тот же тип, но тип ключей не обязан совпадать с типом значений. Тип ключа должен быть сравниваемым с помощью оператора ==, чтобы map мог проверить, равен ли данный ключ одному из имеющихся в нем.

Числа с плавающей точкой являются сравниваемыми, сравнивать их на равенство - плохая идея, и это особенно плохая идея, если NaN является возможным значением. На тип значения V никаких ограничений нет.

Встроенная функция make может использоваться для создания map:

ages := make(map[string]int)

Map c литералами:

ages := map[string]int{
    "alice": 31,
    "charlie": 34,
}

Эта запись эквивалентна следующей:

ages := make(map[string]int)
ages["alice"] = 31
ages["charlie"] = 34

Альтернативное выражение для создания новой пустой map:

map[string]int{}

Удаление осуществляется с помощью встроенной функции delete:

delete(ages, "alice") // Удаление элемента ages["alice"]

Все эти операции безопасны, даже если элемент отсутствует в map. При использовании ключа, которого нет, поиск возвращает нулевое значение соответствующего типа. Так что след. инструкция работает, даже когда ключа bob нет, поскольку значение ages["bob"] в этом случае будет равно 0:

ages["bob"] = ages["bob"] + 1 

Можно записывать с помощью сокращенных записей += -= ++ --:

ages["bob"] += 1
ages["bob"]++

Однако, элементы map не являются переменными, и мы не можем получить их адреса:

_ = &ages["bob"] // Ошибка: невозможно получить адрес map

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

Для перечисления всех пар ключ-значение используются циклы по диапазону:

for name, age := range ages {
    fmt.Printf("%s\t%d\n", name, age)
}

Порядок итераций по map не определен, различные реализации могут использовать разные хеш-функции, что приведет к иному порядку. На практике получается случайный порядок, который варьируется от одного запуска программы к другому. Это сделано преднамеренно, варьируемые последовательности помогают писать программы, которые одинаково надежны в разных реализациях языка. Для перечисления пар ключ-значение в определенном порядке требуется явная сортировка ключей, например, с помощью функции Strings из пакета sort, если ключи являются строками. Общий шаблон выглядит так:

import "sort"

var names []string
for name := ages {
    names = append(names, name)
}
sort.Strings(names)
for _, name := range names {
    fmt.Printf("%s\t%d\n", name, ages[name])
}

Так как мы знаем окончательный размер names с самого начала, более эффективным решением будет сразу выделить массив нужного размера. Приведенная далее инструкция создает срез, который изначально пуст, но обладает достаточной емкостью для хранения всех ключей из map ages:

names := make([]string, 0, len(ages))

Нулевым значением для типа map является nil:

var ages map[string]int
fmt.Println(ages == nil) // true
fmt.Println(len(ages) == 0) // true

Большинство операций над map, включая поиск, удаление (delete), получение длины (len) и цикл по диапазону (range), безопасно выполняются с нулевым map, поскольку он ведет себя так же, как пустой map. Однако сохранение значений в нулевом map приводит к panic:

ages["carol"] = 21 // panic: присваивание элементу нулевого map

Перед тем, как выполнять присваивание, следует выделить память для map.

Доступ к элементу map с помощью индексации всегда дает значение. Если ключ присутствует в map, мы получаем соответствующее значение. Если нет - мы получим нулевое значение типа элемента. Для многих целей это вполне нормально, но иногда нужно знать, есть ли некоторый элемент в map. Например, если типом элемента является число, то отличить несуществующий элемент от элемента, который имеет нулевое значение, можно с помощью следующего теста:

age, ok := ages["bob"]
if !ok {
    // ...   "bob" не является ключом в данном map, age == 0
}

Зачастую две такие конструкции объединяются:

if age, ok := ages["bob"]; !ok { /*...*/ }

Индексация map в этом контексте дает два значения. Второе значение - логическое, показывающее, имеется ли данный элемент в map. Этой логической переменной часто дают имя ok, особенно если она сразу же используется в условии инструкции if.

Как и срезы, map нельзя сравнивать друг с другом. Единственное сравнение, которое разрешено является сравнение с nil.

Чтобы проверить, содержат ли два map одни и те же ключи и связанные с ними значения, нужно написать цикл:

func equal(x, y map[string]int) bool {
    if len(x) != len(y) {
        return false
    }
    for k, xv := range x {
        if yv, ok := y[k]; !ok || yv != xv {
            return false
        }
    }
    return true
}

!ok используется так, чтобы отличить случаи отсутсвует и присутствует, но равен нулю. Если написать xv != y[k], то показанный ниже вызов сообщил бы, что аргументы равны, хотя это не так:

// Истинно при некорректном написании функции
equal(map[string]int{"A": 0}, map[string]int{"B": 42})

В Go нет set, но так как все ключи map различны, map может служить и для этой цели. Для иллюстрации программа (см. dedup.go), считывает последовательность строк и выводит только первое вхождение каждой из различных строк. Она использует map, ключи представляют множество строк, которые уже встречались, и с его помощью обеспечивается отсутствие в выводе дубликатов строк.

Программисты Go часто описывают map, используемое таким образом, как "множество строк", но нужно быть осторожным: не все значения map[string]bool являются просто множествами - некоторые из них могут содержать значения true и false.

Иногда необходим map или set (множество map[string]bool), ключи которого являются срезами, но поскольку ключи map должны быть сравниваемыми, такой map не может быть выражен непосредственно. Однако это можно сделать в два этапа. Сначала нужно определить вспомогательную функцию k, которая отображает каждый ключ на строку, с тем свойством, что k(x) == k(y), тогда и только тогда, когда x и y считаются равными. Затем нужно создать map, ключи которого являются строками, применяя вспомогательную функцию к каждому ключу перед обращением к map.

В приведенном ниже примере map используется для записи количества вызовов Add с данным списком строк. Пример использует функцию fmt.Sprintf для преобразования среза строк с помощью символов преобразования %q в одну строку, которая является подходящим ключом map:

var m = make(map[string]int)

func k(list []string) string { return fmt.Sprintf("%q", list) }

func Add(list []string) string { return m[k(list)]++ }

func Count(list []string) int {return m[k(list)]}

Такой же подход может использоваться для любого не сравниваемого типа ключей, не только для срезов. Иногда этот подход полезен даже для ключей сравниваемых типов, когда требуется определение равенства, отличное от ==, например сравнение без учета регистра для строк. Тип k(x) так же не обязан быть строкой, подойдут любые сравниваемые типы с необходимым свойством эквивалентности, такие как целые числа, массивы или структуры.

Еще один пример map в действии (см. charcount.go): программа, которая подсчитывает количество вхождений каждого различного символа unicode в его входных данных. Поскольку имеется большое количество всевозможных символов, только небольшая часть которых будет встречаться в любом конкретном документе, map является естественным способом отслеживать только те из них, которые встречаются в документе.

Метод ReadRune выполняет декодирование UTF-8 и возвращает три значения:

• декодированную руну
• длину ее UTF-8 кода в байтах
• значение ошибки

Единственная ошибка, которую мы ожидаем - это достижение конца файла. Если ввод не является корректным UTF-8 кодом руны, возвращается руна unicode.ReplacementChar и длина 1.

Тип значения map сам может быть составным типом, таким как map или срез. В приведенном ниже коде (см. graph.go), типом ключа graph является string, а типом значения map[string]bool, представляющим множество строк. Концептуально graph отображает строку на множество связанных с ней строк, ее преемников в ориентированном графе.

Функция addEdge демонстрирует идиоматический способ отложенного заполнения map, при котором инициализация каждого значения выполняется, когда его ключ встречается в первый раз. Функция hasEdge показывает, как работает нулевое значение отсутствующей записи map: даже если в наличии нет ни from ни to, graph[from][to] всегда дает значимый результат.

Выводы:

• Хеш-таблица (map) в Go представляет собой неупорядоченную коллекцию пар ключ-значение, где все ключи уникальны и значения могут быть найдены, обновлены или удалены с использованием в среднем константного количества сравнений ключей (O(1));
• Тип карты записывается как map[K]V, где K и V являются типами ключей и значений соответственно;
• Для создания map используется встроенная функция make, например: ages := make(map[string]int);
• Map можно создать с использованием литералов: ages := map[string]int{"alice": 31, "charlie": 34};
• Для удаления элемента из map используется встроенная функция delete: delete(ages, "alice");
• Итерация по элементам map варьируется от одного запуска программы к другому, для определенного порядка итерации нужно явно сортировать ключи;
• Нулевым значением для типа map является nil, большинство операций с ним выполняются безопасно, но сохранение значений в нулевом map вызовет panic;
• Для проверки наличия элемента в map, можно использовать двойное значение переменной, например: age, ok := ages["bob"];
• Map нельзя сравнивать друг с другом, единственное разрешенное сравнение - сравнение с nil ;
• Так как все ключи map различны, map может служить в качестве множества (set);
• Ключи в map должны быть сравниваемыми, поэтому ключами срезы не могут быть напрямую; однако можно использовать вспомогательную функцию для преобразования срезов в строки, сохраняющих условия равенства исходных срезов;
• Использование вспомогательной функции для преобразования ключей позволяет применять подходы с использованием map[string]bool для любых несравниваемых типов ключей, а также для сравниваемых типов ключей, требующих особого определения равенства, например, сравнение без учета регистра для строк;
• Использование map для подсчета количества вхождений различных символов Unicode позволяет легко и эффективно решать задачи в документах с разными наборами символов, поскольку отслеживаются только встречающиеся символы;
• Встроенный метод ReadRune из пакета bufio позволяет декодировать символы Unicode в тексте, обрабатывая корректные и некорректные UTF-8 коды;
• Вложенные составные типы в значении map, такие как map или срезы, позволяют создавать гибкую и полезную структуру данных для организации и сохранения связей между строками (map[string][]string{}).