Как сломать HashMap

Как сломать HashMap: потенциальные проблемы и атаки

HashMap — мощная структура данных, но её можно "сломать" несколькими способами. Знание этих уязвимостей критично для написания безопасного кода.

1. Hash Collision Attack (DoS атака)

Проблема: Если хеш-функция генерирует одинаковые хеши для разных значений, HashMap превращается в список.

// Худший случай: все элементы с одинаковым хешем
HashMap<String, Integer> map = new HashMap<>();

// Создаём объекты с одинаковым хешем
class BadHash {
    @Override
    public int hashCode() {
        return 42; // ВСЕ коллизии!
    }
    
    @Override
    public boolean equals(Object obj) {
        return obj instanceof BadHash;
    }
}

// Вставляем 10000 элементов
for (int i = 0; i < 10000; i++) {
    map.put(new BadHash(), i);
}

// Поиск вырождается в O(n) вместо O(1)
// CPU использование скачёт до 100%
long start = System.currentTimeMillis();
map.get(new BadHash()); // Может занять секунды!
System.out.println(System.currentTimeMillis() - start);

Решение: Java 8+ использует Red-Black Tree при количестве коллизий > 8, что ограничивает O(n) до O(log n).

2. Нарушение контракта hashCode/equals

Проблема: Если hashCode() меняется после добавления в HashMap, элемент становится недостижимым.

public class User {
    private String name;
    private int age;
    
    // ПЛОХО: hashCode зависит от mutable поля
    @Override
    public int hashCode() {
        return name.hashCode() + age;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof User)) return false;
        User other = (User) obj;
        return this.name.equals(other.name) && this.age == other.age;
    }
}

// Демонстрация проблемы
HashMap<User, String> map = new HashMap<>();
User user = new User("John", 30);
map.put(user, "Developer");

// Меняем поле - hashCode меняется!
user.age = 31;

// Не сможем найти!
System.out.println(map.get(user)); // null
System.out.println(map.containsKey(user)); // false

// Но элемент всё ещё в памяти!
System.out.println(map.size()); // 1
System.out.println(map.values()); // [Developer]

Правильно: используй immutable поля или делай hashCode на основе immutable fields

public class User {
    private final String id; // immutable ID
    private String name;
    private int age;
    
    @Override
    public int hashCode() {
        return id.hashCode(); // На основе immutable
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof User)) return false;
        User other = (User) obj;
        return this.id.equals(other.id);
    }
}

3. Thread-safety проблемы

HashMap НЕ thread-safe! Может привести к infinite loop.

HashMap<String, Integer> map = new HashMap<>();

// Поток 1: вставляет элементы
new Thread(() -> {
    for (int i = 0; i < 1000000; i++) {
        map.put("key" + i, i);
    }
}).start();

// Поток 2: читает элементы
new Thread(() -> {
    while (true) {
        for (String key : map.keySet()) {
            System.out.println(key); // ConcurrentModificationException
        }
    }
}).start();

// Результат: исключение или infinite loop

Решение: используй ConcurrentHashMap для многопоточных приложений

Map<String, Integer> map = new ConcurrentHashMap<>();

// Теперь безопасно из нескольких потоков
map.put("key", 1);
map.get("key");

4. Memory Leak через статический HashMap

public class CacheManager {
    // ПЛОХО: статический HashMap растёт без контроля
    private static final HashMap<String, byte[]> CACHE = new HashMap<>();
    
    public static void cache(String key, byte[] data) {
        CACHE.put(key, data); // Никогда не удаляется!
    }
}

// Использование
while (true) {
    byte[] hugeData = new byte[1024 * 1024]; // 1MB
    CacheManager.cache("key" + System.nanoTime(), hugeData);
    // OutOfMemoryError через некоторое время!
}

Решение: используй LinkedHashMap с LRU политикой или WeakHashMap

public class LRUCache extends LinkedHashMap<String, byte[]> {
    private final int maxSize;
    
    public LRUCache(int maxSize) {
        super(16, 0.75f, true); // true = access-order
        this.maxSize = maxSize;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > maxSize; // Удаляем старые элементы
    }
}

Map<String, byte[]> cache = new LRUCache(100);
cache.put("key", data); // Максимум 100 элементов

5. Equals/HashCode inconsistency

public class Product {
    private String name;
    private double price;
    
    // ПЛОХО: равные объекты имеют разные хеши
    @Override
    public int hashCode() {
        return name.hashCode();
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Product)) return false;
        Product other = (Product) obj;
        // Используем ОБА поля для equals
        return this.name.equals(other.name) && 
               Double.compare(this.price, other.price) == 0;
    }
}

// Ломается HashMap
HashMap<Product, String> map = new HashMap<>();
Product p1 = new Product("Apple", 1.5);
Product p2 = new Product("Apple", 2.5);

map.put(p1, "cheap");
map.put(p2, "expensive");

// Оба с одинаковым хешем, но разные equals
System.out.println(map.size()); // 2, но это может привести к проблемам

6. Null handling

HashMap<String, Integer> map = new HashMap<>();

// HashMap позволяет одну null ключ и null значения
map.put(null, 1);
map.put("key", null);
map.put(null, 2); // Перезаписывает первый

System.out.println(map.get(null)); // 2
System.out.println(map.size()); // 2

// Но это может вызвать проблемы в других Map реализациях
// TreeMap кинет NullPointerException если ключ null
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put(null, 1); // NullPointerException!

7. Resize аномалии

// HashMap автоматически увеличивает размер
HashMap<String, Integer> map = new HashMap<>(2); // Начальный размер 2

map.put("a", 1);
map.put("b", 2); // Дошли до load factor 0.75, resize происходит
map.put("c", 3); // Может быть медленнее из-за rehashing

// В многопоточной среде resize может привести к deadlock или data loss

Правила для безопасного использования HashMap

public class SafeHashMapUsage {
    // 1. Правильный hashCode/equals contract
    @Override
    public int hashCode() {
        return Objects.hash(immutableField1, immutableField2);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof SafeHashMapUsage)) return false;
        SafeHashMapUsage other = (SafeHashMapUsage) obj;
        return Objects.equals(this.immutableField1, other.immutableField1) &&
               Objects.equals(this.immutableField2, other.immutableField2);
    }
    
    // 2. Не меняй объекты после добавления в HashMap
    // 3. Для многопоточности используй ConcurrentHashMap
    // 4. Для кэша используй LinkedHashMap с размер лимитом
    // 5. Не полагайся на то что null работает везде
    // 6. Избегай huge HashMaps (> 100M элементов)
}

Результат неправильного использования

• O(1) становится O(n)
• Элементы становятся недостижимыми
• ConcurrentModificationException
• OutOfMemoryError
• InfiniteLoop в resize коде
• Data corruption в многопоточной среде

Знание этих проблем — ключ к написанию надёжного Java кода.