Map

Хэш функция, требования:

1. детерминированность. Хэш от одного и того же значения должен быть одинаковым
2. равномерное распределение по таблице, мало коллизий
3. быстрота операции хэширования

Хэш таблица

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

Map

структура в go, которая позволяет все операции выполнить за константное время - O(1). Вставки, удаления, получения значения по ключу.

Структура map состоит из:

• размер map
• log2 числа бакетов
• ссылка на бакеты
• hash seed

Как работает операция получения значения по ключу:

1. из ключа получаем его хэш
2. из хэша получаем LOB (low order bytes). из LOB получаем адрес нужного бакета
3. в бакете получаем из хэша получаем HOB (high order bytes). из hob получаем адрес ключа, а потом адрес значения. Если не найдено, возвращаем zero value.
4. при переполнении бакетов в бакете хранится ссылка на следующий бакет. поэтому если такая ссылка есть и HOB не найден, то идем в следующий бакет

Особенности Map:

1. осознанный рандомный обходы map в цикле
2. в каждом бакете 8 пар ключей и значений, сначала идут все ключи, потом все значения. В бакетах хранятся коллизии
3. при среднем значении заполненности бакетов в 6.5 происходит эвакуация бакетов. Бакетов становится в 2 раза больше
4. эвакуация бакетов постепенная при каждой вставке или удалении, поэтому операции чуть медленнее, но нет большой задержки в определенное время
5. из-за эвакуации бакетов нельзя брать ссылку на значение мапы, потому что после эвакуации эта ссылка будет неактуальна
6. также из-за эвакуации эффективнее выделять память заранее, если есть информация о количестве элементов