Что такое Entry в HashMap?

Entry в HashMap

Определение

Entry — это внутренний интерфейс HashMap (и других Map реализаций), который представляет пару ключ-значение (key-value pair). Каждый элемент в HashMap хранится как Entry.

public interface Map<K, V> {
    interface Entry<K, V> {
        K getKey();
        V getValue();
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
    }
}

Структура Entry в HashMap

Внутри HashMap используется приватный класс Node (или Entry в старых версиях Java):

// Упрощённая версия из HashMap
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;        // Хеш кода ключа
    final K key;           // Ключ (неизменяемый)
    V value;               // Значение
    Node<K,V> next;        // Ссылка на следующий элемент (для цепочки коллизий)
    
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?> e = (Map.Entry<?>) o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

Как HashMap использует Entry

HashMap организует элементы в массив buckets, где каждый bucket содержит цепочку (или бинарное дерево в Java 8+) Entry объектов:

HashMap internal structure:
┌─────────────┐
│  bucket[0]  │ -> Entry(key1, val1) -> Entry(key2, val2)
│  bucket[1]  │ -> Entry(key3, val3)
│  bucket[2]  │ -> null
│  ...        │
│ bucket[15]  │ -> Entry(key4, val4) -> Entry(key5, val5) -> Entry(key6, val6)
└─────────────┘

Коллизии (когда несколько ключей имеют одинаковый хеш) разрешаются цепочками Entry объектов, связанных через поле next.

Использование Entry в коде

1. Итерация через entrySet() — самый эффективный способ

Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
map.put("Bob", 30);
map.put("Charlie", 35);

// Правильно — итерируем Entry
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String name = entry.getKey();
    Integer age = entry.getValue();
    System.out.println(name + " is " + age);
}

// Неправильно — итерируем ключи, потом ищем значения
for (String name : map.keySet()) {
    Integer age = map.get(name);  // Лишний поиск O(n)
}

2. Модификация значений через Entry

Map<String, Integer> salaries = new HashMap<>();
salaries.put("Alice", 50000);
salaries.put("Bob", 60000);

// Повышаем зарплату на 10%
for (Map.Entry<String, Integer> entry : salaries.entrySet()) {
    Integer newSalary = (int) (entry.getValue() * 1.1);
    entry.setValue(newSalary);
}

3. Фильтрация и трансформация

Map<String, Integer> scores = new HashMap<>();
scores.put("Game1", 100);
scores.put("Game2", 85);
scores.put("Game3", 92);

// Удалить все игры с низким результатом
scores.entrySet().removeIf(entry -> entry.getValue() < 90);

// Stream API
Map<String, Integer> filtered = scores.entrySet().stream()
    .filter(entry -> entry.getValue() >= 90)
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

Производительность

Разница в производительности значительна при больших картах:

Map<String, String> largeMap = new HashMap<>();
// Добавляем 1,000,000 элементов

long start, end;

// 1. entrySet() — O(n)
start = System.nanoTime();
for (Map.Entry<String, String> entry : largeMap.entrySet()) {
    String key = entry.getKey();
    String value = entry.getValue();
}
end = System.nanoTime();
System.out.println("entrySet: " + (end - start)); // ~10ms

// 2. keySet() + get() — O(n²) или близко к этому
start = System.nanoTime();
for (String key : largeMap.keySet()) {
    String value = largeMap.get(key);
}
end = System.nanoTime();
System.out.println("keySet+get: " + (end - start)); // ~100ms

// 3. values() — если нужны только значения
start = System.nanoTime();
for (String value : largeMap.values()) {
    // используем value
}
end = System.nanoTime();
System.out.println("values: " + (end - start)); // ~10ms

Entry в LinkedHashMap

// LinkedHashMap сохраняет порядок вставки через дополнительные Entry
public class LinkedHashMap<K,V> extends HashMap<K,V> {
    static class LinkedHashMapEntry<K,V> extends Node<K,V> {
        LinkedHashMapEntry<K,V> before, after;  // Двусвязный список
        
        LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
}

Практические правила

1. Используйте entrySet() для итерации — это самый быстрый способ
2. Используйте keySet() только если нужны только ключи
3. Используйте values() только если нужны только значения
4. Избегайте keySet() + get() — это создаёт дополнительные поиски
5. Для Stream API используйте .entrySet().stream() для максимальной производительности

Entry в другие типах Map

Entry поддерживается всеми реализациями Map:

• HashMap — несортированная, неупорядоченная
• LinkedHashMap — сохраняет порядок вставки
• TreeMap — отсортирована по ключам
• ConcurrentHashMap — потокобезопасная

Интерфейс Entry везде одинаков, разница только во внутренней реализации.