Как разрешаются коллизии ключей?

Разрешение коллизий ключей в хэш-таблицах

Коллизии ключей — это ситуация, когда разные ключи имеют одинаковый хэш-код и претендуют на одну ячейку в хэш-таблице. В Go, как и в большинстве языков, используются два основных подхода: метод цепочек (chaining) и открытая адресация (open addressing). В стандартной реализации map в Go используется второй вариант с конкретной разновидностью — линейное пробирование (linear probing).

Основные методы разрешения коллизий

1. Метод цепочек (Chaining)

Каждая ячейка таблицы содержит не одно значение, а связный список (или другую структуру) пар ключ-значение. При коллизии новый элемент добавляется в список.

// Упрощенная иллюстрация (не реальная реализация Go)
type Entry struct {
    key   string
    value interface{}
    next  *Entry
}

type Bucket struct {
    head *Entry
}

// При коллизии добавляем в цепочку
func (b *Bucket) insert(key string, value interface{}) {
    newEntry := &Entry{key: key, value: value, next: b.head}
    b.head = newEntry
}

Преимущества:

• Простота реализации
• Таблица никогда не заполняется полностью
• Устойчивость к плохим хэш-функциям

Недостатки:

• Дополнительные расходы памяти на указатели
• Локализация данных хуже, что влияет на кэш-процессора

2. Открытая адресация (Open Addressing)

Все элементы хранятся непосредственно в массиве таблицы. При коллизии алгоритм ищет следующую свободную ячейку по определенному алгоритму пробирования.

Реализация в Go

В Go используется открытая адресация с линейным пробированием. Вот ключевые особенности:

// Упрощенное представление структуры map (из runtime/map.go)
type hmap struct {
    count     int    // количество элементов
    flags     uint8
    B         uint8  // log_2 от количества бакетов
    noverflow uint16 // приблизительное количество переполненных бакетов
    hash0     uint32 // seed для хэш-функции
    
    buckets    unsafe.Pointer // массив бакетов
    oldbuckets unsafe.Pointer // предыдущий массив при росте
    nevacuate  uintptr        // счетчик прогресса эвакуации
}

// Бакет содержит 8 ячеек
type bmap struct {
    tophash [bucketCnt]uint8 // первые 8 бит хэша для каждой ячейки
    // Далее следуют ключи и значения в отдельных массивах
    // keys [bucketCnt]keyType
    // values [bucketCnt]valueType
    // overflow указатель на следующий бакет при переполнении
}

Алгоритм работы при коллизии:

1. Вычисляется хэш ключа и определяется начальный бакет
2. Проверяются 8 ячеек в бакете по tophash (первые 8 бит хэша)
3. Если все ячейки заняты, используется линейное пробирование — проверяются следующие бакеты
4. При переполнении создается overflow bucket (связный список бакетов)

// Псевдокод поиска с разрешением коллизий
func mapaccess(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    hash := hash(key, h.hash0)
    bucketIndex := hash & (1<<h.B - 1)
    
    // Поиск в основном бакете
    b := (*bmap)(add(h.buckets, bucketIndex*uintptr(t.bucketsize)))
    
    for ; b != nil; b = b.overflow(t) {
        for i := 0; i < bucketCnt; i++ {
            if b.tophash[i] == topHash {
                // Проверка полного совпадения ключа
                k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                if alg.equal(key, k) {
                    v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                    return v
                }
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}

Особенности реализации в Go

Двойное хэширование: Go использует два разных хэша для каждого ключа — один для определения бакета, другой для tophash (быстрая предварительная проверка).

Инкрементальное перехеширование: При росте таблицы (когда count > 6.5 * 2^B) данные постепенно переносятся в новую таблицу вдвое большего размера. Это позволяет избежать задержек при операциях.

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

Управление памятью: Overflow бакеты создаются по мере необходимости и связываются в список, что сочетает преимущества открытой адресации и цепочек.

Производительность и практические следствия

• Средняя сложность операций остается O(1), но в худшем случае (много коллизий) может деградировать до O(n)
• Качество хэш-функции критически важно — в Go используются быстрые и хорошо распределяющие хэш-функции
• Размер таблицы всегда является степенью двойки, что позволяет использовать битовые операции вместо деления
• Удаление элементов реализовано через специальный маркер в tophash, чтобы не прерывать цепочки пробирования

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