#include <iostream>
#include <string>

using namespace std;

// Konstanten
const int TABLE_SIZE = 10; // Größe der Hash-Tabelle

// Struktur für einen Hash-Eintrag
struct HashEntry {
    string key;
    string value;
    bool isDeleted; // Flag to indicate if the entry is deleted
};

// Hash-Tabelle als Array von Hash-Einträgen
HashEntry table[TABLE_SIZE];

// Funktion zum Berechnen des Hash-Werts für eine Schlüssel-String
int hashFunction(string key) {
    int hash = 0;
    for (char c : key) {
        hash += c;
    }
    return hash % TABLE_SIZE;
}

// Quadratische Sondierung zum Finden des nächsten freien Index
int quadraticProbing(int hash, int i) {
    return (hash + i * i) % TABLE_SIZE;
}

// Funktion zum Schreiben eines Hash-Eintrags
void insert(string key, string value) {
    int index = hashFunction(key);
    int i = 0;
    while (table[quadraticProbing(index, i)].key != "" && !table[quadraticProbing(index, i)].isDeleted) { // Suche nach einem freien Platz
        i++;
        if (i == TABLE_SIZE) { // Tabelle ist voll
            cout << "Hash table is full, cannot insert " << key << endl;
            return;
        }
    }
    int finalIndex = quadraticProbing(index, i);
    table[finalIndex].key = key;
    table[finalIndex].value = value;
    table[finalIndex].isDeleted = false;
}

// Funktion zum Lesen eines Hash-Eintrags
string get(string key) {
    int index = hashFunction(key);
    int i = 0;
    while (table[quadraticProbing(index, i)].key != "") { // Suche nach dem passenden Eintrag
        int currentIndex = quadraticProbing(index, i);
        if (table[currentIndex].key == key && !table[currentIndex].isDeleted) {
            return table[currentIndex].value; // Rückgabe des Wertes für den Schlüssel
        }
        i++;
        if (i == TABLE_SIZE) { // Wenn die ganze Tabelle durchsucht wurde
            break;
        }
    }
    return ""; // Kein Eintrag gefunden, leerer String zurückgeben
}

// Funktion zum Löschen eines Hash-Eintrags
void remoove(string key) {
    int index = hashFunction(key);
    int i = 0;
    while (table[quadraticProbing(index, i)].key != "") { // Suche nach dem passenden Eintrag
        int currentIndex = quadraticProbing(index, i);
        if (table[currentIndex].key == key && !table[currentIndex].isDeleted) {
            table[currentIndex].isDeleted = true; // Markieren des Eintrags als gelöscht
            return;
        }
        i++;
        if (i == TABLE_SIZE) { // Wenn die ganze Tabelle durchsucht wurde
            break;
        }
    }
}

int main() {
    insert("Hello", "World");
    insert("Foo", "Bar");
    insert("Baz", "Qux");

    cout << get("Hello") << endl; // Ausgabe: World
    cout << get("Foo") << endl; // Ausgabe: Bar
    cout << get("Baz") << endl; // Ausgabe: Qux

    remoove("Hello");

    cout << get("Hello") << endl; // Ausgabe: (leer)

    return 0;
}