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

Открытая адресация

Открытая адресация (Open Addressing) — метод разрешения коллизий, при котором все элементы хранятся непосредственно в хеш-таблице. Если возникает коллизия, элемент перемещается в другое место в таблице согласно определённому алгоритму.

Основные методы открытой адресации

Линейное пробегание (Linear Probing)

При линейном пробегании, если хешируемая ячейка занята, проверяется следующая ячейка (по модулю размера таблицы), и так далее, пока не будет найдена свободная ячейка.
```
int hashFunction(int key, int size) {
    return key % size;
}
 
int linearProbe(int hash, int i, int size) {
    return (hash + i) % size;
}
```
Квадратичное пробегание (Quadratic Probing)

При квадратичном пробегании используется квадратичная функция для определения следующей ячейки: $(ha s h + i^{2}) % s i ze$ . Это позволяет уменьшить кластеризацию по сравнению с линейным пробеганием.
```
int quadraticProbe(int hash, int i, int size) {
    return (hash + i * i) % size;
}
```
Двойное хеширование (Double Hashing)

При двойном хешировании используется вторая хеш-функция для определения шага пробегания: $(ha s h 1 + i \times ha s h 2) % s i ze$ .
```
int doubleHash(int hash1, int hash2, int i, int size) {
    return (hash1 + i * hash2) % size;
}
```

Пример реализации открытой адресации с линейным пробеганием

#include <iostream>
#include <vector>
#include <utility>
 
class HashTable {
private:
    std::vector<std::pair<int, std::string>> table;
    std::vector<bool> occupied;
    int size;
 
    int hashFunction(int key) {
        return key % size;
    }
 
public:
    HashTable(int size) : size(size) {
        table.resize(size, std::make_pair(-1, ""));
        occupied.resize(size, false);
    }
 
    void insert(int key, std::string value) {
        int hash = hashFunction(key);
        int i = 0;
        while (occupied[(hash + i) % size]) {
            i++;
        }
        table[(hash + i) % size] = std::make_pair(key, value);
        occupied[(hash + i) % size] = true;
    }
 
    std::string search(int key) {
        int hash = hashFunction(key);
        int i = 0;
        while (occupied[(hash + i) % size]) {
            if (table[(hash + i) % size].first == key) {
                return table[(hash + i) % size].second;
            }
            i++;
        }
        return "Not found";
    }
 
    void remove(int key) {
        int hash = hashFunction(key);
        int i = 0;
        while (occupied[(hash + i) % size]) {
            if (table[(hash + i) % size].first == key) {
                table[(hash + i) % size] = std::make_pair(-1, "");
                occupied[(hash + i) % size] = false;
                return;
            }
            i++;
        }
    }
};
 
int main() {
    HashTable hashTable(10);
 
    hashTable.insert(1, "Data1");
    hashTable.insert(2, "Data2");
    hashTable.insert(12, "Data12"); // Это вызовет коллизию с ключом 2
 
    std::cout << hashTable.search(1) << std::endl;
    std::cout << hashTable.search(12) << std::endl;
    std::cout << hashTable.search(2) << std::endl;
 
    hashTable.remove(12);
    std::cout << hashTable.search(12) << std::endl;
 
    return 0;
}

Закрытая адресация

Закрытая адресация (Closed Addressing), также известная как метод цепочек (Separate Chaining), предполагает, что каждый бакет хеш-таблицы содержит список (или другую структуру данных), в который помещаются все элементы, хешируемые в данный бакет.

Основные аспекты метода цепочек

Хеш-функция: Преобразует ключ в индекс бакета.
Бакет: Содержит список элементов с одинаковым хеш-значением.

Преимущества метода цепочек

Простота в реализации.
Отсутствие необходимости в рехешировании при заполнении таблицы.
Гибкость в управлении размером таблицы.

Недостатки метода цепочек

Дополнительное потребление памяти на хранение списков.
Увеличение времени поиска при длинных цепочках.

Пример реализации метода цепочек

#include <iostream>
#include <vector>
#include <list>
#include <utility> // Для std::pair
 
class HashTable {
private:
    std::vector<std::list<std::pair<int, std::string>>> table;
    int size;
 
    int hashFunction(int key) {
        return key % size;
    }
 
public:
    HashTable(int size) : size(size) {
        table.resize(size);
    }
 
    void insert(int key, std::string value) {
        int hash = hashFunction(key);
        table[hash].emplace_back(key, value);
    }
 
    std::string search(int key) {
        int hash = hashFunction(key);
        for (auto& pair : table[hash]) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        return "Not found";
    }
 
    void remove(int key) {
        int hash = hashFunction(key);
        auto& cell = table[hash];
        cell.remove_if([key](const std::pair<int, std::string>& item) { return item.first == key; });
    }
};
 
int main() {
    HashTable hashTable(10);
 
    hashTable.insert(1, "Data1");
    hashTable.insert(2, "Data2");
    hashTable.insert(12, "Data12"); // Это вызовет коллизию с ключом 2
 
    std::cout << hashTable.search(1) << std::endl;
    std::cout << hashTable.search(12) << std::endl;
    std::cout << hashTable.search(2) << std::endl;
 
    hashTable.remove(12);
    std::cout << hashTable.search(12) << std::endl;
 
    return 0;
}

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

Открытая адресация:

Элементы хранятся в самой хеш-таблице.
Подходит для использования в условиях с низкой или средней загрузкой таблицы.
Рехеширование может быть дорогим при заполнении таблицы.

Закрытая адресация:

Использует списки для хранения элементов с одинаковым хеш-значением.
Легко справляется с высокой загрузкой таблицы.
Требует дополнительных структур данных для хранения списков.

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

m4lvx

Explorer

Методы открытой и закрытой адресации