size_t hash(const std::string& key);

size_t simpleHash(const std::string& key)
{
    size_t hash = 0;
    const size_t prime = 31;  // Просте число для зменшення колізій
    
    for (char c : key)
    {
        hash = hash * prime + static_cast<size_t>(c);
    }
    
    return hash;
}

hash = 0
Символ 'c' (ASCII 99): hash = 0 * 31 + 99 = 99
Символ 'a' (ASCII 97): hash = 99 * 31 + 97 = 3166
Символ 't' (ASCII 116): hash = 3166 * 31 + 116 = 98262
Фінальний хеш: 98262

size_t index = simpleHash("cat") % M;  // M = 100 → index = 98262 % 100 = 62

simpleHash("listen") % 100 → 42
simpleHash("silent") % 100 → 42  // Колізія!

template <typename K, typename V>
struct HashNode
{
    K key;          // Ключ (наприклад, std::string)
    V value;        // Значення (наприклад, std::string)
    HashNode* next; // Покажчик на наступний вузол у ланцюжку колізій
    
    HashNode(const K& k, const V& v)
        : key(k), value(v), next(nullptr)
    {
    }
};

// HashTable.h
#ifndef HASH_TABLE_H
#define HASH_TABLE_H

#include <iostream>
#include <vector>
#include <string>
#include <stdexcept>

template <typename K, typename V>
struct HashNode
{
    K key;
    V value;
    HashNode* next;
    
    HashNode(const K& k, const V& v)
        : key(k), value(v), next(nullptr)
    {
    }
};

template <typename K, typename V>
class HashTable
{
private:
    std::vector<HashNode<K, V>*> buckets;  // Масив покажчиків на голови списків
    size_t count;                          // Кількість елементів у таблиці
    size_t bucketCount;                    // Кількість бакетів
    
    // Константа для обчислення порогу завантаження
    static constexpr double MAX_LOAD_FACTOR = 0.75;
    
    // Приватні допоміжні методи
    size_t hashFunction(const K& key) const;
    size_t getBucketIndex(const K& key) const;
    void rehash();
    void destroyBucket(HashNode<K, V>* node);

public:
    // Конструктор: створює таблицю із заданою початковою ємністю
    explicit HashTable(size_t capacity = 16);
    
    // Деструктор: звільняє всі вузли (RAII)
    ~HashTable();
    
    // Заборона копіювання (для простоти)
    HashTable(const HashTable&) = delete;
    HashTable& operator=(const HashTable&) = delete;
    
    // Вставити пару (ключ, значення)
    void insert(const K& key, const V& value);
    
    // Видалити елемент за ключем
    bool remove(const K& key);
    
    // Знайти значення за ключем (повертає покажчик або nullptr)
    V* find(const K& key);
    const V* find(const K& key) const;
    
    // Перевірити, чи таблиця порожня
    bool isEmpty() const;
    
    // Отримати кількість елементів
    size_t size() const;
    
    // Отримати поточну ємність (кількість бакетів)
    size_t capacity() const;
    
    // Обчислити поточний коефіцієнт завантаження
    double loadFactor() const;
    
    // Вивести статистику таблиці (для відлагодження)
    void printStatistics() const;
};

#endif

// HashTable.cpp (реалізація шаблонного класу зазвичай у .h, але для наочності виносимо окремо)

template <typename K, typename V>
HashTable<K, V>::HashTable(size_t capacity)
    : buckets(capacity, nullptr)
    , count(0)
    , bucketCount(capacity)
{
    if (capacity == 0)
    {
        throw std::invalid_argument("Capacity must be greater than zero");
    }
}

template <typename K, typename V>
HashTable<K, V>::~HashTable()
{
    // Проходимо по всіх бакетах та знищуємо їхні списки
    for (size_t i = 0; i < bucketCount; ++i)
    {
        destroyBucket(buckets[i]);
    }
}

// Рекурсивне знищення зв'язаного списку в бакеті
template <typename K, typename V>
void HashTable<K, V>::destroyBucket(HashNode<K, V>* node)
{
    if (node == nullptr)
    {
        return;  // Базовий випадок: порожній бакет
    }
    
    // Рекурсивно знищуємо наступний вузол
    destroyBucket(node->next);
    
    // Тепер можна видалити поточний вузол
    delete node;
}

// Спеціалізація для std::string (для інших типів потрібні окремі перевантаження)
template <>
size_t HashTable<std::string, std::string>::hashFunction(const std::string& key) const
{
    size_t hash = 0;
    const size_t prime = 31;
    
    for (char c : key)
    {
        hash = hash * prime + static_cast<size_t>(c);
    }
    
    return hash;
}

// Загальний метод для будь-яких типів K, V
template <typename K, typename V>
size_t HashTable<K, V>::getBucketIndex(const K& key) const
{
    return hashFunction(key) % bucketCount;
}

template <typename K, typename V>
void HashTable<K, V>::insert(const K& key, const V& value)
{
    // Крок 1: Знайти індекс бакета
    size_t index = getBucketIndex(key);
    
    // Крок 2: Перевірити, чи ключ вже існує
    HashNode<K, V>* current = buckets[index];
    while (current != nullptr)
    {
        if (current->key == key)
        {
            // Ключ знайдено → оновлюємо значення
            current->value = value;
            return;  // Розмір не змінюється
        }
        current = current->next;
    }
    
    // Крок 3: Ключ не знайдено → створюємо новий вузол
    HashNode<K, V>* newNode = new HashNode<K, V>(key, value);
    
    // Вставка на початок списку (O(1))
    newNode->next = buckets[index];
    buckets[index] = newNode;
    
    // Крок 4: Збільшити розмір
    ++count;
    
    // Крок 5: Перевірити коефіцієнт завантаження
    if (loadFactor() > MAX_LOAD_FACTOR)
    {
        rehash();
    }
}

template <typename K, typename V>
double HashTable<K, V>::loadFactor() const
{
    return static_cast<double>(count) / bucketCount;
}

template <typename K, typename V>
V* HashTable<K, V>::find(const K& key)
{
    size_t index = getBucketIndex(key);
    HashNode<K, V>* current = buckets[index];
    
    // Проходимо по ланцюжку бакета
    while (current != nullptr)
    {
        if (current->key == key)
        {
            return &current->value;  // Знайдено → повертаємо покажчик на значення
        }
        current = current->next;
    }
    
    return nullptr;  // Не знайдено
}

// Константна версія для константних об'єктів HashTable
template <typename K, typename V>
const V* HashTable<K, V>::find(const K& key) const
{
    size_t index = getBucketIndex(key);
    HashNode<K, V>* current = buckets[index];
    
    while (current != nullptr)
    {
        if (current->key == key)
        {
            return &current->value;
        }
        current = current->next;
    }
    
    return nullptr;
}

HashTable<std::string, std::string> dict;
dict.insert("cat", "кіт");

std::string* translation = dict.find("cat");
if (translation != nullptr)
{
    std::cout << "Переклад: " << *translation << '\n';  // Виведе: Переклад: кіт
}
else
{
    std::cout << "Слово не знайдено\n";
}

template <typename K, typename V>
bool HashTable<K, V>::remove(const K& key)
{
    size_t index = getBucketIndex(key);
    HashNode<K, V>* current = buckets[index];
    HashNode<K, V>* previous = nullptr;
    
    // Проходимо по ланцюжку, відстежуючи попередній вузол
    while (current != nullptr)
    {
        if (current->key == key)
        {
            // Знайдено вузол для видалення
            
            if (previous == nullptr)
            {
                // Випадок 1: Видаляємо голову списку
                buckets[index] = current->next;
            }
            else
            {
                // Випадок 2: Видаляємо вузол всередині/в кінці списку
                previous->next = current->next;
            }
            
            delete current;  // Звільняємо пам'ять
            --count;         // Зменшуємо розмір таблиці
            return true;     // Успішно видалено
        }
        
        previous = current;
        current = current->next;
    }
    
    return false;  // Ключ не знайдено
}

template <typename K, typename V>
void HashTable<K, V>::rehash()
{
    size_t newCapacity = bucketCount * 2;
    std::vector<HashNode<K, V>*> newBuckets(newCapacity, nullptr);
    
    // Проходимо по всіх старих бакетах
    for (size_t i = 0; i < bucketCount; ++i)
    {
        HashNode<K, V>* current = buckets[i];
        
        // Проходимо по ланцюжку поточного бакета
        while (current != nullptr)
        {
            HashNode<K, V>* nextNode = current->next;  // Зберігаємо next (будемо змінювати)
            
            // Обчислюємо новий індекс для вузла
            size_t newIndex = hashFunction(current->key) % newCapacity;
            
            // Вставляємо вузол на початок нового бакета
            current->next = newBuckets[newIndex];
            newBuckets[newIndex] = current;
            
            current = nextNode;  // Переходимо до наступного у старому ланцюжку
        }
    }
    
    // Замінюємо старий масив на новий
    buckets = std::move(newBuckets);
    bucketCount = newCapacity;
}

template <typename K, typename V>
bool HashTable<K, V>::isEmpty() const
{
    return count == 0;
}

template <typename K, typename V>
size_t HashTable<K, V>::size() const
{
    return count;
}

template <typename K, typename V>
size_t HashTable<K, V>::capacity() const
{
    return bucketCount;
}

template <typename K, typename V>
void HashTable<K, V>::printStatistics() const
{
    size_t emptyBuckets = 0;
    size_t maxChainLength = 0;
    size_t totalChainLength = 0;
    
    for (size_t i = 0; i < bucketCount; ++i)
    {
        size_t chainLength = 0;
        HashNode<K, V>* current = buckets[i];
        
        while (current != nullptr)
        {
            ++chainLength;
            current = current->next;
        }
        
        if (chainLength == 0)
        {
            ++emptyBuckets;
        }
        else
        {
            totalChainLength += chainLength;
            maxChainLength = std::max(maxChainLength, chainLength);
        }
    }
    
    size_t filledBuckets = bucketCount - emptyBuckets;
    double avgChainLength = (filledBuckets > 0) 
        ? static_cast<double>(totalChainLength) / filledBuckets 
        : 0.0;
    
    std::cout << "=== Статистика хеш-таблиці ===\n";
    std::cout << "Кількість елементів: " << count << '\n';
    std::cout << "Кількість бакетів: " << bucketCount << '\n';
    std::cout << "Коефіцієнт завантаження: " << loadFactor() << '\n';
    std::cout << "Пустих бакетів: " << emptyBuckets << '\n';
    std::cout << "Заповнених бакетів: " << filledBuckets << '\n';
    std::cout << "Максимальна довжина ланцюжка: " << maxChainLength << '\n';
    std::cout << "Середня довжина ланцюжка: " << avgChainLength << '\n';
}

#include "HashTable.h"
#include <iostream>

int main()
{
    std::cout << "=== Демонстрація хеш-таблиці ===\n\n";
    
    // Створюємо словник англійсько-український
    HashTable<std::string, std::string> dictionary(8);  // Початкова ємність 8
    
    // Вставка елементів
    std::cout << "Додаємо слова до словника:\n";
    dictionary.insert("cat", "кіт");
    dictionary.insert("dog", "собака");
    dictionary.insert("apple", "яблуко");
    dictionary.insert("computer", "комп'ютер");
    dictionary.insert("algorithm", "алгоритм");
    dictionary.insert("data", "дані");
    dictionary.insert("structure", "структура");
    dictionary.insert("hash", "хеш");
    dictionary.insert("table", "таблиця");
    dictionary.insert("function", "функція");
    
    std::cout << "Додано " << dictionary.size() << " слів\n\n";
    
    // Пошук перекладів
    std::cout << "Пошук перекладів:\n";
    std::string words[] = {"cat", "algorithm", "zebra", "table"};
    
    for (const auto& word : words)
    {
        std::string* translation = dictionary.find(word);
        if (translation != nullptr)
        {
            std::cout << "  " << word << " → " << *translation << " ✓\n";
        }
        else
        {
            std::cout << "  " << word << " → не знайдено ✗\n";
        }
    }
    
    std::cout << '\n';
    
    // Статистика таблиці
    dictionary.printStatistics();
    std::cout << '\n';
    
    // Оновлення значення
    std::cout << "Оновлюємо переклад 'cat':\n";
    dictionary.insert("cat", "кішка");  // Перезаписує стару
    std::string* catTranslation = dictionary.find("cat");
    std::cout << "  cat → " << *catTranslation << '\n';
    std::cout << '\n';
    
    // Видалення елементів
    std::cout << "Видаляємо слова:\n";
    bool removed1 = dictionary.remove("dog");
    bool removed2 = dictionary.remove("zebra");
    std::cout << "  dog: " << (removed1 ? "видалено ✓" : "не знайдено ✗") << '\n';
    std::cout << "  zebra: " << (removed2 ? "видалено ✓" : "не знайдено ✗") << '\n';
    std::cout << "  Елементів залишилось: " << dictionary.size() << '\n';
    std::cout << '\n';
    
    // Фінальна статистика
    dictionary.printStatistics();
    
    return 0;
}

class Iterator
{
private:
    HashTable* table;
    size_t bucketIndex;
    HashNode<K, V>* currentNode;

public:
    Iterator& operator++();  // Перехід до наступного елемента
    std::pair<K, V>& operator*();  // Доступ до пари (ключ, значення)
    bool operator!=(const Iterator& other) const;
};

template <typename K, typename V, typename Hash = std::hash<K>>
class HashTable
{
    Hash hasher;  // Об'єкт хеш-функції
    
    size_t hashFunction(const K& key) const
    {
        return hasher(key);
    }
};

V& operator[](const K& key)
{
    V* value = find(key);
    if (value == nullptr)
    {
        insert(key, V());  // Вставити дефолтне значення
        value = find(key);
    }
    return *value;
}

#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
    std::unordered_map<std::string, std::string> dictionary;
    
    // Вставка
    dictionary["cat"] = "кіт";
    dictionary["dog"] = "собака";
    dictionary.insert({"apple", "яблуко"});
    
    // Пошук
    if (dictionary.find("cat") != dictionary.end())
    {
        std::cout << "cat → " << dictionary["cat"] << '\n';
    }
    
    // Видалення
    dictionary.erase("dog");
    
    // Обхід всіх елементів (маємо ітератори!)
    for (const auto& [key, value] : dictionary)
    {
        std::cout << key << " → " << value << '\n';
    }
    
    return 0;
}