Как добраться до листов HashMap

# Как добраться до листов (узлов) в HashMap

Этот вопрос касается внутреннего строения HashMap и как получить доступ к его внутренним структурам данных. Я разберу разные подходы от простых до продвинутых.

Внутренняя структура HashMap

HashMap состоит из:

1. Array of buckets (массив бакетов) — массив ссылок на узлы
2. Nodes (Entry) — каждый узел содержит key, value, hash, next
3. Linked List / Red-Black Tree — при коллизиях

HashMap структура:
┌───────────────────────────────┐
│     table (Node<K,V>[])       │  Массив бакетов (размер 16, 32, ...)
├───────────────────────────────┤
│ [0] → null                    │
│ [1] → Node(key=A, val=1)      │  ┌──────────────────┐
│       └→ Node(key=B, val=2)   │  │ Linked List при  │
│          └→ Node(key=C, val=3)│  │ коллизиях        │
│ [2] → Node(key=D, val=4)      │  └──────────────────┘
│ [3] → null                    │
│ ...                           │
│ [15]→ Node(key=E, val=5)      │  Red-Black Tree (size > 8)
└───────────────────────────────┘

Вариант 1: Через entrySet() (Public API) ✅

Это самый правильный способ:

public class HashMapTraversal {
    public void traverseHashMap(Map<String, Integer> map) {
        // Вариант 1: entrySet (самый эффективный)
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key + " : " + value);
        }
        // Проход по всем узлам, O(n)
    }
    
    // Вариант 2: values() (менее эффективный)
    public void traverseValues(Map<String, Integer> map) {
        for (Integer value : map.values()) {
            System.out.println(value);
        }
    }
    
    // Вариант 3: keySet() (менее эффективный)
    public void traverseKeys(Map<String, Integer> map) {
        for (String key : map.keySet()) {
            System.out.println(key);
        }
    }
}

Что происходит под капотом:

// HashMap.entrySet() возвращает:
public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

// EntrySet итерирует по всем бакетам
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final Iterator<Map.Entry<K,V>> iterator() {
        return new EntryIterator();  // ← Вот тут!
    }
}

// EntryIterator проходит по table массиву
final class EntryIterator extends HashIterator {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

Вариант 2: Через Reflection (Advanced)

Для получения прямого доступа к внутренней таблице:

import java.lang.reflect.Field;

public class HashMapReflection {
    
    @SuppressWarnings("unchecked")
    public void accessInternalTable(HashMap<String, Integer> map) 
            throws NoSuchFieldException, IllegalAccessException {
        
        // Получить поле "table"
        Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        
        // Это массив Node<K,V>
        Object[] table = (Object[]) tableField.get(map);
        
        System.out.println("Table size: " + table.length);
        
        // Пройти по каждому бакету
        for (int i = 0; i < table.length; i++) {
            Object node = table[i]; // Первый узел в бакете
            
            if (node != null) {
                System.out.println("\nBucket " + i + ":");
                
                // Если это Node, проходим по цепочке
                while (node != null) {
                    String key = getKeyFromNode(node);
                    Object value = getValueFromNode(node);
                    System.out.println("  " + key + " = " + value);
                    
                    node = getNextFromNode(node);
                }
            }
        }
    }
    
    private String getKeyFromNode(Object node) 
            throws NoSuchFieldException, IllegalAccessException {
        Field keyField = node.getClass().getDeclaredField("key");
        keyField.setAccessible(true);
        return (String) keyField.get(node);
    }
    
    private Object getValueFromNode(Object node) 
            throws NoSuchFieldException, IllegalAccessException {
        Field valueField = node.getClass().getDeclaredField("value");
        valueField.setAccessible(true);
        return valueField.get(node);
    }
    
    private Object getNextFromNode(Object node) 
            throws NoSuchFieldException, IllegalAccessException {
        Field nextField = node.getClass().getDeclaredField("next");
        nextField.setAccessible(true);
        return nextField.get(node);
    }
}

Пример использования:

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

HashMapReflection reflector = new HashMapReflection();
reflector.accessInternalTable(map);

// Output:
// Table size: 16
// Bucket 2:
//   Alice = 30
// Bucket 5:
//   Bob = 25
//   Charlie = 35

Вариант 3: Unsafe (Очень Advanced)

Лишь для специалистов:

import sun.misc.Unsafe;
import java.lang.reflect.Field;

public class HashMapUnsafe {
    
    private static Unsafe unsafe;
    private static long tableOffset;
    
    static {
        try {
            Field field = Unsafe.class.getDeclaredField("theUnsafe");
            field.setAccessible(true);
            unsafe = (Unsafe) field.get(null);
            
            // Получить смещение поля "table"
            tableOffset = unsafe.objectFieldOffset(
                HashMap.class.getDeclaredField("table")
            );
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
    
    public void accessUnsafe(HashMap<String, Integer> map) {
        // Получить таблицу через Unsafe
        Object[] table = (Object[]) unsafe.getObject(
            map, tableOffset
        );
        
        System.out.println("Table length: " + table.length);
        // Очень быстро, но опасно!
    }
}

⚠️ Unsafe не рекомендуется в production коде.

Вариант 4: Итератор (Iterator)

Более гибкий способ:

public class HashMapIteration {
    
    public void iterateWithIterator(Map<String, Integer> map) {
        // Iterator сам управляет позицией в таблице
        Iterator<Map.Entry<String, Integer>> iterator = 
            map.entrySet().iterator();
        
        while (iterator.hasNext()) {
            Map.Entry<String, Integer> entry = iterator.next();
            String key = entry.getKey();
            Integer value = entry.getValue();
            
            System.out.println(key + " = " + value);
            
            // Безопасное удаление во время итерации
            if (value > 30) {
                iterator.remove();
            }
        }
    }
    
    // Без iterator'а это выбросит ConcurrentModificationException
    public void unsafeModification(Map<String, Integer> map) {
        for (String key : map.keySet()) {
            if (map.get(key) > 30) {
                map.remove(key); // ❌ ConcurrentModificationException
            }
        }
    }
}

Вариант 5: Stream API

Модерный подход:

public class HashMapStreams {
    
    public void streamTraversal(Map<String, Integer> map) {
        // Обход через stream
        map.entrySet().stream()
            .filter(entry -> entry.getValue() > 25)
            .forEach(entry -> 
                System.out.println(entry.getKey() + " = " + entry.getValue())
            );
    }
    
    // Параллельный обход
    public void parallelTraversal(Map<String, Integer> map) {
        map.entrySet().parallelStream()
            .filter(entry -> entry.getValue() > 25)
            .forEach(entry -> 
                System.out.println(entry.getKey() + " = " + entry.getValue())
            );
    }
}

LinkedHashMap (Сохраняет порядок вставки)

public class LinkedHashMapTraversal {
    
    public void traverseLinkedHashMap() {
        // LinkedHashMap сохраняет порядок вставки
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("Alice", 30);
        map.put("Bob", 25);
        map.put("Charlie", 35);
        
        // Порядок: Alice, Bob, Charlie (insertion order)
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey());
        }
        
        // Внутри использует:
        // - table[] (как HashMap)
        // - head/tail (doubly-linked list для порядка)
    }
}

TreeMap (Red-Black Tree)

public class TreeMapTraversal {
    
    public void traverseTreeMap() {
        // TreeMap отсортирован по ключам
        Map<String, Integer> map = new TreeMap<>();
        map.put("Charlie", 35);
        map.put("Alice", 30);
        map.put("Bob", 25);
        
        // Порядок: Alice, Bob, Charlie (sorted by key)
        for (String key : map.keySet()) {
            System.out.println(key);
        }
        
        // TreeMap использует Red-Black Tree:
        // Entry(key, value, left, right, color)
    }
}

Сравнение подходов

Real-world пример

@Service
public class UserService {
    private final Map<UUID, User> userCache = new HashMap<>();
    
    // ✅ Правильно
    public void printAllUsers() {
        for (Map.Entry<UUID, User> entry : userCache.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
    
    // Альтернатива с stream
    public List<User> getActiveUsers() {
        return userCache.values().stream()
            .filter(User::isActive)
            .collect(Collectors.toList());
    }
    
    // Безопасное удаление
    public void removeInactiveUsers() {
        Iterator<Map.Entry<UUID, User>> iterator = 
            userCache.entrySet().iterator();
        
        while (iterator.hasNext()) {
            if (!iterator.next().getValue().isActive()) {
                iterator.remove(); // ✅ Safe
            }
        }
    }
}

Best Practices

1. Используй entrySet() для оптимальной производительности

// ❌ Плохо: два поиска в HashMap
for (String key : map.keySet()) {
    Integer value = map.get(key); // ← Второй поиск!
}

// ✅ Хорошо: один проход
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
}

2. Не используй Reflection в production

// ❌ Не делай так
Field tableField = HashMap.class.getDeclaredField("table");

// ✅ Используй public API
for (Map.Entry<K,V> entry : map.entrySet()) { ... }

3. Будь осторожен с модификацией

// ❌ ConcurrentModificationException
for (String key : map.keySet()) {
    if (shouldRemove(key)) {
        map.remove(key);
    }
}

// ✅ Используй Iterator
Iterator<String> iter = map.keySet().iterator();
while (iter.hasNext()) {
    if (shouldRemove(iter.next())) {
        iter.remove();
    }
}

Заключение

Доступ к узлам HashMap:

• Public API (entrySet, keySet, values) — рекомендуется ✅
• Iterator — для безопасного изменения
• Stream — модерный функциональный подход
• Reflection — только для отладки, не production
• Unsafe — очень редко, только эксперты

Это показывает понимание того, как работают коллекции под капотом, что важно для оптимизации performance.