PrepBro
← Назад к вопросам

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

1.8 Middle🔥 131 комментариев
#SOLID и паттерны проектирования#Spring Boot и Spring Data

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Хеш-функция

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

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

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

Одинаковые входные данные всегда дают одинаковый хеш:

public class HashFunctionDemo {
    public static void main(String[] args) {
        String input = "Hello";
        
        int hash1 = input.hashCode();
        int hash2 = input.hashCode();
        
        System.out.println(hash1 == hash2); // true
    }
}

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

Хеш должен вычисляться за O(1) время:

String s = "very_long_string_".repeat(1000);
long start = System.nanoTime();
int hash = s.hashCode(); // Быстро, независимо от длины
long elapsed = System.nanoTime() - start;
System.out.println("Time: " + elapsed + " ns");

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

Разные входные данные должны давать хорошо распределённые значения хеша (минимизировать коллизии).

4. Изменчивость

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

String s1 = "Hello";
String s2 = "hello"; // Один символ изменился

System.out.println(s1.hashCode()); // Различные значения
System.out.println(s2.hashCode());

Хеш-функции в Java

1. Object.hashCode()

Базовый метод для всех объектов:

public class CustomObject {
    private String name;
    private int age;
    
    public CustomObject(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int hashCode() {
        // Простая реализация
        return name.hashCode() * 31 + age;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof CustomObject)) return false;
        CustomObject other = (CustomObject) obj;
        return this.name.equals(other.name) && 
               this.age == other.age;
    }
}

// Использование
CustomObject obj1 = new CustomObject("John", 25);
CustomObject obj2 = new CustomObject("John", 25);

System.out.println(obj1.hashCode() == obj2.hashCode()); // true
System.out.println(obj1.equals(obj2)); // true

2. String.hashCode()

Для строк использует алгоритм:

public class StringHashExample {
    public static void main(String[] args) {
        // Строки с одинаковым содержимым имеют одинаковый хеш
        String s1 = "Hello";
        String s2 = new String("Hello");
        
        System.out.println(s1.hashCode()); // Одинаковое
        System.out.println(s2.hashCode()); // Одинаковое
        
        // Небольшое изменение дает разный хеш
        System.out.println("Hello".hashCode());  // Один хеш
        System.out.println("hello".hashCode()); // Другой хеш
    }
}

Внутренняя реализация String.hashCode():

// Примерная реализация (упрощённо)
public int hashCode() {
    int hash = 0;
    for (char c : this.toCharArray()) {
        hash = 31 * hash + c; // 31 — простое число
    }
    return hash;
}

Коллизии хеша

Коллизия — когда разные входные данные дают одинаковый хеш:

public class HashCollisionExample {
    public static void main(String[] args) {
        // Пример простой хеш-функции с коллизиями
        String[] words = {"AB", "BA", "hello"};
        
        for (String word : words) {
            // Простая функция: сумма кодов символов
            int hash = word.chars().sum() % 10;
            System.out.println(word + ": " + hash);
        }
        // "AB" и "BA" дадут одинаковый хеш (коллизия!)
    }
}

Хеширование и HashMap

import java.util.HashMap;

public class HashMapDemo {
    public static void main(String[] args) {
        // HashMap использует хеш-функцию для быстрого доступа
        HashMap<String, Integer> map = new HashMap<>();
        
        map.put("apple", 5);
        map.put("banana", 3);
        map.put("cherry", 8);
        
        // Поиск за O(1) благодаря хешированию
        System.out.println(map.get("apple")); // 5
    }
}

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

  1. При вставке: key.hashCode() вычисляет индекс бакета
  2. Если коллизия: элементы хранятся в связном списке (или дереве)
  3. При поиске: вычисляется хеш, находится бакет, затем сравниваются ключи
public class HashMapInternals {
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>();
        
        // Вставка
        map.put(1, "One");   // hash(1) → индекс в таблице
        map.put(11, "Eleven"); // hash(11) может совпасть с hash(1)
        
        // Поиск
        String value = map.get(1); // Быстро благодаря хешу
    }
}

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

Для безопасности используются специальные функции:

import java.security.MessageDigest;
import java.util.Arrays;

public class CryptographicHashExample {
    
    // MD5 (устаревшая, не используй для безопасности)
    public static String md5(String input) throws Exception {
        MessageDigest md = MessageDigest.getInstance("MD5");
        byte[] hash = md.digest(input.getBytes());
        return Arrays.toString(hash);
    }
    
    // SHA-256 (рекомендуется)
    public static String sha256(String input) throws Exception {
        MessageDigest md = MessageDigest.getInstance("SHA-256");
        byte[] hash = md.digest(input.getBytes());
        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 {
        String password = "mypassword";
        String hashed = sha256(password);
        System.out.println("SHA-256: " + hashed);
        // Результат: длинная строка из 64 символов
    }
}

BCrypt для хеширования паролей

import org.springframework.security.crypto.bcrypt.BCryptPasswordEncoder;

public class BCryptExample {
    public static void main(String[] args) {
        BCryptPasswordEncoder encoder = new BCryptPasswordEncoder();
        
        String password = "myPassword123";
        String hashed = encoder.encode(password);
        
        System.out.println("Original: " + password);
        System.out.println("Hashed: " + hashed);
        
        // Проверка пароля
        boolean matches = encoder.matches(password, hashed);
        System.out.println("Matches: " + matches); // true
    }
}

Правильная реализация hashCode() и equals()

import java.util.Objects;

public class Person {
    private String name;
    private int age;
    private String email;
    
    public Person(String name, int age, String email) {
        this.name = name;
        this.age = age;
        this.email = email;
    }
    
    // ❌ Старый способ
    @Override
    public int hashCode() {
        return name.hashCode() * 31 + age;
    }
    
    // ✅ Лучший способ (Java 7+)
    @Override
    public int hashCode() {
        return Objects.hash(name, age, email);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;              // Оптимизация
        if (!(obj instanceof Person)) return false; // Проверка типа
        
        Person other = (Person) obj;
        return Objects.equals(this.name, other.name) &&
               this.age == other.age &&
               Objects.equals(this.email, other.email);
    }
}

// Использование
public class PersonTest {
    public static void main(String[] args) {
        Person p1 = new Person("John", 25, "john@example.com");
        Person p2 = new Person("John", 25, "john@example.com");
        
        System.out.println(p1.equals(p2));        // true
        System.out.println(p1.hashCode() == p2.hashCode()); // true
        
        // Работает с HashSet
        HashSet<Person> set = new HashSet<>();
        set.add(p1);
        set.add(p2); // p2 не будет добавлен (дубликат)
        System.out.println(set.size()); // 1
    }
}

Хеш-функции для контрольных сумм

import java.util.zip.CRC32;
import java.util.zip.Checksum;

public class ChecksumExample {
    public static void main(String[] args) {
        String data = "Hello, World!";
        byte[] bytes = data.getBytes();
        
        // CRC32 для проверки целостности
        Checksum checksum = new CRC32();
        checksum.update(bytes, 0, bytes.length);
        long crcValue = checksum.getValue();
        
        System.out.println("CRC32: " + crcValue);
    }
}

Распространённые хеш-функции

ФункцияРазмерПрименениеБезопасность
hashCode()32 bitКоллекции JavaНизкая
SHA-1160 bitКонтроль версийСлабая
SHA-256256 bitКриптографияВысокая
SHA-512512 bitКриптографияВысокая
MD5128 bitКонтрольные суммыВзломана
BCryptVariableПаролиВысокая

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

  1. Всегда переопредели hashCode() и equals() вместе
  2. Используй Objects.hash() для простоты
  3. Не используй MD5 для безопасности
  4. Используй BCrypt или PBKDF2 для паролей
  5. Помни о коллизиях при выборе функции
  6. Тестируй распределение хешей

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

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