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

Как возникают коллизии?

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

Представим, что у нас есть простая хэш-функция для строк, которая возвращает длину строки в качестве хэш-значения. Для строк "cat" и "dog" хэш-значение будет одинаковым (3), что приводит к коллизии.

Управление коллизиями

Существует несколько методов для управления хэш-коллизиями. Два наиболее распространенных метода — это цепочки (chaining) и открытая адресация (open addressing).

1. Цепочки (Chaining):

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

   ```go
   type Entry struct {
       key   string
       value int
       next  *Entry
   }

   type HashMap struct {
       buckets []*Entry
   }

   func (m *HashMap) Put(key string, value int) {
       index := hash(key) % len(m.buckets)
       entry := m.buckets[index]
       for entry != nil {
           if entry.key == key {
               entry.value = value
               return
           }
           entry = entry.next
       }
       m.buckets[index] = &Entry{key: key, value: value, next: m.buckets[index]}
   }

   func hash(key string) int {
       hash := 0
       for _, char := range key {
           hash += int(char)
       }
       return hash
   }
   ```

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

• В этом методе все элементы хранятся непосредственно в хэш-таблице. Если ячейка, определенная хэш-функцией, уже занята, используется альтернативная стратегия для нахождения следующей доступной ячейки.
• Наиболее распространенные стратегии включают линейное пробирование (linear probing), квадратичное пробирование (quadratic probing) и двойное хеширование (double hashing).

   ```go
   type HashMap struct {
       keys   []string
       values []int
       size   int
   }

   func (m *HashMap) Put(key string, value int) {
       index := hash(key) % len(m.keys)
       for m.keys[index] != "" {
           if m.keys[index] == key {
               m.values[index] = value
               return
           }
           index = (index + 1) % len(m.keys)
       }
       m.keys[index] = key
       m.values[index] = value
       m.size++
   }

   func hash(key string) int {
       hash := 0
       for _, char := range key {
           hash += int(char)
       }
       return hash
   }
   ```

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

June 2, 2024, easyoffer