Как устроено хранение key-value пар в Go `map`?

В Go основной структурой для хранения key-value пар является map. Она реализована как хэш-таблица, что обеспечивает в среднем очень быстрый доступ к элементам (O(1)).

Принципы хранения:

1. Хэширование ключей: Каждый ключ передается через внутреннюю хэш-функцию, которая генерирует числовой хэш. Этот хэш используется для определения, в каком "бакете" (внутренней структуре хэш-таблицы) будет храниться пара ключ-значение.
2. Обработка коллизий: Разные ключи могут давать одинаковый хэш (коллизии). Go map использует методы для разрешения коллизий (например, цепочки), чтобы все пары были доступны, даже если их хэши совпадают.
3. Неупорядоченность: В отличие от некоторых других языков, порядок итерации элементов в Go map не гарантирован и является случайным (начиная с Go 1.12). Это сделано для предотвращения написания кода, который случайно полагается на определенный порядок итерации, что может привести к ошибкам при изменении реализации map.
4. Уникальность ключей: Каждый ключ в map должен быть уникальным. При попытке добавить пару с уже существующим ключом, старое значение будет перезаписано новым.
5. Динамический размер: map автоматически расширяется (перехешируется) по мере добавления элементов, когда количество элементов достигает определенного порога, чтобы поддерживать эффективную производительность.

Особенности использования map в Go:

• Ключи должны быть сравниваемыми: Типы, используемые в качестве ключей (int, string, bool, указатели, каналы, массивы и структуры, все поля которых сравниваемы), должны поддерживать операторы == и !=.
• Доступ и проверка существования: Для безопасного доступа используйте идиому value, ok := myMap[key], чтобы проверить, существует ли ключ, и отличить отсутствие ключа от значения по умолчанию (zero-value) для данного типа.

Пример:

package main

import "fmt"

func main() {
    // Создание map
    data := make(map[string]int)

    // Добавление элементов
    data["apple"] = 5
    data["banana"] = 3
    data["orange"] = 7

    // Доступ к элементу
    count := data["apple"]
    fmt.Println("Count of apple:", count) // Output: Count of apple: 5

    // Проверка существования ключа
    val, ok := data["pear"]
    if ok {
        fmt.Println("Count of pear:", val)
    } else {
        fmt.Println("Pear not found.") // Output: Pear not found.
    }

    // Итерация (порядок не гарантирован)
    fmt.Println("All items:")
    for key, value := range data {
        fmt.Printf("  %s: %dn", key, value)
    }
}