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

1. Открытая адресация (open addressing): при коллизии ищется альтернативная свободная позиция в таблице с помощью различных стратегий:

   • Линейное исследование (linear probing): последовательное исследование ячеек с постоянным шагом.

   // Пример линейного исследования
   func (ht *HashTable) get(key int) (int, bool) {
       index := ht.hash(key)
       for i := 0; i < ht.size; i++ {
           probeIndex := (index + i) % ht.size
           if ht.table[probeIndex].key == key && ht.table[probeIndex].occupied {
               return ht.table[probeIndex].value, true
           }
           if !ht.table[probeIndex].occupied && ht.table[probeIndex].value == 0 /* предполагаем, что 0 означает пустоту */ {
               return 0, false // Не найдено
           }
       }
       return 0, false // Таблица заполнена
   }
   

   • Квадратичное исследование (quadratic probing): исследование ячеек с возрастающим квадратичным шагом ($i^2$).
   • Двойное хеширование (double hashing): использование второй хеш-функции для определения шага исследования.

2. Метод цепочек (separate chaining): каждая ячейка таблицы хеширования содержит указатель на связный список (или другую структуру данных), в который добавляются элементы с одинаковым хешем.

type Node struct {
	key   int
	value int
	next  *Node
}

type HashTableChain struct {
	table []*Node
	size  int
}

func (ht *HashTableChain) get(key int) (int, bool) {
	index := ht.hash(key)
	currentNode := ht.table[index]
	for currentNode != nil {
		if currentNode.key == key {
			return currentNode.value, true
		}
		currentNode = currentNode.next
	}
	return 0, false
}

3. Хеширование Кукушки (Cuckoo hashing): использование двух или более хеш-функций. При вставке элемента он помещается в первую свободную ячейку, определенную одной из хеш-функций. Если обе ячейки заняты, один из существующих элементов "выталкивается" в альтернативное место, определенное его второй хеш-функцией.

Сравнение методов: