Как считается hash в Map

Как считается hash в Map

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

Базовый принцип работы HashMap

HashMap использует массив "бакетов". Каждый ключ преобразуется в индекс массива через хеш-функцию:

int hash = key.hashCode();
int index = hash % buckets.length;
Entry entry = buckets[index];

1. Процесс хеширования ключа

public class HashCalculation {
    public static void main(String[] args) {
        String key = "myKey";
        int hashCode = key.hashCode();
        System.out.println("hashCode: " + hashCode);
        System.out.println("Binary: " + Integer.toBinaryString(hashCode));
    }
}

2. Оптимизация хеша в HashMap

Для уменьшения конфликтов HashMap применяет XOR операцию:

static int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3. Вычисление индекса

public class BucketIndexCalculation {
    static final int DEFAULT_CAPACITY = 16;
    
    public static void main(String[] args) {
        String key = "apple";
        int hash = hash(key);
        int index = hash & (DEFAULT_CAPACITY - 1);
        System.out.println("Index: " + index);
    }
    
    static int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
}

4. Разрешение коллизий - цепочки

Когда несколько ключей дают одинаковый индекс, используется связанный список:

static class Entry<K, V> {
    K key;
    V value;
    Entry<K, V> next;
    
    Entry(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

public V get(K key) {
    int index = hash(key);
    Entry<K, V> entry = buckets[index];
    
    while (entry != null) {
        if (entry.key.equals(key)) {
            return entry.value;
        }
        entry = entry.next;
    }
    return null;
}

5. Дерево вместо цепочки (Java 8+)

При превышении порога (TREEIFY_THRESHOLD = 8) цепочка преобразуется в красно-чёрное дерево для O(log n) поиска:

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

6. Переопределение hashCode() и equals()

Главное правило: если переопределяешь equals(), обязательно переопредели hashCode():

static class User {
    String username;
    int id;
    
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof User)) return false;
        User user = (User) o;
        return id == user.id && username.equals(user.username);
    }
    
    @Override
    public int hashCode() {
        return java.util.Objects.hash(username, id);
    }
}

7. Load Factor и расширение HashMap

• DEFAULT_LOAD_FACTOR = 0.75
• Когда size > capacity * 0.75, HashMap расширяется вдвое
• Требует пересчёта всех индексов (rehashing)

Важные замечания

• Равенство: объекты a.equals(b) должны иметь a.hashCode() == b.hashCode()
• Стабильность: hashCode() должен быть неизменным для объекта в Map
• Неизменяемость: ключи не должны меняться во время нахождения в Map
• Коллизии: неизбежны, но хороший hashCode() их минимизирует
• Null ключ: HashMap позволяет ровно один null ключ
• LinkedHashMap: сохраняет порядок вставки через двусвязный список
• Производительность: средний O(1), худший O(n) при плохом hashCode()