Что такое коллизия hashCode в HashSet?

Коллизия hashCode в HashSet

Коллизия hashCode (Hash Collision) — это ситуация, когда два разных объекта возвращают одинаковое значение hashCode(). Это нормальное явление в хеш-таблицах, и HashSet использует специальные механизмы (chaining) для обработки коллизий. Однако неправильная реализация hashCode() может привести к деградации производительности.

Основная концепция hashCode

Что такое hashCode:

public class HashCodeBasics {
    public static void main(String[] args) {
        String str1 = "Hello";
        String str2 = "Hello";
        String str3 = "World";
        
        // hashCode должен быть одинаковым для одинаковых объектов
        System.out.println(str1.hashCode());  // 69609650
        System.out.println(str2.hashCode());  // 69609650 (одинаково)
        System.out.println(str3.hashCode());  // 83766130 (другое)
        
        // HashCode используется для определения bucket в HashSet
    }
}

Как HashSet использует hashCode:

public class HashSetBucketExample {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        
        // Когда добавляем элемент:
        // 1. Вычисляется hashCode()
        // 2. hashCode преобразуется в индекс bucket (обычно: hashCode % capacity)
        // 3. Объект добавляется в bucket
        
        set.add("Apple");   // hashCode = 63272711, bucket = 3
        set.add("Banana");  // hashCode = 1871055323, bucket = 7
        set.add("Cherry");  // hashCode = 65595098, bucket = 2
        
        // HashSet может выглядеть так:
        // Bucket 0: []
        // Bucket 1: []
        // Bucket 2: [Cherry]
        // Bucket 3: [Apple]
        // Bucket 4: []
        // Bucket 5: []
        // Bucket 6: []
        // Bucket 7: [Banana]
    }
}

Коллизии hashCode

Идеальная ситуация - нет коллизий:

public class NoCollisionExample {
    public static void main(String[] args) {
        // Хорошая реализация hashCode избегает коллизий
        Set<User> users = new HashSet<>();
        
        User user1 = new User(1, "John");
        User user2 = new User(2, "Jane");
        User user3 = new User(3, "Bob");
        
        users.add(user1); // hashCode = 1, bucket = 1
        users.add(user2); // hashCode = 2, bucket = 2
        users.add(user3); // hashCode = 3, bucket = 3
        
        // Все объекты в разных buckets -> O(1) поиск
    }
    
    static class User {
        int id;
        String name;
        
        User(int id, String name) {
            this.id = id;
            this.name = name;
        }
        
        @Override
        public int hashCode() {
            return id; // Хорошо распределённый hash
        }
        
        @Override
        public boolean equals(Object o) {
            if (!(o instanceof User)) return false;
            User user = (User) o;
            return id == user.id && Objects.equals(name, user.name);
        }
    }
}

Плохая ситуация - много коллизий:

public class CollisionExample {
    public static void main(String[] args) {
        Set<Person> persons = new HashSet<>();
        
        Person p1 = new Person("Alice");
        Person p2 = new Person("Bob");
        Person p3 = new Person("Charlie");
        
        persons.add(p1); // hashCode = 0, bucket = 0
        persons.add(p2); // hashCode = 0, bucket = 0 (коллизия!)
        persons.add(p3); // hashCode = 0, bucket = 0 (ещё коллизия!)
        
        // HashSet теперь выглядит так:
        // Bucket 0: [p1, p2, p3] <- все в одном bucket!
        // Bucket 1: []
        // Bucket 2: []
        // ...
        // Bucket 15: []
        
        // Поиск теперь O(n) вместо O(1)!
    }
    
    static class Person {
        String name;
        
        Person(String name) {
            this.name = name;
        }
        
        @Override
        public int hashCode() {
            return 0;  // ПЛОХО! Все объекты имеют одинаковый hash
        }
        
        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Person)) return false;
            Person p = (Person) o;
            return Objects.equals(name, p.name);
        }
    }
}

Механизм разрешения коллизий - Chaining

Как HashSet обрабатывает коллизии:

public class ChainingExample {
    
    // Упрощённая реализация Hash Table с chaining
    class SimplHashSet<E> {
        private LinkedList<E>[] buckets;
        private int capacity = 16;
        
        @SuppressWarnings("unchecked")
        public SimplHashSet() {
            buckets = new LinkedList[capacity];
            for (int i = 0; i < capacity; i++) {
                buckets[i] = new LinkedList<>();
            }
        }
        
        public void add(E element) {
            int hash = element.hashCode();
            int index = Math.abs(hash % capacity);
            
            LinkedList<E> chain = buckets[index];
            
            // Проверяем, есть ли уже такой элемент в chain
            for (E e : chain) {
                if (e.equals(element)) {
                    return; // Дубликат, не добавляем
                }
            }
            
            // Добавляем в конец chain (O(1) для LinkedList)
            chain.add(element);
        }
        
        public boolean contains(E element) {
            int hash = element.hashCode();
            int index = Math.abs(hash % capacity);
            
            LinkedList<E> chain = buckets[index];
            
            // Проходим по chain для поиска (O(k) где k - длина chain)
            for (E e : chain) {
                if (e.equals(element)) {
                    return true;
                }
            }
            
            return false;
        }
    }
    
    public static void main(String[] args) {
        SimplHashSet<String> set = new SimplHashSet<>();
        
        // Добавляем элементы
        set.add("Apple");   // hash=63272711, index=7
        set.add("Apricot"); // hash=1302754, index=14 (коллизия с Apple!)
        set.add("Avocado"); // hash=1302754, index=14 (коллизия с Apricot!)
        
        // Bucket 14 содержит chain: [Apricot, Avocado]
        // Поиск "Apricot" требует прохода по chain
    }
}

Потенциальные проблемы

1. Плохое распределение хешей - Performance degradation:

public class BadHashDistribution {
    
    static class Product {
        int id;
        String name;
        
        Product(int id, String name) {
            this.id = id;
            this.name = name;
        }
        
        @Override
        public int hashCode() {
            // ПЛОХО: Только используем id % 10, много коллизий
            return id % 10;
        }
        
        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Product)) return false;
            Product p = (Product) o;
            return id == p.id && Objects.equals(name, p.name);
        }
    }
    
    public static void main(String[] args) {
        Set<Product> products = new HashSet<>();
        
        // Все числа кратные 10 будут в одном bucket
        for (int i = 0; i < 100; i++) {
            products.add(new Product(i, "Product " + i));
        }
        
        // 10 объектов в каждом bucket -> O(10) поиск вместо O(1)
    }
}

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

public class BrokenHashContract {
    
    static class User {
        String email;
        String name;
        
        User(String email, String name) {
            this.email = email;
            this.name = name;
        }
        
        // ПЛОХО: Нарушение контракта!
        @Override
        public int hashCode() {
            return email.hashCode(); // Использует только email
        }
        
        @Override
        public boolean equals(Object o) {
            if (!(o instanceof User)) return false;
            User u = (User) o;
            // Сравнивает email И name
            return email.equals(u.email) && name.equals(u.name);
        }
    }
    
    public static void main(String[] args) {
        Set<User> users = new HashSet<>();
        
        User user1 = new User("john@example.com", "John");
        User user2 = new User("john@example.com", "Johnny");
        
        users.add(user1);
        users.add(user2);
        
        // Контракт: если equals() = true, то hashCode должен быть одинаковым
        System.out.println(user1.equals(user2)); // false (разные name)
        System.out.println(user1.hashCode() == user2.hashCode()); // true
        
        // Оба объекта будут добавлены (неправильно)
        System.out.println(users.size()); // 2 (должно быть 2, но из-за разных name)
    }
}

Хорошая реализация hashCode

Правильный hashCode для複数 полей:

public class GoodHashCodeImplementation {
    
    static class Account {
        String email;
        String username;
        int accountId;
        
        Account(String email, String username, int accountId) {
            this.email = email;
            this.username = username;
            this.accountId = accountId;
        }
        
        @Override
        public int hashCode() {
            // Хорошо: используем все поля, участвующие в equals()
            return Objects.hash(email, username, accountId);
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Account)) return false;
            Account acc = (Account) o;
            return accountId == acc.accountId &&
                   Objects.equals(email, acc.email) &&
                   Objects.equals(username, acc.username);
        }
    }
    
    // Objects.hash() использует эффективный алгоритм комбинирования
    public static void main(String[] args) {
        Set<Account> accounts = new HashSet<>();
        
        accounts.add(new Account("john@example.com", "john_doe", 1));
        accounts.add(new Account("jane@example.com", "jane_doe", 2));
        accounts.add(new Account("bob@example.com", "bob_smith", 3));
        
        System.out.println(accounts.size()); // 3
    }
}

Альтернатива: примитивная реализация для производительности:

public class OptimizedHashCode {
    
    static class Point {
        int x, y;
        
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        @Override
        public int hashCode() {
            // Оптимизированная реализация
            // Используем праймное число и bit shifting
            int prime = 31;
            int result = 1;
            result = prime * result + x;
            result = prime * result + y;
            return result;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Point)) return false;
            Point p = (Point) o;
            return x == p.x && y == p.y;
        }
    }
}

Best Practices

1. Контракт hashCode() и equals():

// Правило:
// 1. Если a.equals(b), то a.hashCode() == b.hashCode()
// 2. hashCode() должен быть consistent - возвращать одно значение
// 3. Используй ВСЕ поля в equals() в hashCode()

static class Email {
    String address;
    
    @Override
    public int hashCode() {
        return address.hashCode(); // ✅ Используем всё
    }
    
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Email)) return false;
        return address.equals(((Email) o).address);
    }
}

2. Используй Objects.hash() для простоты:

@Override
public int hashCode() {
    return Objects.hash(field1, field2, field3); // Просто и правильно
}

3. Тестируй распределение hashCode:

public class HashCodeDistributionTest {
    
    @Test
    public void testHashDistribution() {
        Set<MyClass> set = new HashSet<>();
        
        for (int i = 0; i < 10000; i++) {
            set.add(new MyClass(i));
        }
        
        // HashSet должен сохранить все элементы
        assertEquals(10000, set.size());
    }
}

Заключение

Коллизии hashCode в HashSet — это нормальное явление и обрабатываются автоматически через chaining. Однако плохая реализация hashCode() может привести к деградации производительности (O(n) вместо O(1)). Используй Objects.hash() для простоты и всегда соблюдай контракт между hashCode() и equals().