Хеш-функции std::hash в C++ программировании

size_t hash_value = 0;
const int p = 31; // Простое число для умножения
for (char c : str) {
    hash_value = hash_value * p + c;
}
return hash_value;

// Использование std::unordered_map с целочисленными ключами
std::unordered_map<int, std::string> id_to_name;
id_to_name[42] = "Артур Дент";
id_to_name[1337] = "Хакер";
 
// Поиск по ключу
auto it = id_to_name.find(42);
if (it != id_to_name.end()) {
    std::cout << "Найдено: " << it->second << std::endl;
}

// Хранение уникальных строк
std::unordered_set<std::string> unique_words;
unique_words.insert("хеш");
unique_words.insert("таблица");
unique_words.insert("контейнер");
 
// Проверка наличия элемента
if (unique_words.contains("хеш")) { // C++20
    std::cout << "Слово найдено" << std::endl;
}

template<>
struct hash<int> {
    size_t operator()(int val) const noexcept {
        return static_cast<size_t>(val);
    }
};

index = hash_value % bucket_count

// Внутренняя структура std::unordered_map схематически:
struct HashTable {
    struct Bucket {
        std::forward_list<std::pair<const Key, Value>> elements;
        // Список элементов с одинаковым хешем
    };
    std::vector<Bucket> buckets;
    // Другие поля...
};

std::unordered_map<std::string, int> word_count;
// Получение текущего коэффициента загрузки
float current_load = word_count.load_factor();
// Установка максимального коэффициента загрузки
word_count.max_load_factor(0.7f);
// Зарезервировать место для N элементов без перехеширования
word_count.reserve(1000);

// Измерение времени поиска в std::map и std::unordered_map
const int N = 1'000'000;
std::map<int, int> ordered_map;
std::unordered_map<int, int> unordered_map;
 
// Заполнение контейнеров
for (int i = 0; i < N; ++i) {
    ordered_map[i] = i;
    unordered_map[i] = i;
}
 
// Измерение времени поиска
auto start = std::chrono::high_resolution_clock::now();
volatile int sum = 0;
for (int i = 0; i < 10000; ++i) {
    sum += ordered_map.find(rand() % N)->second;
}
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> elapsed = end - start;
std::cout << "std::map поиск: " << elapsed.count() << " секунд\n";
 
start = std::chrono::high_resolution_clock::now();
sum = 0;
for (int i = 0; i < 10000; ++i) {
    sum += unordered_map.find(rand() % N)->second;
}
end = std::chrono::high_resolution_clock::now();
elapsed = end - start;
std::cout << "std::unordered_map поиск: " << elapsed.count() << " секунд\n";

// Демонстрация различий между реализациями
std::string test = "Hello, world!";
size_t hash_value = std::hash<std::string>{}(test);
std::cout << "Хеш \"Hello, world!\": " << hash_value << std::endl;
// Может давать разные результаты в GCC, Clang и MSVC

template <typename T>
size_t salted_hash(const T& value, size_t salt) {
    std::hash<T> hasher;
    return hasher(value) ^ (salt + 0x9e3779b9 + (hasher(value) << 6) + (hasher(value) >> 2));
}

// Пример упрощенного идеального хеширования для ключевых слов C++
static const char* keywords[] = {"int", "char", "if", "for", "while", "class", "struct"};
// Предварительно вычисленная функция, гарантирующая отсутствие коллизий для данного набора
size_t keyword_hash(const std::string& word) {
    // Фиктивный пример, в реальности функция была бы сложнее
    switch(word.length()) {
        case 2: return 0; // "if"
        case 3: return word[0] == 'i' ? 1 : 2; // "int" или "for"
        case 4: return 3; // "char"
        case 5: return 4; // "while"
        case 5: return word[0] == 'c' ? 5 : 6; // "class" или "struct"
        default: return SIZE_MAX; // Не ключевое слово
    }
}

// Упрощенный пример LSH для строк (расстояние Хэмминга)
size_t lsh_hamming(const std::string& str, int sample_positions[], int n) {
    size_t hash = 0;
    for (int i = 0; i < n; ++i) {
        int pos = sample_positions[i];
        if (pos < str.length()) {
            hash = (hash << 1) | (str[pos] & 1); // Берем только один бит
        }
    }
    return hash;
}

Функция    | Скорость (GB/s) | Качество распределения | Коллизии (10^6 случайных строк)
-----------|----------------|------------------------|--------------------------------
FNV-1a     | ~1            | Хорошее                | ~500
MurmurHash3| ~5            | Очень хорошее          | ~20
CityHash   | ~7            | Отличное               | ~10
xxHash     | ~13           | Отличное               | ~8

struct Person {
    std::string name;
    int age;
    
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};
 
// Специализация std::hash для Person
namespace std {
    template<>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            // Комбинирование хешей отдельных полей
            size_t h1 = hash<std::string>{}(p.name);
            size_t h2 = hash<int>{}(p.age);
            return h1 ^ (h2 << 1); // Примитивное комбинирование
        }
    };
}

std::unordered_map<Person, std::string> person_roles;
Person alice{"Алиса", 30};
person_roles[alice] = "Разработчик";

// Улучшенное комбинирование хешей
size_t hash_combine(size_t seed, size_t hash) {
    seed ^= hash + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    return seed;
}
 
// Применение в специализации std::hash
size_t operator()(const Person& p) const {
    size_t seed = 0;
    seed = hash_combine(seed, std::hash<std::string>{}(p.name));
    seed = hash_combine(seed, std::hash<int>{}(p.age));
    return seed;
}

class Employee {
private:
    std::string name;
    int id;
    std::vector<std::string> skills;
    Department* department; // Указатель на другой объект
 
public:
    // Конструкторы, методы...
    
    bool operator==(const Employee& other) const {
        return id == other.id &&
               name == other.name &&
               skills == other.skills &&
               (department == other.department || 
                (department && other.department && 
                 *department == *other.department));
    }
    
    // Дружественная функция для доступа к приватным полям
    friend struct std::hash<Employee>;
};
 
namespace std {
    template<>
    struct hash<Employee> {
        size_t operator()(const Employee& e) const {
            size_t seed = 0;
            
            // Хеширование примитивных полей
            seed = hash_combine(seed, hash<string>{}(e.name));
            seed = hash_combine(seed, hash<int>{}(e.id));
            
            // Хеширование контейнера
            for (const auto& skill : e.skills) {
                seed = hash_combine(seed, hash<string>{}(skill));
            }
            
            // Хеширование указателя с проверкой на null
            if (e.department) {
                seed = hash_combine(seed, hash<Department>{}(*e.department));
            }
            
            return seed;
        }
    };
}

class Shape {
public:
    virtual ~Shape() = default;
    virtual bool operator==(const Shape& other) const = 0;
    virtual size_t hash_value() const = 0; // Виртуальный метод для хеширования
};
 
class Circle : public Shape {
private:
    double radius;
    Point center;
    
public:
    // Реализация operator==
    bool operator==(const Shape& other) const override {
        if (auto* circle = dynamic_cast<const Circle*>(&other)) {
            return radius == circle->radius && center == circle->center;
        }
        return false;
    }
    
    size_t hash_value() const override {
        size_t seed = 0;
        // Идентификатор типа для различения разных подклассов
        seed = hash_combine(seed, typeid(Circle).hash_code());
        seed = hash_combine(seed, hash<double>{}(radius));
        seed = hash_combine(seed, hash<Point>{}(center));
        return seed;
    }
};
 
// Специализация для базового класса, вызывающая виртуальный метод
namespace std {
    template<>
    struct hash<Shape> {
        size_t operator()(const Shape& s) const {
            return s.hash_value();
        }
    };
    
    // При необходимости также можно специализировать для каждого подкласса
    template<>
    struct hash<Circle> {
        size_t operator()(const Circle& c) const {
            return c.hash_value();
        }
    };
}

enum class Color { Red, Green, Blue, Yellow };
 
namespace std {
    template<>
    struct hash<Color> {
        size_t operator()(Color c) const {
            return static_cast<size_t>(c);
        }
    };
}

enum class LargeEnum : uint64_t { 
    Value1 = 1ULL << 40,
    Value2 = 1ULL << 41
    // ...
};
 
namespace std {
    template<>
    struct hash<LargeEnum> {
        size_t operator()(LargeEnum e) const {
            // Для 32-битных платформ может потребоваться дополнительная обработка
            return static_cast<size_t>(static_cast<uint64_t>(e));
        }
    };
}

template<typename T>
size_t hash_range(const T* begin, const T* end, size_t seed = 0) {
    for (; begin != end; ++begin) {
        seed = hash_combine(seed, std::hash<T>{}(*begin));
    }
    return seed;
}
 
// Применение для вектора
template<typename T>
struct hash<vector<T>> {
    size_t operator()(const vector<T>& v) const {
        return hash_range(v.data(), v.data() + v.size());
    }
};

// Пример простого теста равномерности распределения
void test_hash_distribution(size_t buckets = 100) {
    std::vector<int> distribution(buckets, 0);
    const int test_count = 1000000;
    
    for (int i = 0; i < test_count; ++i) {
        Person p{"Имя" + std::to_string(i), i % 100};
        size_t hash = std::hash<Person>{}(p);
        distribution[hash % buckets]++;
    }
    
    // Анализ распределения
    double mean = test_count / static_cast<double>(buckets);
    double variance = 0.0;
    
    for (int count : distribution) {
        variance += (count - mean) * (count - mean);
    }
    variance /= buckets;
    
    std::cout << "Среднее элементов на корзину: " << mean << std::endl;
    std::cout << "Дисперсия: " << variance << std::endl;
    std::cout << "Стандартное отклонение: " << std::sqrt(variance) << std::endl;
}

// Пример стабильного хеширования строки (FNV-1a)
size_t stable_string_hash(const std::string& str) {
    const uint64_t fnv_prime = 1099511628211ULL;
    const uint64_t fnv_offset_basis = 14695981039346656037ULL;
    
    uint64_t hash = fnv_offset_basis;
    for (char c : str) {
        hash ^= static_cast<uint64_t>(c);
        hash *= fnv_prime;
    }
    
    return static_cast<size_t>(hash);
}
 
// Использование в пользовательском типе
struct SerializablePerson {
    std::string name;
    int age;
    
    // Для сериализации
    std::vector<uint8_t> serialize() const {
        // Реализация сериализации...
    }
    
    static SerializablePerson deserialize(const std::vector<uint8_t>& data) {
        // Реализация десериализации...
    }
};
 
namespace std {
    template<>
    struct hash<SerializablePerson> {
        size_t operator()(const SerializablePerson& p) const {
            size_t h1 = stable_string_hash(p.name);
            size_t h2 = p.age;
            return h1 ^ (h2 << 1);
        }
    };
}

class IncrementalHasher {
private:
    size_t current_hash = 0;
 
public:
    IncrementalHasher() = default;
    
    // Добавление части данных к хешу
    template<typename T>
    void add(const T& data) {
        current_hash = hash_combine(current_hash, std::hash<T>{}(data));
    }
    
    // Специализация для массивов байтов
    void add_bytes(const void* data, size_t length) {
        const uint8_t* bytes = static_cast<const uint8_t*>(data);
        for (size_t i = 0; i < length; ++i) {
            current_hash = hash_combine(current_hash, std::hash<uint8_t>{}(bytes[i]));
        }
    }
    
    // Получение текущего значения хеша
    size_t get_hash() const {
        return current_hash;
    }
};
 
// Пример использования
void hash_large_file(const std::string& filename) {
    IncrementalHasher hasher;
    std::ifstream file(filename, std::ios::binary);
    
    constexpr size_t buffer_size = 4096;
    char buffer[buffer_size];
    
    while (file) {
        file.read(buffer, buffer_size);
        size_t bytes_read = file.gcount();
        if (bytes_read > 0) {
            hasher.add_bytes(buffer, bytes_read);
        }
    }
    
    std::cout << "Хеш файла: " << hasher.get_hash() << std::endl;
}

struct TreeNode {
    int value;
    std::vector<std::unique_ptr<TreeNode>> children;
    
    bool operator==(const TreeNode& other) const {
        if (value != other.value || children.size() != other.children.size()) {
            return false;
        }
        
        for (size_t i = 0; i < children.size(); ++i) {
            if (!(*children[i] == *other.children[i])) {
                return false;
            }
        }
        
        return true;
    }
};
 
namespace std {
template<>
struct hash<TreeNode> {
    size_t operator()(const TreeNode& node) const {
        size_t result = hash<int>{}(node.value);
        
        // Хеширование структуры дерева
        for (const auto& child : node.children) {
            // Рекурсивный вызов хеш-функции для дочерних узлов
            result = hash_combine(result, hash<TreeNode>{}(*child));
        }
        
        return result;
    }
};
}

// Пример оптимизированной хеш-функции для структур с выравниванием
struct AlignedData {
    int32_t field1;
    int32_t field2;
    int64_t field3;
    
    // Гарантируем выравнивание структуры
    alignas(16) char buffer[16];
    
    bool operator==(const AlignedData& other) const {
        return field1 == other.field1 &&
               field2 == other.field2 &&
               field3 == other.field3 &&
               std::memcmp(buffer, other.buffer, sizeof(buffer)) == 0;
    }
};
 
namespace std {
template<>
struct hash<AlignedData> {
    size_t operator()(const AlignedData& data) const {
        // Используем выравнивание для эффективного доступа
        const uint64_t* ptr64 = reinterpret_cast<const uint64_t*>(&data);
        
        // Для 64-битных систем
        size_t result = ptr64[0]; // Включает field1 и field2
        result = hash_combine(result, ptr64[1]); // field3
        
        // Обработка буфера с выравниванием
        result = hash_combine(result, ptr64[2]);
        result = hash_combine(result, ptr64[3]);
        
        return result;
    }
};
}

// Хеш-функция для приближенного сравнения чисел с плавающей точкой
struct ApproximateDouble {
    double value;
    double epsilon; // Точность сравнения
    
    bool operator==(const ApproximateDouble& other) const {
        return std::abs(value - other.value) <= epsilon;
    }
};
 
namespace std {
template<>
struct hash<ApproximateDouble> {
    size_t operator()(const ApproximateDouble& ad) const {
        // Округляем до заданной точности перед хешированием
        double rounded = std::round(ad.value / ad.epsilon) * ad.epsilon;
        return hash<double>{}(rounded);
    }
};
}

template<typename T>
class SecureHasher {
private:
    size_t seed;
 
public:
    explicit SecureHasher(size_t random_seed = std::random_device{}()) 
        : seed(random_seed) {}
    
    size_t operator()(const T& value) const {
        std::hash<T> base_hasher;
        // Комбинируем базовый хеш со случайным числом
        return hash_combine(base_hasher(value), seed);
    }
};
 
// Использование с unordered_map
std::unordered_map<
    std::string, 
    std::string, 
    SecureHasher<std::string>
> secure_map(
    10, // начальный размер
    SecureHasher<std::string>(/* можно передать seed */)
);

// Два варианта хеш-функции для строк
namespace string_hashers {
    // Быстрый, но простой вариант
    struct FastStringHash {
        size_t operator()(const std::string& s) const {
            size_t result = 0;
            // Учитываем только каждый n-й символ и длину
            for (size_t i = 0; i < s.length(); i += 4) {
                result = hash_combine(result, s[i]);
            }
            return hash_combine(result, s.length());
        }
    };
    
    // Более тщательный, но медленный вариант
    struct ThoroughStringHash {
        size_t operator()(const std::string& s) const {
            size_t result = 0;
            for (char c : s) {
                result = hash_combine(result, c);
            }
            return result;
        }
    };
}

// Упрощенный перцептивный хеш для изображения
struct PerceptualImageHash {
    static size_t compute(const Image& img, int resolution = 8) {
        // Уменьшение изображения до заданного разрешения
        Image resized = resize(img, resolution, resolution);
        
        // Преобразование в оттенки серого
        Image grayscale = to_grayscale(resized);
        
        // Вычисление среднего значения
        double mean = compute_mean(grayscale);
        
        // Создание бинарного шаблона: 1 для пикселей ярче среднего, 0 для остальных
        size_t hash = 0;
        for (int y = 0; y < resolution; ++y) {
            for (int x = 0; x < resolution; ++x) {
                hash = (hash << 1) | (grayscale.pixel(x, y) > mean ? 1 : 0);
            }
        }
        
        return hash;
    }
};

// Улучшенная техника комбинирования хешей с использованием Boost-подобного алгоритма
template <typename T>
size_t hash_val(const T& val) {
    return std::hash<T>{}(val);
}
 
template <typename T, typename... Types>
size_t hash_val(const T& first, const Types&... rest) {
    size_t seed = hash_val(first);
    // Магическое число на основе золотого сечения улучшает перемешивание битов
    return hash_val(rest...) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
 
// Пример использования для структуры с несколькими полями
struct ComplexObject {
    std::string name;
    std::vector<int> data;
    double coefficient;
    
    // Для простоты опустим оператор сравнения
};
 
namespace std {
    template <>
    struct hash<ComplexObject> {
        size_t operator()(const ComplexObject& obj) const {
            return hash_val(
                obj.name,
                obj.coefficient,
                // Хеширование вектора с помощью обобщённой функции
                std::accumulate(obj.data.begin(), obj.data.end(), size_t{0},
                    [](size_t seed, int val) {
                        return seed + 0x9e3779b9 + (std::hash<int>{}(val) << 6) + (seed >> 2);
                    })
            );
        }
    };
}

template <typename Key, typename Value, size_t ShardCount = 16>
class ConcurrentHashMap {
private:
    struct Shard {
        std::unordered_map<Key, Value> map;
        std::mutex mutex;
    };
    
    std::array<Shard, ShardCount> shards;
    
    // Определяем, к какому сегменту относится ключ
    size_t shard_index(const Key& key) const {
        return std::hash<Key>{}(key) % ShardCount;
    }
    
public:
    // Атомарная вставка элемента
    void insert(const Key& key, const Value& value) {
        size_t index = shard_index(key);
        std::lock_guard<std::mutex> lock(shards[index].mutex);
        shards[index].map[key] = value;
    }
    
    // Атомарный поиск элемента
    std::optional<Value> find(const Key& key) const {
        size_t index = shard_index(key);
        std::lock_guard<std::mutex> lock(shards[index].mutex);
        auto it = shards[index].map.find(key);
        if (it != shards[index].map.end()) {
            return it->second;
        }
        return std::nullopt;
    }
    
    // Другие методы...
};

// Защищенная хеш-функция с использованием SipHash
class SecureHasher {
private:
    uint64_t k0, k1; // Секретные ключи
    
public:
    SecureHasher() {
        // Генерация случайных ключей при создании
        std::random_device rd;
        std::mt19937_64 gen(rd());
        std::uniform_int_distribution<uint64_t> dis;
        k0 = dis(gen);
        k1 = dis(gen);
    }
    
    template <typename T>
    size_t operator()(const T& value) const {
        // Упрощенная схема: в реальном коде используйте полноценный SipHash
        std::hash<T> standard_hash;
        uint64_t h = standard_hash(value);
        
        // Имитация SipHash с секретными ключами
        h ^= k0;
        h *= 0x9e3779b97f4a7c15ULL; // Константа из SipHash
        h ^= k1;
        h ^= h >> 33;
        h *= 0xc4ceb9fe1a85ec53ULL;
        h ^= h >> 33;
        
        return static_cast<size_t>(h);
    }
};

// Упрощенный пример perfect hashing для небольшого набора ключевых слов C++
class KeywordPerfectHash {
private:
    static const std::array<std::string, 10> keywords;
    static const std::array<size_t, 10> hash_table;
    
    // Специальная хеш-функция, подобранная для избежания коллизий
    static size_t special_hash(const std::string& str) {
        // Простая для демонстрации функция; в реальности была бы сложнее
        size_t h = 0;
        for (char c : str) {
            h = (h * 13 + c) % 23;
        }
        return h;
    }
    
public:
    // Проверяет, является ли строка ключевым словом
    static bool is_keyword(const std::string& str) {
        size_t index = hash_table[special_hash(str)];
        // Если индекс некорректный или строка не совпадает с ключевым словом
        if (index >= keywords.size() || keywords[index] != str) {
            return false;
        }
        return true;
    }
};
 
// Определение статических членов
const std::array<std::string, 10> KeywordPerfectHash::keywords = {
    "auto", "break", "case", "class", "const", "continue", "default", "delete", "do", "double"
};
 
// Для каждого возможного хеш-значения указываем индекс или некорректный индекс, если нет соответствия
const std::array<size_t, 10> KeywordPerfectHash::hash_table = {
    // Индексы, соответствующие хеш-значениям от 0 до 9
    // Реальные значения зависели бы от выбранной хеш-функции
    2, 7, 0, 3, 9, 1, 8, 5, 6, 4
};

// Упрощенный пример LSH для поиска похожих документов
class MinHashLSH {
private:
    static const int NUM_PERMUTATIONS = 100;
    std::vector<std::vector<int>> permutations;
    
public:
    MinHashLSH() {
        // Создаем случайные перестановки для хеширования
        std::random_device rd;
        std::mt19937 gen(rd());
        
        const int VOCABULARY_SIZE = 10000; // Предполагаемый размер словаря
        for (int i = 0; i < NUM_PERMUTATIONS; ++i) {
            std::vector<int> perm(VOCABULARY_SIZE);
            std::iota(perm.begin(), perm.end(), 0);
            std::shuffle(perm.begin(), perm.end(), gen);
            permutations.push_back(std::move(perm));
        }
    }
    
    // Вычисляет сигнатуру MinHash для множества слов
    std::vector<int> compute_signature(const std::unordered_set<std::string>& document_words,
                                       const std::unordered_map<std::string, int>& word_to_id) {
        std::vector<int> signature(NUM_PERMUTATIONS, std::numeric_limits<int>::max());
        
        // Для каждого слова в документе
        for (const auto& word : document_words) {
            if (word_to_id.count(word) == 0) continue;
            int word_id = word_to_id.at(word);
            
            // Для каждой перестановки обновляем минимальное значение
            for (int i = 0; i < NUM_PERMUTATIONS; ++i) {
                signature[i] = std::min(signature[i], permutations[i][word_id]);
            }
        }
        
        return signature;
    }
    
    // Оценивает сходство двух сигнатур (приближение Jaccard similarity)
    double estimate_similarity(const std::vector<int>& sig1, const std::vector<int>& sig2) {
        int matches = 0;
        for (int i = 0; i < NUM_PERMUTATIONS; ++i) {
            if (sig1[i] == sig2[i]) {
                matches++;
            }
        }
        return static_cast<double>(matches) / NUM_PERMUTATIONS;
    }
};

template <typename Key, typename Value>
class CuckooHashTable {
private:
    static const size_t NUM_TABLES = 2;
    static const size_t MAX_LOOP = 100;
    
    struct Entry {
        Key key;
        Value value;
        bool occupied = false;
    };
    
    std::vector<std::vector<Entry>> tables;
    std::array<std::function<size_t(const Key&)>, NUM_TABLES> hash_functions;
    
public:
    CuckooHashTable(size_t capacity = 1024) : tables(NUM_TABLES) {
        for (auto& table : tables) {
            table.resize(capacity);
        }
        
        // Инициализация разных хеш-функций
        std::random_device rd;
        std::seed_seq seeds{rd(), rd(), rd(), rd()};
        std::mt19937 gen(seeds);
        std::uniform_int_distribution<size_t> dis;
        
        for (size_t i = 0; i < NUM_TABLES; ++i) {
            size_t seed = dis(gen);
            hash_functions[i] = [seed, capacity](const Key& key) {
                std::hash<Key> hasher;
                return (hasher(key) ^ seed) % capacity;
            };
        }
    }
    
    bool insert(const Key& key, const Value& value) {
        Key current_key = key;
        Value current_value = value;
        
        for (size_t loop = 0; loop < MAX_LOOP; ++loop) {
            for (size_t table_idx = 0; table_idx < NUM_TABLES; ++table_idx) {
                size_t pos = hash_functions[table_idx](current_key);
                
                if (!tables[table_idx][pos].occupied) {
                    tables[table_idx][pos].key = current_key;
                    tables[table_idx][pos].value = current_value;
                    tables[table_idx][pos].occupied = true;
                    return true;
                }
                
                // Вытесняем существующий элемент (как кукушка выталкивает другие яйца)
                std::swap(current_key, tables[table_idx][pos].key);
                std::swap(current_value, tables[table_idx][pos].value);
            }
        }
        
        // Если достигли MAX_LOOP, нужно перехеширование
        return false;
    }
    
    std::optional<Value> find(const Key& key) const {
        for (size_t table_idx = 0; table_idx < NUM_TABLES; ++table_idx) {
            size_t pos = hash_functions[table_idx](key);
            
            if (tables[table_idx][pos].occupied && tables[table_idx][pos].key == key) {
                return tables[table_idx][pos].value;
            }
        }
        
        return std::nullopt;
    }
};

template <typename T>
class BloomFilter {
private:
    std::vector<bool> bits;
    std::array<std::function<size_t(const T&)>, 3> hash_functions;
    size_t num_elements = 0;
 
public:
    BloomFilter(size_t expected_elements, double false_positive_rate = 0.01) {
        // Вычисляем оптимальный размер на основе ожидаемого количества элементов
        // и желаемой вероятности ложноположительных срабатываний
        size_t size = -std::log(false_positive_rate) * expected_elements / std::log(2) / std::log(2);
        bits.resize(size, false);
        
        // Создаем несколько независимых хеш-функций
        std::random_device rd;
        std::mt19937_64 gen(rd());
        std::uniform_int_distribution<uint64_t> dis;
        
        for (auto& func : hash_functions) {
            uint64_t seed = dis(gen);
            func = [this, seed](const T& value) {
                std::hash<T> hasher;
                return (hasher(value) ^ seed) % bits.size();
            };
        }
    }
    
    void insert(const T& value) {
        for (const auto& hash_func : hash_functions) {
            size_t index = hash_func(value);
            bits[index] = true;
        }
        num_elements++;
    }
    
    bool might_contain(const T& value) const {
        for (const auto& hash_func : hash_functions) {
            size_t index = hash_func(value);
            if (!bits[index]) {
                return false; // Точно не содержится
            }
        }
        return true; // Возможно содержится (с некоторой вероятностью ошибки)
    }
    
    // Оценка заполненности фильтра
    double fill_ratio() const {
        size_t set_bits = std::count(bits.begin(), bits.end(), true);
        return static_cast<double>(set_bits) / bits.size();
    }
};

template <typename Key, typename Value>
class HopscotchHashTable {
private:
    static const size_t HOP_RANGE = 32; // Должно быть <= 64 для эффективного представления битсета
    
    struct Entry {
        Key key;
        Value value;
        bool occupied = false;
    };
    
    std::vector<Entry> table;
    std::vector<uint64_t> hop_info; // Битсет, показывающий "соседство"
    std::hash<Key> hasher;
    size_t capacity;
    size_t size_ = 0;
    
    size_t get_hash(const Key& key) const {
        return hasher(key) % capacity;
    }
    
public:
    HopscotchHashTable(size_t initial_capacity = 1024) 
        : capacity(initial_capacity), table(initial_capacity), hop_info(initial_capacity, 0) {}
    
    bool insert(const Key& key, const Value& value) {
        size_t home_bucket = get_hash(key);
        
        // Проверяем, не существует ли уже элемент
        for (size_t i = 0; i < HOP_RANGE; ++i) {
            if ((hop_info[home_bucket] & (1ULL << i)) && 
                table[(home_bucket + i) % capacity].key == key) {
                // Обновляем существующее значение
                table[(home_bucket + i) % capacity].value = value;
                return true;
            }
        }
        
        // Ищем свободную ячейку в окрестности домашнего бакета
        for (size_t i = 0; i < HOP_RANGE; ++i) {
            size_t bucket = (home_bucket + i) % capacity;
            if (!table[bucket].occupied) {
                table[bucket].key = key;
                table[bucket].value = value;
                table[bucket].occupied = true;
                hop_info[home_bucket] |= (1ULL << i);
                size_++;
                return true;
            }
        }
        
        // Если окрестность заполнена, пытаемся освободить место
        // [Упрощенная версия - в реальности здесь был бы сложный алгоритм перемещения]
        
        // Если не удалось найти или освободить место, требуется перехеширование
        return false;
    }
    
    std::optional<Value> find(const Key& key) const {
        size_t home_bucket = get_hash(key);
        
        // Проверяем только ячейки в окрестности
        for (size_t i = 0; i < HOP_RANGE; ++i) {
            if (hop_info[home_bucket] & (1ULL << i)) {
                size_t bucket = (home_bucket + i) % capacity;
                if (table[bucket].key == key) {
                    return table[bucket].value;
                }
            }
        }
        
        return std::nullopt;
    }
    
    size_t size() const {
        return size_;
    }
};

template <typename Key, typename Value>
class RobinHoodHashTable {
private:
    struct Entry {
        Key key;
        Value value;
        int probe_distance = -1; // -1 означает пустую ячейку
    };
    
    std::vector<Entry> table;
    std::hash<Key> hasher;
    size_t size_ = 0;
    size_t capacity;
    
    size_t get_hash(const Key& key) const {
        return hasher(key) % capacity;
    }
    
public:
    RobinHoodHashTable(size_t initial_capacity = 1024) 
        : table(initial_capacity), capacity(initial_capacity) {}
    
    bool insert(const Key& key, const Value& value) {
        size_t ideal_pos = get_hash(key);
        int probe_distance = 0;
        
        while (probe_distance < capacity) { // Ограничение на максимальную длину поиска
            size_t current_pos = (ideal_pos + probe_distance) % capacity;
            
            // Если ячейка пуста или содержит тот же ключ
            if (table[current_pos].probe_distance == -1) {
                table[current_pos].key = key;
                table[current_pos].value = value;
                table[current_pos].probe_distance = probe_distance;
                size_++;
                return true;
            }
            
            // Если текущий элемент находится дальше от своей идеальной позиции,
            // чем новый элемент, меняем их местами (Robin Hood)
            if (table[current_pos].probe_distance < probe_distance) {
                std::swap(key, table[current_pos].key);
                std::swap(value, table[current_pos].value);
                std::swap(probe_distance, table[current_pos].probe_distance);
            }
            
            probe_distance++;
        }
        
        // Не удалось вставить элемент, требуется перехеширование
        return false;
    }
    
    std::optional<Value> find(const Key& key) const {
        size_t ideal_pos = get_hash(key);
        int probe_distance = 0;
        
        while (probe_distance < capacity) {
            size_t current_pos = (ideal_pos + probe_distance) % capacity;
            
            if (table[current_pos].probe_distance == -1) {
                // Достигли пустой ячейки
                return std::nullopt;
            }
            
            if (table[current_pos].probe_distance < probe_distance) {
                // Если текущий элемент ближе к своей идеальной позиции,
                // чем мы к нашей, значит искомого элемента нет
                return std::nullopt;
            }
            
            if (table[current_pos].key == key) {
                return table[current_pos].value;
            }
            
            probe_distance++;
        }
        
        return std::nullopt;
    }
    
    size_t size() const {
        return size_;
    }
};

// Пример метрической хеш-функции для строк (на основе расстояния Левенштейна)
class LevenshteinHasher {
private:
    struct Pivot {
        std::string reference;
        int bucket_radius;
    };
    
    std::vector<Pivot> pivots;
    
    // Вычисляет расстояние Левенштейна между двумя строками
    int levenshtein_distance(const std::string& a, const std::string& b) const {
        // Динамическое программирование для вычисления расстояния редактирования
        // [Упрощено: в реальном коде была бы полная реализация]
        if (a == b) return 0;
        if (a.empty()) return b.length();
        if (b.empty()) return a.length();
        
        // Частичная реализация для демонстрации
        return std::abs(static_cast<int>(a.length() - b.length()));
    }
    
public:
    // Инициализация с опорными точками (pivots)
    LevenshteinHasher(const std::vector<std::pair<std::string, int>>& reference_points) {
        for (const auto& [ref, radius] : reference_points) {
            pivots.push_back({ref, radius});
        }
    }
    
    // Хеширование строки в виде вектора принадлежности к "ячейкам" вокруг опорных точек
    std::vector<bool> hash(const std::string& str) const {
        std::vector<bool> result(pivots.size());
        
        for (size_t i = 0; i < pivots.size(); ++i) {
            int distance = levenshtein_distance(str, pivots[i].reference);
            result[i] = (distance <= pivots[i].bucket_radius);
        }
        
        return result;
    }
    
    // Оценка сходства на основе хеш-значений
    double estimate_similarity(const std::vector<bool>& hash1, const std::vector<bool>& hash2) const {
        if (hash1.size() != hash2.size()) return 0.0;
        
        int matches = 0;
        for (size_t i = 0; i < hash1.size(); ++i) {
            if (hash1[i] == hash2[i]) {
                matches++;
            }
        }
        
        return static_cast<double>(matches) / hash1.size();
    }
};

class RollingHash {
private:
    const uint64_t base = 256; // Основание (обычно размер алфавита)
    const uint64_t mod = 1000000007; // Большое простое число
    uint64_t current_hash = 0;
    uint64_t power = 1; // base^(window_size-1) mod mod
    size_t window_size;
    std::deque<char> window;
    
public:
    explicit RollingHash(size_t size) : window_size(size) {
        // Предварительное вычисление base^(window_size-1)
        for (size_t i = 1; i < window_size; ++i) {
            power = (power * base) % mod;
        }
    }
    
    // Добавляет символ и возвращает обновленное хеш-значение
    uint64_t add(char c) {
        window.push_back(c);
        current_hash = ((current_hash * base) % mod + c) % mod;
        
        if (window.size() > window_size) {
            // Удаляем влияние уходящего символа
            char removed = window.front();
            window.pop_front();
            current_hash = (mod + current_hash - (power * removed) % mod) % mod;
        }
        
        return current_hash;
    }
    
    // Получение текущего хеш-значения
    uint64_t hash() const {
        return current_hash;
    }
    
    // Сброс хеша
    void reset() {
        current_hash = 0;
        window.clear();
    }
};
 
// Пример использования: алгоритм Рабина-Карпа для поиска подстроки
std::vector<size_t> rabin_karp_search(const std::string& text, const std::string& pattern) {
    std::vector<size_t> matches;
    if (pattern.empty() || pattern.size() > text.size()) return matches;
    
    // Вычисляем хеш паттерна
    RollingHash pattern_hasher(pattern.size());
    for (char c : pattern) {
        pattern_hasher.add(c);
    }
    uint64_t pattern_hash = pattern_hasher.hash();
    
    // Ищем совпадения в тексте
    RollingHash text_hasher(pattern.size());
    for (size_t i = 0; i < text.size(); ++i) {
        text_hasher.add(text[i]);
        
        // Если окно достигло полного размера и хеши совпадают
        if (i >= pattern.size() - 1) {
            if (text_hasher.hash() == pattern_hash) {
                // Проверяем посимвольно для исключения коллизий
                bool match = true;
                for (size_t j = 0; j < pattern.size(); ++j) {
                    if (text[i - pattern.size() + 1 + j] != pattern[j]) {
                        match = false;
                        break;
                    }
                }
                
                if (match) {
                    matches.push_back(i - pattern.size() + 1);
                }
            }
        }
    }
    
    return matches;
}

// Пример кеш-оптимизированной хеш-таблицы
template <typename Key, typename Value>
class CacheOptimizedHashTable {
private:
    // Группируем ключи и хеш-значения вместе для лучшей локальности кеша
    struct alignas(64) Bucket { // Выравнивание по размеру линии кеша
        static const size_t ENTRIES_PER_BUCKET = 8;
        
        struct Entry {
            Key key;
            Value value;
            bool occupied = false;
        };
        
        std::array<Entry, ENTRIES_PER_BUCKET> entries;
    };
    
    std::vector<Bucket> buckets;
    std::hash<Key> hasher;
    size_t num_buckets;
    size_t size_ = 0;
    
public:
    CacheOptimizedHashTable(size_t initial_size = 1024) {
        num_buckets = initial_size / Bucket::ENTRIES_PER_BUCKET;
        if (num_buckets == 0) num_buckets = 1;
        buckets.resize(num_buckets);
    }
    
    bool insert(const Key& key, const Value& value) {
        size_t bucket_idx = hasher(key) % num_buckets;
        auto& bucket = buckets[bucket_idx];
        
        // Сначала ищем существующий ключ или свободное место
        for (auto& entry : bucket.entries) {
            if (entry.occupied && entry.key == key) {
                entry.value = value; // Обновляем значение
                return true;
            }
            else if (!entry.occupied) {
                entry.key = key;
                entry.value = value;
                entry.occupied = true;
                size_++;
                return true;
            }
        }
        
        // Если бакет заполнен, можно реализовать стратегию переполнения
        // (например, следующий бакет или отдельное хранилище для переполнений)
        return false;
    }
    
    std::optional<Value> find(const Key& key) const {
        size_t bucket_idx = hasher(key) % num_buckets;
        const auto& bucket = buckets[bucket_idx];
        
        for (const auto& entry : bucket.entries) {
            if (entry.occupied && entry.key == key) {
                return entry.value;
            }
        }
        
        return std::nullopt;
    }
    
    size_t size() const {
        return size_;
    }
};

class LightingCalculator {
private:
    struct LightParams {
        Vector3 position;
        Vector3 direction;
        float intensity;
        
        bool operator==(const LightParams& other) const {
            return position == other.position &&
                   direction == other.direction &&
                   std::abs(intensity - other.intensity) < 1e-6f;
        }
    };
    
    std::unordered_map<LightParams, Color> lighting_cache;
 
public:
    Color calculateLighting(const LightParams& params) {
        auto it = lighting_cache.find(params);
        if (it != lighting_cache.end()) {
            return it->second; // Возвращаем кешированный результат
        }
        
        // Выполняем дорогостоящие вычисления
        Color result = performExpensiveLightingCalculation(params);
        
        // Сохраняем в кеше для будущего использования
        lighting_cache[params] = result;
        return result;
    }
};
 
// Специализация std::hash для LightParams
namespace std {
    template<>
    struct hash<LightingCalculator::LightParams> {
        size_t operator()(const LightingCalculator::LightParams& p) const {
            size_t h1 = hash<float>{}(p.position.x) ^ hash<float>{}(p.position.y) ^ hash<float>{}(p.position.z);
            size_t h2 = hash<float>{}(p.direction.x) ^ hash<float>{}(p.direction.y) ^ hash<float>{}(p.direction.z);
            size_t h3 = hash<float>{}(p.intensity);
            return h1 ^ (h2 << 1) ^ (h3 << 2);
        }
    };
}

template <typename T>
class DedupStore {
private:
    std::unordered_map<T, std::weak_ptr<T>> storage;
    std::mutex mutex;
 
public:
    std::shared_ptr<T> store(const T& value) {
        std::lock_guard<std::mutex> lock(mutex);
        
        auto it = storage.find(value);
        if (it != storage.end()) {
            if (auto existing = it->second.lock()) {
                return existing; // Возвращаем существующий объект
            }
        }
        
        // Создаём новый объект и сохраняем слабую ссылку
        auto new_ptr = std::make_shared<T>(value);
        storage[value] = new_ptr;
        return new_ptr;
    }
};

class DistributedCache {
public:
    bool needsUpdate(const std::string& key, const std::vector<char>& data) {
        size_t data_hash = std::hash<std::string>{}(std::string(data.begin(), data.end()));
        
        // Проверяем, изменились ли данные с последнего обновления
        if (key_hash_map.find(key) != key_hash_map.end() && 
            key_hash_map[key] == data_hash) {
            return false; // Данные не изменились
        }
        
        // Сохраняем новый хеш
        key_hash_map[key] = data_hash;
        return true; // Требуется обновление
    }
 
private:
    std::unordered_map<std::string, size_t> key_hash_map;
};

class GeneticOptimizer {
private:
    struct Chromosome {
        std::vector<int> genes;
        
        bool operator==(const Chromosome& other) const {
            return genes == other.genes;
        }
    };
    
    std::unordered_set<Chromosome> population;
 
public:
    void addIfUnique(const Chromosome& candidate) {
        // Добавляем только если такой хромосомы ещё нет в популяции
        population.insert(candidate);
    }
};
 
namespace std {
    template<>
    struct hash<GeneticOptimizer::Chromosome> {
        size_t operator()(const GeneticOptimizer::Chromosome& c) const {
            return hash<vector<int>>{}(c.genes);
        }
    };
}

size_t fibonacci(int n, std::unordered_map<int, size_t>& cache) {
    if (n <= 1) return n;
    
    auto it = cache.find(n);
    if (it != cache.end()) {
        return it->second;
    }
    
    size_t result = fibonacci(n-1, cache) + fibonacci(n-2, cache);
    cache[n] = result;
    return result;
}

double priceOption(const OptionParams& params, std::unordered_map<OptionParams, double>& cache) {
    auto it = cache.find(params);
    if (it != cache.end()) {
        return it->second;
    }
    
    // Сложные расчеты по методу Монте-Карло
    double price = calculateOptionPriceMonteCarlo(params);
    cache[params] = price;
    return price;
}

template <typename T>
class HashBasedSerializer {
private:
    std::unordered_map<size_t, std::string> hash_to_data;
    
public:
    std::string serializeIfChanged(const T& obj) {
        size_t hash = std::hash<T>{}(obj);
        
        // Сериализуем только если хеш не найден
        if (hash_to_data.find(hash) == hash_to_data.end()) {
            std::string serialized = serialize(obj);
            hash_to_data[hash] = serialized;
            return serialized;
        }
        
        return hash_to_data[hash];
    }
};

template <typename Key, typename Value>
class MemoryEfficientMap {
private:
    // Разделяем данные на страницы для уменьшения фрагментации
    static constexpr size_t PAGE_SIZE = 1024;
    std::vector<std::pair<Key, Value>*> pages;
    
    std::unordered_map<Key, std::pair<size_t, size_t>> index; // Отображение ключ -> (страница, смещение)
    
    std::pair<Key, Value>* allocateNewPair() {
        if (pages.empty() || currentPageOffset >= PAGE_SIZE) {
            pages.push_back(new std::pair<Key, Value>[PAGE_SIZE]);
            currentPageOffset = 0;
        }
        
        return &pages.back()[currentPageOffset++];
    }
    
    size_t currentPageOffset = 0;
    
public:
    void insert(const Key& key, const Value& value) {
        auto* pair = allocateNewPair();
        pair->first = key;
        pair->second = value;
        
        index[key] = {pages.size() - 1, currentPageOffset - 1};
    }
    
    // ... остальные методы
    
    ~MemoryEfficientMap() {
        for (auto* page : pages) {
            delete[] page;
        }
    }
};