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

Примеры хеш-функций для строк в C++

Хеш-функция преобразует строку в уникальное целое число (хеш-код). Рассмотрю различные подходы от простых к production-ready.

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

unsigned long hash_djb2(const std::string& str) {
    unsigned long hash = 5381;
    for (char c : str) {
        hash = ((hash << 5) + hash) + c;  // hash * 33 + c
    }
    return hash;
}

Характеристики:

• Очень быстрая
• Хороша для небольших строк
• Простая в понимании

2. MurmurHash — хорошо для hash-таблиц

#include <cstring>

uint32_t murmur_hash(const std::string& key) {
    const uint32_t c1 = 0xcc9e2d51;
    const uint32_t c2 = 0x1b873593;
    
    uint32_t h1 = 0;
    uint32_t length = key.length();
    const uint8_t* data = (const uint8_t*)key.data();
    
    // Обработка 4-байтовых блоков
    const int nblocks = length / 4;
    for (int i = 0; i < nblocks; ++i) {
        uint32_t k1;
        std::memcpy(&k1, data + i*4, 4);
        
        k1 *= c1;
        k1 = ((k1 << 15) | (k1 >> 17));  // ROTL32
        k1 *= c2;
        
        h1 ^= k1;
        h1 = ((h1 << 13) | (h1 >> 19));
        h1 = h1*5 + 0xe6546b64;
    }
    
    // Обработка оставшихся байт
    const uint8_t* tail = data + nblocks * 4;
    uint32_t k1 = 0;
    
    switch(length & 3) {
        case 3: k1 ^= tail[2] << 16;
        case 2: k1 ^= tail[1] << 8;
        case 1: k1 ^= tail[0];
                k1 *= c1;
                k1 = ((k1 << 15) | (k1 >> 17));
                k1 *= c2;
                h1 ^= k1;
    }
    
    h1 ^= length;
    
    // fmix32
    h1 ^= h1 >> 16;
    h1 *= 0x85ebca6b;
    h1 ^= h1 >> 13;
    h1 *= 0xc2b2ae35;
    h1 ^= h1 >> 16;
    
    return h1;
}

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

• Быстрая, хорошо распределяет значения
• Используется в production системах
• Меньше коллизий

3. Встроенная std::hash (рекомендуется)

#include <functional>
#include <iostream>

int main() {
    std::hash<std::string> hasher;
    std::string str = "hello world";
    
    size_t hash_value = hasher(str);
    std::cout << hash_value << std::endl;
    
    // Или прямо в unordered_map
    std::unordered_map<std::string, int> map;
    map[str] = 42;
    
    return 0;
}

Почему использовать:

• Оптимизирована компилятором
• Часть STL
• Безопасна от timing attacks
• Использует randomization (SipHash) в production GCC/Clang

4. CRC32 для контрольной суммы

#include <cstdint>

uint32_t crc32(const std::string& str) {
    const uint32_t polynomial = 0xEDB88320;
    uint32_t crc = 0xFFFFFFFF;
    
    for (unsigned char byte : str) {
        crc ^= byte;
        for (int i = 0; i < 8; ++i) {
            if (crc & 1) {
                crc = (crc >> 1) ^ polynomial;
            } else {
                crc >>= 1;
            }
        }
    }
    
    return crc ^ 0xFFFFFFFF;
}

Применение: проверка целостности данных, не криптография.

5. SHA-256 для криптографии

#include <openssl/sha.h>
#include <iomanip>
#include <sstream>

std::string sha256(const std::string& str) {
    unsigned char hash[SHA256_DIGEST_LENGTH];
    SHA256((unsigned char*)str.c_str(), str.length(), hash);
    
    std::stringstream ss;
    for(int i = 0; i < SHA256_DIGEST_LENGTH; i++) {
        ss << std::hex << std::setw(2) << std::setfill('0') << (int)hash[i];
    }
    return ss.str();
}

Использование: пароли, токены, проверка целостности.

6. Custom хеш функция для структур

struct Person {
    std::string name;
    int age;
};

struct PersonHash {
    size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ 
               (std::hash<int>()(p.age) << 1);
    }
};

int main() {
    std::unordered_map<Person, std::string, PersonHash> map;
    map[{"Alice", 30}] = "engineer";
    return 0;
}

Выбор хеш-функции

Важные моменты

• Для hash-таблиц (unordered_map): используй std::hash<std::string>
• Для checksums: CRC32
• Для криптографии: SHA-256 или Bcrypt
• Для специализированных случаев: MurmurHash
• Старайся избежать коллизий: хорошая хеш-функция распределяет значения равномерно

Best Practice: всегда используй std::hash и std::unordered_map вместо ручного хеширования, если не требуется специфическое поведение.