Приведи пример использования хеширования

# Хеширование в Java - примеры использования

Определение

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

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

1. HashMap и HashSet - быстрый поиск

Одно из самых частых применений хеширования в Java.

// HashMap использует хеширование для O(1) поиска
public class UserService {
    private Map<String, User> userCache = new HashMap<>();
    
    public void cacheUser(String email, User user) {
        userCache.put(email, user);  // Хеш email для быстрого сохранения
    }
    
    public User findUser(String email) {
        return userCache.get(email);  // Хеш email для быстрого поиска O(1)
    }
}

// HashSet для быстрой проверки наличия элемента
Set<String> bannedEmails = new HashSet<>();
bannedEmails.add("spam@example.com");

if (bannedEmails.contains(email)) {  // O(1) вместо O(n)
    System.out.println("Email забанен");
}

2. equals() и hashCode() контракт

Любой объект в Java должен иметь правильную реализацию hashCode():

public class User {
    private String email;
    private String name;
    
    // ✓ Правильная реализация
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        User user = (User) obj;
        return Objects.equals(email, user.email) && 
               Objects.equals(name, user.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(email, name);
    }
}

// Использование в HashMap
Map<User, String> map = new HashMap<>();
User user1 = new User("john@example.com", "John");
User user2 = new User("john@example.com", "John");

map.put(user1, "value1");
User found = map.get(user2);  // Находит правильно благодаря hashCode()
// user1.hashCode() == user2.hashCode() && user1.equals(user2)

3. Пароли и безопасность

Хеширование используется для безопасного хранения паролей:

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

public class AuthService {
    private final BCryptPasswordEncoder encoder = new BCryptPasswordEncoder();
    
    // Регистрация
    public void register(String password) {
        String hashedPassword = encoder.encode(password);
        // Сохраняем hashedPassword в БД
        // Оригинальный пароль забывается
        userRepository.save(new User(hashedPassword));
    }
    
    // Вход
    public boolean authenticate(String inputPassword, String storedHash) {
        // Сравнивают хеши, а не оригинальные пароли
        return encoder.matches(inputPassword, storedHash);
    }
}

// Пример с SHA-256
import java.security.MessageDigest;
import java.util.Base64;

public class PasswordHasher {
    public String hashPassword(String password) throws Exception {
        MessageDigest digest = MessageDigest.getInstance("SHA-256");
        byte[] hash = digest.digest(password.getBytes());
        return Base64.getEncoder().encodeToString(hash);
    }
}

4. Проверка целостности файлов

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

import java.security.MessageDigest;
import java.nio.file.Files;
import java.nio.file.Paths;

public class FileIntegrityChecker {
    
    public String calculateFileHash(String filePath) throws Exception {
        MessageDigest digest = MessageDigest.getInstance("SHA-256");
        byte[] fileData = Files.readAllBytes(Paths.get(filePath));
        byte[] hash = digest.digest(fileData);
        return bytesToHex(hash);
    }
    
    public boolean verifyFileIntegrity(String filePath, String expectedHash) 
            throws Exception {
        String actualHash = calculateFileHash(filePath);
        return actualHash.equals(expectedHash);
    }
    
    private String bytesToHex(byte[] bytes) {
        StringBuilder sb = new StringBuilder();
        for (byte b : bytes) {
            sb.append(String.format("%02x", b));
        }
        return sb.toString();
    }
}

// Использование
FileIntegrityChecker checker = new FileIntegrityChecker();
String hash = checker.calculateFileHash("/path/to/file.zip");
if (checker.verifyFileIntegrity("/path/to/file.zip", hash)) {
    System.out.println("Файл не изменён");
}

5. Кэширование вычислений

Хеш входных параметров используется как ключ кэша:

public class ExpensiveCalculationService {
    private Map<Integer, Long> cache = new HashMap<>();
    
    public long fibonacci(int n) {
        // Используем n как ключ (его хеш)
        if (cache.containsKey(n)) {
            return cache.get(n);  // Возвращаем закэшированный результат
        }
        
        long result;
        if (n <= 1) {
            result = n;
        } else {
            result = fibonacci(n - 1) + fibonacci(n - 2);
        }
        
        cache.put(n, result);  // Сохраняем в кэш
        return result;
    }
}

// Более сложный пример с несколькими параметрами
public class ApiResponseCache {
    private Map<Integer, ApiResponse> cache = new HashMap<>();
    
    public ApiResponse fetchWithCache(String userId, String resourceId) {
        int key = Objects.hash(userId, resourceId);  // Хеш обоих параметров
        
        return cache.computeIfAbsent(key, k -> {
            // Вычисляется только если ключа нет в кэше
            return fetchFromApi(userId, resourceId);
        });
    }
}

6. Распределённое хеширование (Consistent Hashing)

Для распределения данных по нескольким серверам:

public class ConsistentHashRing {
    private TreeMap<Integer, String> ring = new TreeMap<>();
    private final int virtualNodes = 3;
    
    public void addNode(String node) {
        for (int i = 0; i < virtualNodes; i++) {
            int hash = hashFunction(node + ":" + i);
            ring.put(hash, node);
        }
    }
    
    public String getNode(String key) {
        if (ring.isEmpty()) return null;
        int hash = hashFunction(key);
        
        Map.Entry<Integer, String> entry = ring.ceilingEntry(hash);
        if (entry == null) {
            entry = ring.firstEntry();
        }
        return entry.getValue();
    }
    
    private int hashFunction(String key) {
        return Math.abs(key.hashCode());
    }
}

// Использование для распределения кэша по серверам
ConsistentHashRing ring = new ConsistentHashRing();
ring.addNode("cache-server-1");
ring.addNode("cache-server-2");
ring.addNode("cache-server-3");

String node = ring.getNode("user:123");  // Определит нужный сервер

7. Дедупликация данных

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

public class DuplicateDetector {
    private Set<Integer> hashes = new HashSet<>();
    
    public boolean isDuplicate(byte[] data) {
        int hash = Arrays.hashCode(data);
        if (hashes.contains(hash)) {
            return true;  // Вероятно, это дубликат
        }
        hashes.add(hash);
        return false;
    }
}

// Для файлов
public class FileDeduplicator {
    private Map<String, String> fileHashes = new HashMap<>();
    
    public void processFile(String filePath) throws Exception {
        String hash = calculateFileHash(filePath);
        
        if (fileHashes.containsValue(hash)) {
            System.out.println("Файл " + filePath + " уже обработан");
            return;
        }
        fileHashes.put(filePath, hash);
        // Обработка файла
    }
}

8. Гиперсистема - вероятностная проверка

Для экономии памяти при проверке наличия элемента:

import java.util.BitSet;

public class BloomFilter {
    private BitSet bitSet;
    private int size;
    private int numHashFunctions = 3;
    
    public BloomFilter(int size) {
        this.size = size;
        this.bitSet = new BitSet(size);
    }
    
    public void add(String element) {
        for (int i = 0; i < numHashFunctions; i++) {
            int hash = hashFunction(element + i) % size;
            bitSet.set(hash);
        }
    }
    
    public boolean contains(String element) {
        for (int i = 0; i < numHashFunctions; i++) {
            int hash = hashFunction(element + i) % size;
            if (!bitSet.get(hash)) {
                return false;  // Точно не содержит
            }
        }
        return true;  // Вероятно содержит (может быть false positive)
    }
    
    private int hashFunction(String key) {
        return Math.abs(key.hashCode());
    }
}

// Использование для списка спама/блокировки
BloomFilter spamFilter = new BloomFilter(100000);
spamFilter.add("spam@example.com");
if (spamFilter.contains("email@example.com")) {
    // Возможно в спаме (может быть false positive)
}

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

// 1. hashCode() - объектов Java
int hash = "hello".hashCode();

// 2. MessageDigest - криптографические
MessageDigest digest = MessageDigest.getInstance("SHA-256");
byte[] hash = digest.digest("hello".getBytes());

// 3. MurmurHash - быстрый, не криптографический
// com.google.guava:guava
int hash = Hashing.murmur3_32().hashString("hello", StandardCharsets.UTF_8).asInt();

// 4. CRC32 - для проверки целостности
import java.util.zip.CRC32;
CRC32 crc = new CRC32();
crc.update("hello".getBytes());
long hash = crc.getValue();

Заключение

Хеширование — это фундаментальная техника в программировании:

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

• HashMap/HashSet для быстрого поиска O(1)
• equals()/hashCode() контракт для правильной работы коллекций
• Безопасное хранение паролей (BCrypt, SHA-256)
• Проверка целостности данных и файлов
• Кэширование вычислений
• Распределённые системы (consistent hashing)
• Дедупликация данных
• Вероятностные структуры (Bloom Filter)

Помни:

• Хорошая хеш-функция распределяет данные равномерно
• Для безопасности используй криптографические хеши (SHA-256, BCrypt)
• Для производительности используй быстрые хеши (murmur3, CRC32)