Метод Кукушки

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

Принципы метода кукушки

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

Основные шаги метода кукушки

1. Инициализация: Создаются две хеш-таблицы и две хеш-функции.
2. Вставка:
   • Вычисляются два возможных места для нового элемента с помощью двух хеш-функций.
   • Если одно из мест свободно, элемент помещается туда.
   • Если оба места заняты, один из существующих элементов вытесняется и перемещается в своё альтернативное место. Этот процесс повторяется рекурсивно.
3. Поиск:
   • Для элемента вычисляются два возможных места.
   • Если элемент находится в одном из них, он возвращается. Если нет, возвращается значение “не найдено”.
4. Удаление:
   • Для элемента вычисляются два возможных места.
   • Если элемент находится в одном из них, он удаляется. Если нет, возвращается значение “элемент отсутствует”.

Пример реализации на C++

Ниже приведен пример реализации метода кукушки на языке C++:

#include <iostream>
#include <vector>
#include <cstdlib> // Для функции rand
 
class CuckooHashTable {
private:
    std::vector<int> table1, table2;
    int size;
    const int MAX_ITERATIONS = 50;
 
    int hash1(int key) {
        return key % size;
    }
 
    int hash2(int key) {
        return (key / size) % size;
    }
 
    void rehash() {
        std::vector<int> oldTable1 = table1;
        std::vector<int> oldTable2 = table2;
        table1.clear();
        table2.clear();
        table1.resize(size, -1);
        table2.resize(size, -1);
        
        for (int key : oldTable1) {
            if (key != -1) {
                insert(key);
            }
        }
        for (int key : oldTable2) {
            if (key != -1) {
                insert(key);
            }
        }
    }
 
public:
    CuckooHashTable(int size) : size(size) {
        table1.resize(size, -1);
        table2.resize(size, -1);
    }
 
    void insert(int key) {
        int currentKey = key;
        int table = 1;
        for (int i = 0; i < MAX_ITERATIONS; ++i) {
            if (table == 1) {
                int pos = hash1(currentKey);
                if (table1[pos] == -1) {
                    table1[pos] = currentKey;
                    return;
                } else {
                    std::swap(currentKey, table1[pos]);
                    table = 2;
                }
            } else {
                int pos = hash2(currentKey);
                if (table2[pos] == -1) {
                    table2[pos] = currentKey;
                    return;
                } else {
                    std::swap(currentKey, table2[pos]);
                    table = 1;
                }
            }
        }
        rehash();
        insert(currentKey);
    }
 
    bool search(int key) {
        int pos1 = hash1(key);
        if (table1[pos1] == key) {
            return true;
        }
        int pos2 = hash2(key);
        if (table2[pos2] == key) {
            return true;
        }
        return false;
    }
 
    void remove(int key) {
        int pos1 = hash1(key);
        if (table1[pos1] == key) {
            table1[pos1] = -1;
            return;
        }
        int pos2 = hash2(key);
        if (table2[pos2] == key) {
            table2[pos2] = -1;
            return;
        }
    }
 
    void print() {
        std::cout << "Table 1: ";
        for (int key : table1) {
            if (key != -1) {
                std::cout << key << " ";
            } else {
                std::cout << "- ";
            }
        }
        std::cout << "\nTable 2: ";
        for (int key : table2) {
            if (key != -1) {
                std::cout << key << " ";
            } else {
                std::cout << "- ";
            }
        }
        std::cout << std::endl;
    }
};
 
int main() {
    CuckooHashTable hashTable(11);
 
    hashTable.insert(10);
    hashTable.insert(20);
    hashTable.insert(30);
    hashTable.insert(40);
    hashTable.insert(50);
    hashTable.insert(60);
 
    hashTable.print();
 
    std::cout << "Search 30: " << (hashTable.search(30) ? "Found" : "Not found") << std::endl;
    std::cout << "Search 70: " << (hashTable.search(70) ? "Found" : "Not found") << std::endl;
 
    hashTable.remove(30);
    hashTable.print();
    std::cout << "Search 30: " << (hashTable.search(30) ? "Found" : "Not found") << std::endl;
 
    return 0;
}

Преимущества метода кукушки

1. Постоянное время операций: Операции вставки, поиска и удаления выполняются за O(1) в среднем случае.
2. Простота: Алгоритм относительно прост в реализации и понимании.
3. Отсутствие цепочек: В отличие от метода цепочек, метод кукушки не использует списков, что упрощает управление памятью.

Недостатки метода кукушки

1. Рехеширование: В случае многократных коллизий алгоритм может потребовать рехеширования, что временно увеличивает затраты на вставку.
2. Потребление памяти: Метод требует две или более таблицы, что увеличивает потребление памяти по сравнению с методами, использующими одну таблицу.

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