فاخته هشویی: یک تکنیک وضوح کارآمد برخورد با O (1) زمان جستجو

#include 
#include 
#include 
#include 

using namespace std;

#define TABLE_SIZE 11  // Initial hash table size
#define MAX_REHASH 10  // Maximum reinsertion attempts before rehashing

class CuckooHashTable {
private:
    vector table1, table2;
    vector occupied1, occupied2;

    int hash1(int key) { return key % TABLE_SIZE; }
    int hash2(int key) { return (key / TABLE_SIZE) % TABLE_SIZE; }

    void rehash() {
        cout << "Rehashing required!" << endl;
        vector oldTable1 = table1, oldTable2 = table2;
        vector oldOccupied1 = occupied1, oldOccupied2 = occupied2;

        int newSize = TABLE_SIZE * 2;
        table1.assign(newSize, -1);
        table2.assign(newSize, -1);
        occupied1.assign(newSize, false);
        occupied2.assign(newSize, false);

        for (int i = 0; i < oldTable1.size(); i++) {
            if (oldOccupied1[i]) insert(oldTable1[i]);
            if (oldOccupied2[i]) insert(oldTable2[i]);
        }
    }

public:
    CuckooHashTable() {
        table1.assign(TABLE_SIZE, -1);
        table2.assign(TABLE_SIZE, -1);
        occupied1.assign(TABLE_SIZE, false);
        occupied2.assign(TABLE_SIZE, false);
    }

    void insert(int key) {
        int pos1 = hash1(key);
        int pos2 = hash2(key);
        int loopCounter = 0;
        int currKey = key;

        while (loopCounter < MAX_REHASH) {
            if (!occupied1[pos1]) {
                table1[pos1] = currKey;
                occupied1[pos1] = true;
                return;
            }
            swap(currKey, table1[pos1]);

            if (!occupied2[pos2]) {
                table2[pos2] = currKey;
                occupied2[pos2] = true;
                return;
            }
            swap(currKey, table2[pos2]);

            pos1 = hash1(currKey);
            pos2 = hash2(currKey);
            loopCounter++;
        }

        rehash();
        insert(currKey);
    }

    bool search(int key) {
        return (occupied1[hash1(key)] && table1[hash1(key)] == key) ||
               (occupied2[hash2(key)] && table2[hash2(key)] == key);
    }

    void remove(int key) {
        if (occupied1[hash1(key)] && table1[hash1(key)] == key) {
            occupied1[hash1(key)] = false;
            table1[hash1(key)] = -1;
            return;
        }
        if (occupied2[hash2(key)] && table2[hash2(key)] == key) {
            occupied2[hash2(key)] = false;
            table2[hash2(key)] = -1;
            return;
        }
        cout << "Key not found!" << endl;
    }

    void display() {
        cout << "Table 1: ";
        for (int i = 0; i < TABLE_SIZE; i++)
            cout << (occupied1[i] ? to_string(table1[i]) : "-") << " ";
        cout << "\nTable 2: ";
        for (int i = 0; i < TABLE_SIZE; i++)
            cout << (occupied2[i] ? to_string(table2[i]) : "-") << " ";
        cout << "\n";
    }
};

int main() {
    CuckooHashTable hashTable;
    hashTable.insert(10);
    hashTable.insert(20);
    hashTable.insert(30);
    hashTable.insert(25);
    hashTable.insert(35);
    hashTable.insert(40);
    hashTable.insert(50);

    hashTable.display();

    cout << "Searching 25: " << (hashTable.search(25) ? "Found" : "Not Found") << endl;
    cout << "Searching 100: " << (hashTable.search(100) ? "Found" : "Not Found") << endl;

    hashTable.remove(30);
    hashTable.display();
    return 0;
}