Что такое хэш-функция?

Хэш-функция

Хэш-функция (Hash Function) — это математическая функция, которая преобразует входные данные произвольного размера в выходное значение фиксированного размера, называемое хэшем или хэш-кодом. Хэш-функции являются фундаментальной частью информатики и используются в таких приложениях, как хэш-таблицы, цифровые подписи и проверка целостности данных.

Основные свойства хэш-функции

1. Детерминированность

Одинаковые входные данные всегда производят одинаковый выход:

String text = "hello";
int hash1 = text.hashCode();  // Всегда одно и то же значение
int hash2 = text.hashCode();
assert hash1 == hash2;  // Гарантировано верно

2. Скорость вычисления

Хэш должен вычисляться быстро, независимо от размера входных данных.

3. Распределение

Хэши должны быть равномерно распределены по диапазону выходных значений.

4. Чувствительность

Маленькое изменение входа должно радикально изменить выход:

String s1 = "password";
String s2 = "passworf";  // Только один символ отличается

System.out.println(s1.hashCode());  // -1424385949
System.out.println(s2.hashCode());  //  1424385959
// Совершенно разные хэши!

Применение хэш-функций в Java

1. HashMap и HashSet (хэш-таблицы)

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // Внутри HashMap использует hashCode() для определения бакета
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);
        
        // Быстрый поиск за O(1) благодаря хэшированию
        Integer age = map.get("Alice");  // O(1) в среднем
    }
}

Внутри HashMap работает примерно так:

ключ "Alice" -> hashCode() -> 2142 -> бакет 2142 % 16 = 6 -> найти значение

2. Переопределение hashCode() в собственных классах

public class User {
    private String name;
    private int age;
    
    @Override
    public int hashCode() {
        // Хороший хэш-код должен включать все значимые поля
        return java.util.Objects.hash(name, age);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof User)) return false;
        
        User other = (User) obj;
        return age == other.age && 
               java.util.Objects.equals(name, other.name);
    }
}

public class Main {
    public static void main(String[] args) {
        HashMap<User, String> userMap = new HashMap<>();
        User user = new User("Alice", 25);
        
        userMap.put(user, "Engineering");
        System.out.println(userMap.get(new User("Alice", 25)));  // Engineering
    }
}

Важное правило: если переопределяете equals(), ОБЯЗАТЕЛЬНО переопределяйте hashCode()!

// НЕПРАВИЛЬНО
public class BadExample {
    private String id;
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof BadExample)) return false;
        return id.equals(((BadExample) obj).id);
    }
    // hashCode() не переопределён!
}

// Результат: HashMap может не найти объект
BadExample obj = new BadExample("123");
map.put(obj, "value");
map.get(obj);  // Может вернуть null!

3. Хэширование паролей (криптографическое)

import java.security.MessageDigest;
import java.util.Base64;

public class PasswordHasher {
    public static String hashPassword(String password) throws Exception {
        // SHA-256 это криптографическая хэш-функция
        MessageDigest digest = MessageDigest.getInstance("SHA-256");
        byte[] hash = digest.digest(password.getBytes());
        
        // Конвертируем в Base64 для удобства
        return Base64.getEncoder().encodeToString(hash);
    }
    
    public static void main(String[] args) throws Exception {
        String password = "mySecurePassword";
        String hashedPassword = hashPassword(password);
        
        System.out.println("Оригинал: " + password);
        System.out.println("Хэш: " + hashedPassword);
        
        // Проверка пароля
        String inputPassword = "mySecurePassword";
        String inputHash = hashPassword(inputPassword);
        
        if (inputHash.equals(hashedPassword)) {
            System.out.println("Пароль верный!");
        }
    }
}

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

import java.security.MessageDigest;

public class FileIntegrityChecker {
    public static String calculateFileHash(byte[] fileContent) throws Exception {
        MessageDigest digest = MessageDigest.getInstance("SHA-256");
        byte[] hash = digest.digest(fileContent);
        
        // Преобразуем в hex-строку
        StringBuilder hexString = new StringBuilder();
        for (byte b : hash) {
            String hex = Integer.toHexString(0xff & b);
            if (hex.length() == 1) hexString.append('0');
            hexString.append(hex);
        }
        return hexString.toString();
    }
    
    public static void main(String[] args) throws Exception {
        byte[] originalFile = "Important data".getBytes();
        String originalHash = calculateFileHash(originalFile);
        
        // Позже проверяем, не был ли файл изменён
        byte[] receivedFile = "Important data".getBytes();
        String receivedHash = calculateFileHash(receivedFile);
        
        if (originalHash.equals(receivedHash)) {
            System.out.println("Файл не повреждён!");
        } else {
            System.out.println("Файл был изменён!");
        }
    }
}

Типы хэш-функций

1. Простые хэш-функции (для таблиц)

Используются для распределения данных в структурах типа HashMap:

public class SimpleHash {
    public static int hash(String key, int tableSize) {
        return Math.abs(key.hashCode()) % tableSize;
    }
}

2. Криптографические хэш-функции

Используются для безопасности (SHA-256, SHA-512, MD5):

Место использования: пароли, цифровые подписи, проверка целостности
Особенность: практически невозможно найти коллизию

Проблемы хэш-функций

1. Коллизии (Collisions)

Два разных входа производят один и тот же хэш:

"hello" -> 12345
"world" -> 12345  // Коллизия!

В HashMap коллизии решаются через цепочки (chaining):

Бакет 5: [Key1->Value1] -> [Key2->Value2] -> [Key3->Value3]

2. Load Factor

Когда HashMap становится переполненной, она увеличивает размер (rehashing):

HashMap<String, String> map = new HashMap<>();
// По умолчанию capacity = 16, load factor = 0.75
// Когда 12 элементов (16 * 0.75), размер увеличится до 32

Сравнение хэш-функций

Лучшие практики

✅ Делайте:

• Переопределяйте hashCode() и equals() вместе
• Используйте Objects.hash() для удобства
• Используйте SHA-256 или лучше для паролей
• Используйте salt при хешировании паролей

❌ Не делайте:

• Не полагайтесь на hashCode() для безопасности
• Не модифицируйте поля объекта после добавления в HashMap
• Не используйте MD5 для паролей
• Не игнорируйте коллизии в собственных хэш-таблицах

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