Что такое хэш-таблица?

Хеш-таблица (или ассоциативный массив, словарь) — это структура данных, которая хранит пары "ключ-значение" (key-value) и позволяет быстро находить, вставлять и удалять элементы по их ключу.

В Golang хеш-таблица реализована как тип map.

Принцип работы:

1. Хеширование ключа: Для каждого ключа вычисляется хеш-значение с помощью хеш-функции. Хеш-функция преобразует ключ любого размера в число фиксированного размера.
2. Определение индекса: На основе хеш-значения определяется индекс в массиве (корзине или бакетов), где будет храниться пара "ключ-значение". Обычно используется операция по модулю от размера массива.
3. Коллизии: Поскольку разные ключи могут давать одно и то же хеш-значение (или определять один и тот же индекс), возникает коллизия. Для разрешения коллизий применяются различные методы, например:
   • Метод цепочек (Separate Chaining): В каждом бакете хранится список пар "ключ-значение", которые имеют одинаковый индекс.
   • Метод открытой адресации (Open Addressing): При коллизии ищут свободный слот в массиве, используя разные стратегии (линейное зондирование, квадратичное зондирование и т.д.). Golang использует комбинацию этих подходов.

Преимущества хеш-таблиц:

• Высокая скорость доступа: В среднем, операции вставки, удаления и поиска имеют сложность O(1).
• Гибкость: Могут хранить ключи и значения различных типов данных.

Недостатки:

• Возможность коллизий: Производительность может ухудшиться при большом количестве коллизий.
• Зависимость от хеш-функции: Качество хеш-функции напрямую влияет на производительность.
• Потребление памяти: Обычно требуют больше памяти по сравнению с массивами или связными списками.

Пример создания и использования map в Golang:

package main

import "fmt"

func main() {
	// Создание мапы со строковыми ключами и целочисленными значениями
	ages := make(map[string]int)

	// Добавление элементов
	ages["Alice"] = 30
	ages["Bob"] = 25
	ages["Charlie"] = 35

	// Получение значения по ключу
	aliceAge := ages["Alice"]
	fmt.Println("Возраст Alice:", aliceAge)

	// Проверка наличия ключа
	_, exists := ages["David"]
	if !exists {
		fmt.Println("David не найден")
	}

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

	// Итерация по мапе (порядок не гарантируется)
	for name, age := range ages {
		fmt.Printf("%s: %d\n", name, age)
	}
}