Зачем нужна hash функция?

Зачем нужна hash функция

Hash функции — это фундаментальный инструмент в компьютерных науках, используемый в криптографии, структурах данных, проверке целостности и многом другом.

Определение

Hash функция — это математическая функция, которая преобразует входные данные произвольного размера в фиксированный размер вывода (hash):

Hash Function: f(input) → output (fixed size)

Примеры:
f("password123") → "5f4dcc3b5aa765d61d8327deb882cf99" (MD5, 32 символа)
f("hello") → "2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c" (SHA-1, 40 символов)
f(123) → 0x7d58a0... (Java hashCode())

Основные применения

1. HashMap / HashSet (структуры данных)

Hash функция позволяет быстро найти элемент в коллекции:

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, User> userMap = new HashMap<>();
        
        // Сохраняем пользователя
        User user = new User(1, "John");
        userMap.put("john@example.com", user);
        // Внутри HashMap вычисляет hash("john@example.com") → индекс в массиве
        
        // Получаем пользователя (O(1))
        User found = userMap.get("john@example.com");
        // Hash функция быстро находит индекс — очень быстро!
    }
}

Как это работает:

Внутренняя структура HashMap:

Array (capacity = 16):
[0]: null
[1]: [john@example.com → User1] → [alice@example.com → User2]
[2]: null
[3]: [bob@example.com → User3]
...
[15]: null

Когда ищем "john@example.com":
1. Вычисляем hash("john@example.com") = h
2. Индекс = h % capacity = 1
3. Ищем в bucket'е под индексом 1 O(1)

Без hash функции нужно было бы проверить все 16 элементов (O(n))
Средняя сложность: O(1) вместо O(n)

2. Криптографическая безопасность (пароли)

Пароли не хранятся в открытом виде, хранятся hash'и:

@Entity
public class User {
    @Id
    private Long id;
    
    private String username;
    
    @Column
    private String passwordHash;  // Хранится hash, не пароль!
}

@Service
public class AuthService {
    @Autowired
    private PasswordEncoder passwordEncoder;  // использует bcrypt
    
    public void registerUser(String username, String password) {
        // Hash пароля с солью
        String hash = passwordEncoder.encode(password);
        // hash = "$2a$10$N9qo8uLOickgx2ZMRZoMye" (каждый раз разный из-за соли!)
        
        User user = new User();
        user.setUsername(username);
        user.setPasswordHash(hash);
        userRepository.save(user);
    }
    
    public boolean login(String username, String password) {
        User user = userRepository.findByUsername(username);
        
        // Сравниваем hash, а не сам пароль
        return passwordEncoder.matches(password, user.getPasswordHash());
        // matches = хеш пароля == сохранённый хеш
    }
}

Важно: хорошая hash функция обеспечивает:

• Односторонность — невозможно получить оригинальный пароль из hash'а
• Детерминизм — одинаковый вход → одинаковый выход
• Быстрое вычисление — для структур данных
• Сложное обратное вычисление — для криптографии (bcrypt, scrypt)

3. Проверка целостности данных

Hash помогает обнаружить изменения:

// Скачиваем файл с интернета и хотим убедиться, что он не поврежден
public boolean verifyFileIntegrity(File file, String expectedHash) {
    try {
        MessageDigest digest = MessageDigest.getInstance("SHA-256");
        byte[] fileBytes = Files.readAllBytes(file.toPath());
        byte[] hashBytes = digest.digest(fileBytes);
        
        String computedHash = bytesToHex(hashBytes);
        return computedHash.equals(expectedHash);
    } catch (Exception e) {
        throw new RuntimeException(e);
    }
}

Пример: при скачивании ISO образа Linux размер 3GB, website публикует SHA-256:

Оригинальный файл:
SHA-256: a3f9c2b5e1d4...8f7e

После скачивания вычисляем:
SHA-256: a3f9c2b5e1d4...8f7e  ✓ Match!

Если один бит был повреждён:
SHA-256: a3f9c2b5e1d4...8f7d  ✗ Не совпадает!

4. Кэширование и ETAG в HTTP

Web browsers используют hash контента для кэширования:

GET /api/user/1
Response:
ETag: "33a64df551425fcc55e4d42a148795d9f25f89d4"
Cache-Control: max-age=3600

Следующий запрос того же браузера:
GET /api/user/1
If-None-Match: "33a64df551425fcc55e4d42a148795d9f25f89d4"

Если контент не изменился:
Response: 304 Not Modified  (используем кэшированный)

Если изменился:
Response: 200 OK + новый контент + новый ETag

5. Распределённые системы (Consistent Hashing)

В Kafka, Cassandra, Redis используется для распределения данных:

Consistent Hashing для распределения ключей по серверам:

Сервер 1: hash % 3 = 0
Сервер 2: hash % 3 = 1
Сервер 3: hash % 3 = 2

Ключ "user:123"
hash("user:123") = 1234567
1234567 % 3 = 1  → идёт на Сервер 2

Ключ "user:456"
hash("user:456") = 7654321
7654321 % 3 = 0  → идёт на Сервер 1

Виды hash функций

1. Простые hash функции (для HashMap)

public class SimpleHashFunction {
    public static int hash(String s) {
        int hash = 0;
        for (char c : s.toCharArray()) {
            hash = 31 * hash + c;
        }
        return hash;
    }
}

// Java использует похожую функцию в String.hashCode()
// "hello".hashCode() = 99162322

2. Криптографические hash функции

public class CryptoHashExample {
    public static void main(String[] args) throws Exception {
        String password = "mySecurePassword123";
        
        // SHA-256 (быстрая, но не для паролей!)
        MessageDigest sha256 = MessageDigest.getInstance("SHA-256");
        byte[] hash = sha256.digest(password.getBytes());
        System.out.println("SHA-256: " + bytesToHex(hash));
        // Output: 4e388ab...f2e3c (64 символа)
        
        // SHA-512 (медленнее, больше размер)
        MessageDigest sha512 = MessageDigest.getInstance("SHA-512");
        hash = sha512.digest(password.getBytes());
        System.out.println("SHA-512: " + bytesToHex(hash));
        // Output: e3c4a5...f7g2h (128 символов)
    }
}

Важно: SHA-256 для паролей НЕ безопасна! Нужно использовать bcrypt/scrypt/argon2:

public class SecurePasswordHashing {
    public static void main(String[] args) {
        String password = "mySecurePassword123";
        
        // bcrypt (медленная, с солью, защищена от brute-force)
        String bcryptHash = BCrypt.hashpw(password, BCrypt.gensalt());
        System.out.println("bcrypt: " + bcryptHash);
        // Output: $2a$10$N9qo8uLOickgx2ZMRZoMye... (каждый раз разный!)
        
        // Проверка
        boolean matches = BCrypt.checkpw(password, bcryptHash);
        System.out.println("Match: " + matches);  // true
    }
}

3. Content-Addressable Storage (git, IPFS)

В Git каждый коммит идентифицируется по SHA-1 хешу содержимого:

# Git создаёт hash всего содержимого коммита
git log --oneline
# 3d7e4a2 Fix NPE in UserService
# 2c5f1b3 Add caching
# 1a4e0c5 Initial commit

# Hash определяется содержимым
# Если что-то изменить → hash изменится

Свойства хорошей hash функции

1. Детерминизм

String input = "hello";
int hash1 = input.hashCode();  // всегда = 99162322
int hash2 = input.hashCode();  // всегда = 99162322
assert hash1 == hash2;  // true

2. Быстрое вычисление

Для HashMap нужна O(1) скорость:

Map<String, User> map = new HashMap<>();
long start = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) {
    map.get("user_" + i);
}
long end = System.nanoTime();
System.out.println("Time: " + (end - start) / 1_000_000 + " ms");
// Должно быть очень быстро (несколько миллисекунд на 1М операций)

3. Распределение (хорошая diffusion)

Hash должна распределять значения равномерно:

// Плохая hash функция
public int badHash(String s) {
    return s.length();  // Все строки длины 5 будут в одном bucket!
}

// Хорошая hash функция
public int goodHash(String s) {
    int hash = 0;
    for (char c : s.toCharArray()) {
        hash = 31 * hash + c;  // Зависит от каждого символа
    }
    return hash;
}

4. Малые изменения = большие различия (avalanche effect)

Для криптографических функций:

SHA-256("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
SHA-256("hallo") = d3751713b7e2514c54b302bdfb5e16b0157b1213b43b6547cd2db59b2d157fb1

Один символ изменился → hash полностью изменился!

5. Почти непредсказуемая (для криптографии)

// Невозможно предугадать hash без вычисления
String password = "secretPassword123";
String hash = BCrypt.hashpw(password, BCrypt.gensalt());

// Даже если знаешь часть пароля, не сможешь вычислить hash
// (это свойство защищает от dictionary attacks)

Проблемы и решения

Проблема 1: Collision (столкновение)

Два разных входа дают одинаковый hash:

// Плохая hash функция
int hash1 = "hello".hashCode() % 100;  // может быть = 42
int hash2 = "world".hashCode() % 100;  // может быть = 42  (столкновение!)

// HashMap решает через chaining или open addressing
Array[42]: ["hello" → value1] → ["world" → value2]

Проблема 2: Hash DoS Attack

Атакующий специально создаёт значения с одинаковым hash'ем:

// HashMap замедляется с O(1) до O(n) при многих столкновениях
Map<String, String> map = new HashMap<>();
for (int i = 0; i < 1000000; i++) {
    // Злоумышленник создаёт строки с одинаковым hash
    map.put("key_" + i, "value");
    // Вставка становится медленной!
}

// Решение: Java использует RandomizedStringHashing
// Хеш для строк зависит от случайного seed

Java examples из реальной жизни

// Хеширование для deduplication
Set<String> uniqueEmails = new HashSet<>();  // Использует hash

// Кэширование результатов (memoization)
Map<List<Integer>, Integer> memo = new HashMap<>();
public int fibonacci(List<Integer> params) {
    if (memo.containsKey(params)) {
        return memo.get(params);  // Hash позволяет быстро найти
    }
    // ... вычисления
}

// Object.hashCode() и equals()
public class User {
    private String email;
    
    @Override
    public int hashCode() {
        return email.hashCode();
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User user = (User) o;
        return Objects.equals(email, user.email);
    }
}

Заключение

Hash функции — это один из самых фундаментальных инструментов в программировании:

• HashMap/HashSet — быстрые структуры данных
• Пароли — безопасное хранение (bcrypt, scrypt)
• Проверка целостности — обнаружение повреждений
• Кэширование — быстрый доступ
• Распределённые системы — балансировка нагрузки

Golden Rule: использоват правильную hash функцию для правильной задачи!

• Структуры данных: быстрая (O(1))
• Пароли: медленная + соль (bcrypt, argon2)
• Проверка целостности: криптографическая (SHA-256, SHA-512)