Ответ
Коллизия в хеш-таблице возникает, когда разные ключи дают одинаковый индекс (хеш). Существует два основных подхода к их разрешению.
1. Метод цепочек (Separate Chaining) Идея: Каждая ячейка массива (bucket) содержит связный список (или другую структуру) всех элементов, попавших в неё.
class HashTable<Key: Hashable, Value> {
private typealias Element = (key: Key, value: Value)
private typealias Bucket = [Element]
private var buckets: [Bucket]
init(capacity: Int) {
buckets = Array(repeating: [], count: capacity)
}
private func index(for key: Key) -> Int {
return abs(key.hashValue) % buckets.count
}
func insert(_ value: Value, for key: Key) {
let index = self.index(for: key)
// Ищем, есть ли уже такой ключ в цепочке
if let existingIndex = buckets[index].firstIndex(where: { $0.key == key }) {
buckets[index][existingIndex].value = value // Обновление
} else {
buckets[index].append((key: key, value: value)) // Добавление в конец списка
}
}
}Плюсы: Простая реализация, эффективна при высокой нагрузке. Минусы: Дополнительные затраты памяти на хранение указателей списка.
2. Открытая адресация (Open Addressing) Идея: Все элементы хранятся непосредственно в массиве. При коллизии алгоритм ищет следующую свободную ячейку по определённой последовательности (probing sequence).
- Линейное пробирование:
newIndex = (hash + i) % capacity, гдеi— номер попытки.- Проблема: Образование кластеров (первичная кластеризация).
- Квадратичное пробирование:
newIndex = (hash + i²) % capacity.- Уменьшает кластеризацию, но может не найти свободную ячейку даже при их наличии.
- Двойное хеширование:
newIndex = (hash1 + i * hash2(key)) % capacity.- Использует вторую хеш-функцию для шага. Наиболее эффективный метод, минимизирует кластеризацию.
| Сравнение: | Метод | Сложность в худшем случае | Память | Эффективность при высокой нагрузке |
|---|---|---|---|---|
| Цепочки | O(n) для списка | Выше (указатели) | Лучше | |
| Открытая адресация | O(n) при поиске | Ниже (только массив) | Сильно падает при заполнении >70% |
Ответ 18+ 🔞
А, ну это про коллизии в хеш-таблицах, да? Ну, блядь, классика жанра, как два мужика в одну кабинку в сортире пытаются зайти — индексы одинаковые, а ключи разные, ёпта! Вот и получается конфуз.
Так, слушай сюда, их всего два основных подхода, как эту поебень разрешить. Не выдумывай велосипед, всё уже придумали до нас, блядь.
Первый способ — метод цепочек, он же Separate Chaining. Суть в чём: Представь, что каждая ячейка в массиве — это ведро, блядь. И если в это ведро уже кто-то пописал (ключ с таким же хешом), то мы не выливаем его, а ставим рядом ещё одно ведёрко и связываем их верёвочкой. То есть в ячейке лежит не один элемент, а целый связный список (или дерево, если совсем охуевшие).
class HashTable<Key: Hashable, Value> {
private typealias Element = (key: Key, value: Value)
private typealias Bucket = [Element]
private var buckets: [Bucket]
init(capacity: Int) {
buckets = Array(repeating: [], count: capacity)
}
private func index(for key: Key) -> Int {
return abs(key.hashValue) % buckets.count
}
func insert(_ value: Value, for key: Key) {
let index = self.index(for: key)
// Ищем, есть ли уже такой ключ в цепочке
if let existingIndex = buckets[index].firstIndex(where: { $0.key == key }) {
buckets[index][existingIndex].value = value // Обновление
} else {
buckets[index].append((key: key, value: value)) // Добавление в конец списка
}
}
}Чем хорош: Проще говна в стакане, реализуется за пять минут. И когда таблица забита под завязку, он не так сильно проседает по скорости, как его конкурент. Чем плох: Памяти жрёт, как не в себя, эти все указатели на списки — они же тоже место занимают, блядь!
Второй способ — открытая адресация, она же Open Addressing. Суть в чём: Тут у нас принцип "в тесноте, да не в обиде". Все элементы пихаются прямо в массив. Если ячейка занята — пошёл нахуй, иди ищи себе другую свободную квартирку по определённому маршруту (probing sequence).
- Линейное пробирование: Новый индекс = (старый хеш + i) % размер. Где i — номер попытки, как очередь в столовой.
- Пиздец какой: Образуются здоровенные кластеры — пробки из занятых ячеек. Это как на парковке: один припарковался криво, и все остальные вынуждены ехать дальше, блядь.
- Квадратичное пробирование: Новый индекс = (старый хеш + i²) % размер.
- Кластеры поменьше, но есть другая засада — можно проехать мимо свободной ячейки и так её и не найти, даже если она есть, ёпта! Алгоритм, блядь, тупой.
- Двойное хеширование — король и бог! Новый индекс = (первый хеш + i * второй хеш(ключ)) % размер.
- Тут уже используется вторая, независимая хеш-функция для шага. Кластеризация минимальна, работает, как швейцарские часы. Самый ахуенный метод, если, конечно, не полениться вторую функцию написать.
Ну и итоговая табличка, чтобы не путаться, блядь:
| Метод | Сложность в худшем случае | Память | Эффективность при высокой нагрузке |
|---|---|---|---|
| Цепочки | O(n) для списка | Выше (указатели) | Лучше |
| Открытая адресация | O(n) при поиске | Ниже (только массив) | Сильно падает при заполнении >70% |
Короче, выбирай: либо память тратить, но жить спокойно (цепочки), либо экономить память, но потом охуевать от поиска, когда таблица заполнится (открытая адресация). Волшебства не бывает, блядь.