PrepBro
← Назад к вопросам

Как хранятся данные в пустой Map

1.0 Junior🔥 221 комментариев
#Коллекции

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Как хранятся данные в пустой Map в Java

Это интересный вопрос о внутренней структуре HashMap и других реализаций Map. Понимание этого важно для оптимизации памяти и производительности.

HashMap: пустая Map

HashMap<String, Integer> map = new HashMap<>();
// Что здесь создалось в памяти?

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

┌─────────────────────────────────────┐
│ HashMap объект                      │
├─────────────────────────────────────┤
│ transient Node<K,V>[] table         │ ← Массив "бакетов"
│ int size                            │ ← Текущее количество элементов
│ int threshold                       │ ← Порог для resize
│ float loadFactor                    │ ← Коэффициент загрузки
│ int modCount                        │ ← Счетчик изменений
└─────────────────────────────────────┘

Инициализация HashMap

// Способ 1: конструктор без параметров (DEFAULT_INITIAL_CAPACITY = 16)
HashMap<String, Integer> map1 = new HashMap<>();

// Способ 2: конструктор с начальной ёмкостью
HashMap<String, Integer> map2 = new HashMap<>(32);

// Способ 3: конструктор из другой Map
HashMap<String, Integer> map3 = new HashMap<>(map1);

Источник в OpenJDK:

public class HashMap<K,V> extends AbstractMap<K,V> {
    // Дефолтная начальная ёмкость
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
    
    // Максимальная ёмкость
    static final int MAXIMUM_CAPACITY = 1 << 30; // 2^30
    
    // Коэффициент загрузки (перестройка при 75% заполнении)
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // Массив бакетов (ленивая инициализация!)
    transient Node<K,V>[] table;
    
    // Текущий размер
    transient int size;
    
    // Порог перестройки
    int threshold;
    
    // Конструктор
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75f
        // table НЕ инициализируется! (ленивая инициализация)
    }
}

Ленивая инициализация (Lazy Initialization)

ВАЖНО: при создании пустой HashMap массив table НЕ создается сразу!

HashMap<String, Integer> map = new HashMap<>();
// На этом этапе:
// - table = null (не выделена память!)
// - size = 0
// - loadFactor = 0.75f

// При первой вставке происходит инициализация:
map.put("key1", 1);

// Теперь создается массив table размером 16
// table = new Node[16] {
//   null, null, null, ..., null  // 16 элементов
// }

Внутренний механизм инициализации:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // ЛЕНИВАЯ ИНИЦИАЛИЗАЦИЯ!
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; // Первый resize создает массив
    
    // Находим бакет по хешу
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // Если коллизия, добавляем в цепь (до Java 8)
        // или в красно-чёрное дерево (Java 8+)
    }
    
    // ...
    return null;
}

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    // Увеличиваем ёмкость в 2 раза
    if (oldCap > 0) {
        newCap = oldCap << 1; // * 2
    } else if (oldThr > 0) {
        newCap = oldThr;
    } else {
        newCap = DEFAULT_INITIAL_CAPACITY; // 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12
    }
    
    // Создаем новый массив
    Node<K,V>[] newTab = new Node[newCap];
    table = newTab; // Подключаем новый массив
    
    // ...
    return newTab;
}

Структура Node внутри 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;
    }
}

Сравнение разных реализаций Map

1. HashMap (неупорядоченная)

// Пустая HashMap
HashMap<String, Integer> map = new HashMap<>();
// table = null (ленивая инициализация)
// Память: ~48 байт (сам объект HashMap)

// После первого put
// table = new Node[16]
// Память: ~48 байт (объект) + 128 байт (массив Node[16])

2. TreeMap (отсортированная, Red-Black Tree)

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

// Структура:
// ┌────────────────────┐
// │ TreeMap            │
// ├────────────────────┤
// │ Entry<K,V> root    │ ← Корень красно-чёрного дерева
// │ int size           │
// │ Comparator<K>      │
// └────────────────────┘

// root = null (пусто)
// size = 0

3. LinkedHashMap (упорядоченная по вставке)

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

// Структура (расширение HashMap):
// ┌─────────────────────────────┐
// │ LinkedHashMap               │
// ├─────────────────────────────┤
// │ Node<K,V>[] table (унаслед) │ ← null (ленивая инициализация)
// │ Entry<K,V> head             │ ← Начало двусвязного списка
// │ Entry<K,V> tail             │ ← Конец двусвязного списка
// │ boolean accessOrder         │ ← false для insertion order
// └─────────────────────────────┘

// head = null, tail = null

4. ConcurrentHashMap (потокобезопасная)

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

// Структура (похожа на HashMap, но с сегментами):
// ┌──────────────────────────────┐
// │ ConcurrentHashMap            │
// ├──────────────────────────────┤
// │ Node<K,V>[] table            │ ← null (ленивая инициализация)
// │ int sizeCtl                  │ ← Контроль инициализации и resize
// │ volatile long baseCount      │ ← Базовый счёт (для счета элементов)
// │ CounterCell[] counterCells   │ ← Клетки счёта для потокобезопасности
// └──────────────────────────────┘

Расход памяти пустой Map

// Инструмент для измерения
import org.openjdk.jol.core.VM;
import org.openjdk.jol.info.ClassLayout;

// Размер объекта в памяти
public class MapMemoryTest {
    public static void main(String[] args) {
        // Пустая HashMap
        HashMap<String, Integer> hashMap = new HashMap<>();
        System.out.println("HashMap size: " + VM.current().sizeOf(hashMap)); // ~48 байт
        
        // Пустая TreeMap
        TreeMap<String, Integer> treeMap = new TreeMap<>();
        System.out.println("TreeMap size: " + VM.current().sizeOf(treeMap)); // ~48 байт
        
        // Пустая LinkedHashMap
        LinkedHashMap<String, Integer> linkedMap = new LinkedHashMap<>();
        System.out.println("LinkedHashMap size: " + VM.current().sizeOf(linkedMap)); // ~56 байт
        
        // После добавления одного элемента
        hashMap.put("key", 1);
        System.out.println("HashMap with 1 element: " + VM.current().sizeOf(hashMap));
        // Будет больше из-за массива table[16]
    }
}

// Результаты на 64-bit JVM:
// HashMap (пусто): 48 байт
// HashMap (с table[16]): 176 байт (48 + 128)
// TreeMap (пусто): 48 байт
// LinkedHashMap (пусто): 56 байт (две доп. ссылки на head/tail)

Оптимизация памяти для часто пустых Map'ов

// ❌ Плохо: создаешь Map, а он остается пустым
public class Config {
    private Map<String, String> properties = new HashMap<>(); // ~176 байт память
}

// ✅ Хорошо: ленивая инициализация
public class Config {
    private Map<String, String> properties = null;
    
    public void addProperty(String key, String value) {
        if (properties == null) {
            properties = new HashMap<>();
        }
        properties.put(key, value);
    }
    
    public String getProperty(String key) {
        return properties != null ? properties.get(key) : null;
    }
}

// ✅ Или используй Optional
public class Config {
    private Optional<Map<String, String>> properties = Optional.empty();
    
    public void addProperty(String key, String value) {
        properties.orElseGet(HashMap::new).put(key, value);
    }
}

// ✅ Или используй Collections.emptyMap()
public class ImmutableConfig {
    private final Map<String, String> properties = Collections.emptyMap();
    // Ноль памяти на table!
}

Collections.emptyMap() vs new HashMap()

// Collections.emptyMap() - очень экономно
Map<String, Integer> empty = Collections.emptyMap();
// Это синглтон, не создает таблицу
// Пытка модифицировать выбросит UnsupportedOperationException

// new HashMap() - требует больше памяти
Map<String, Integer> map = new HashMap<>();
// Содержит null table, но готов к расширению

// Когда использовать:
if (shouldCreateMap) {
    return new HashMap<>();
} else {
    return Collections.emptyMap(); // Экономит память!
}

Механизм хеширования

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    // XOR верхних 16 бит с нижними для лучшего распределения
}

// Индекс в таблице вычисляется так:
int index = (n - 1) & hash; // Эквивалентно hash % n, но быстрее
// Требует n быть степенью 2!

Резюме

  1. Пустая HashMap создает только сам объект (~48 байт), массив table инициализируется ленивой инициализацией
  2. Первое добавление элемента создает массив table размером 16
  3. При 75% заполнении массив увеличивается в 2 раза (resize)
  4. TreeMap, LinkedHashMap имеют схожую структуру
  5. Для часто пустых Map'ов используй Collections.emptyMap() для экономии памяти
Как хранятся данные в пустой Map | PrepBro