Приведи пример хеш функции для int

Примеры хеш-функций для int

Хеш-функция преобразует входное значение в индекс для хеш-таблицы. Для целых чисел есть несколько подходов разной сложности.

1. Простая и наивная хеш-функция

Самый простой вариант — просто вернуть само число:

#include <cstdint>

uint32_t hash_simple(int key) {
    return static_cast<uint32_t>(key);
}

// Использование:
int table_size = 1000;
int index = hash_simple(42) % table_size;  // 42 % 1000 = 42

Проблемы:

• Плохое распределение: соседние числа дают соседние хеши
• Для таблицы размером N первые N чисел конфликтуют минимально
• Может привести к кластеризации (clustering) в хеш-таблице

2. Разумная хеш-функция (Division-based)

Использование простого числа в качестве размера таблицы:

#include <cstdint>
#include <cstdlib>

uint32_t hash_division(int key, int table_size) {
    // Берём остаток от деления
    // table_size должно быть простым числом для лучшего распределения
    return static_cast<uint32_t>(std::abs(key)) % table_size;
}

// Использование:
int table_size = 101;  // Простое число
int index = hash_division(42, table_size);
int index2 = hash_division(-42, table_size);  // Также 42

Преимущества:

• Просто и понятно
• Работает лучше, если table_size — простое число
• Хорошо для ненегативных чисел

Недостатки:

• Всё ещё плохое распределение для некоторых последовательностей
• Операция modulo медленнее, чем битовые операции

3. Битовая операция (для размеров, кратных степени 2)

#include <cstdint>

uint32_t hash_bitwise(int key) {
    // Берём логику: используем нижние биты
    // Это быстрее modulo
    return static_cast<uint32_t>(key) & 0xFF;  // 256 вариантов
}

// Или для произвольного размера, кратного 2^k:
uint32_t hash_power_of_two(int key, int mask) {
    // mask = table_size - 1, где table_size = 2^k
    return static_cast<uint32_t>(key) & mask;
}

// Использование:
int mask = 127;  // для таблицы размером 128 (2^7)
int index = hash_power_of_two(42, mask);

Преимущества:

• Очень быстро (битовая операция вместо деления)
• Идеален для power-of-2 размеров таблиц

Недостатки:

• Плохое распределение нижних битов
• Требует size = 2^k

4. Multiplicative hashing (Умножающее хеширование)

Использует золотое сечение для лучшего распределения:

#include <cstdint>

uint32_t hash_multiplicative(int key, int table_size) {
    // Константа золотого сечения для 32-бит: 2654435761
    // Это (sqrt(5) - 1) / 2 * 2^32 ≈ 0.618... * 2^32
    const uint32_t GOLDEN = 2654435761U;
    
    uint32_t h = static_cast<uint32_t>(key) * GOLDEN;
    return (h >> 16) % table_size;  // Берём верхние биты
}

// Использование:
int index = hash_multiplicative(42, 1000);

Преимущества:

• Хорошее распределение даже для последовательных чисел
• Быстро для больших таблиц
• Математически обоснованный подход

Недостатки:

• Сложнее для понимания
• Немного медленнее, чем простое modulo

5. Java-style хеш (распространённый подход)

#include <cstdint>

uint32_t hash_java_style(int key) {
    // Используется в Java HashMap
    uint32_t h = static_cast<uint32_t>(key);
    h ^= (h >> 16);  // XOR с битами, сдвинутыми на 16
    return h;
}

// Или с модификациями:
uint32_t hash_java_style_v2(int key, int table_size) {
    uint32_t h = static_cast<uint32_t>(key);
    h ^= (h >> 16);
    h ^= (h >> 8);  // Дополнительное перемешивание
    return h % table_size;
}

int index = hash_java_style_v2(42, 1000);

Преимущества:

• Хорошее распределение
• Проверено годами в production коде
• Простая реализация

6. FNV-1a хеш (криптографический подход)

Это более серьёзный хеш, используется для хеширования строк и данных:

#include <cstdint>

uint32_t hash_fnv1a(const uint8_t* data, size_t len) {
    const uint32_t FNV_prime = 16777619U;   // 2^24 + 2^8 + 0x93
    const uint32_t offset_basis = 2166136261U;
    
    uint32_t hash = offset_basis;
    
    for (size_t i = 0; i < len; i++) {
        hash ^= data[i];
        hash *= FNV_prime;
    }
    
    return hash;
}

// Для int:
uint32_t hash_fnv1a_int(int key) {
    union {
        int i;
        uint8_t bytes[sizeof(int)];
    } u = {key};
    
    return hash_fnv1a(u.bytes, sizeof(int));
}

int index = hash_fnv1a_int(42) % 1000;

Преимущества:

• Отличное распределение
• Устойчив к коллизиям
• Используется профессионально

Недостатки:

• Медленнее для простых типов
• Избыточен для простых чисел

7. Практический пример: хеш-таблица

#include <vector>
#include <cstdint>
#include <iostream>

template <typename T>
class SimpleHashTable {
private:
    static const int TABLE_SIZE = 101;  // Простое число
    std::vector<T> table{TABLE_SIZE};
    
    uint32_t hash(int key) const {
        // Используем multiplicative хеширование
        const uint32_t GOLDEN = 2654435761U;
        uint32_t h = static_cast<uint32_t>(key) * GOLDEN;
        return (h >> 16) % TABLE_SIZE;
    }
    
public:
    void insert(int key, const T& value) {
        int index = hash(key);
        table[index] = value;
    }
    
    T* find(int key) {
        int index = hash(key);
        return &table[index];
    }
};

int main() {
    SimpleHashTable<int> ht;
    ht.insert(42, 100);
    ht.insert(123, 200);
    
    auto val = ht.find(42);
    std::cout << "Значение: " << *val << std::endl;
    
    return 0;
}

Рекомендации по выбору

Используй:

• Простую модульную (division) — для начальных проектов, небольших таблиц
• Multiplicative — для production кода с большими таблицами
• FNV-1a — если нужна надёжность и хорошее распределение
• Битовую операцию — если size = 2^k и нужна максимальная скорость

Ключевые свойства хорошей хеш-функции:

1. Детерминированность (одному ключу — один хеш)
2. Равномерное распределение
3. Минимум коллизий
4. Быстрое вычисление
5. Чувствительность к изменениям входных данных

В C++11+ лучше использовать std::hash:

#include <functional>
#include <unordered_map>

std::unordered_map<int, int> map;  // Использует std::hash<int>
map[42] = 100;