Java for Beginner

HashMap структура и внутреннее устройство.

HashMap — это одна из наиболее часто используемых структур данных в программировании, обеспечивающая хранение пар "ключ-значение" с возможностью быстрой вставки, удаления и поиска данных.

Основные характеристики HashMap:

Ключи и значения: Хранит пары "ключ-значение".
Хэш-функция: Использует хэш-функцию для вычисления индекса, по которому будет храниться элемент.
Бакеты: Внутренне HashMap представляет собой массив бакетов (корзин).
Связанный список или дерево в бакетах: При коллизии (когда разные ключи имеют одинаковый хэш) используется либо связанный список, либо сбалансированное дерево (в современных реализациях).

Внутреннее устройство HashMap

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

Бакеты

Бакет — это место для хранения пары "ключ-значение". Если несколько ключей попадают в один и тот же бакет (коллизия), они хранятся в виде связанного списка или красно-черного дерева.

Связанный список и дерево в бакетах

Когда происходит коллизия, в бакете начинается формироваться структура данных:

Связанный список: В более старых реализациях Java при коллизии использовался связанный список.
Красно-черное дерево: Начиная с Java 8, при определенном числе элементов в бакете связанный список преобразуется в красно-черное дерево для улучшения производительности.

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();

        // Вставка элементов
        map.put("One", 1);
        map.put("Two", 2);
        map.put("Three", 3);

        // Поиск элементов
        System.out.println("Value for key 'Two': " + map.get("Two"));

        // Удаление элемента
        map.remove("One");
        System.out.println("Map after removing 'One': " + map);
    }
}

Хэш-функция

HashMap использует метод hashCode() ключа для вычисления его хэш-кода, который затем преобразуется в индекс бакета с использованием операции побитового AND с размером массива минус один.

Алгоритм поиска

Вычисление хэш-кода: Сначала вычисляется хэш-код ключа.
Вычисление индекса бакета: Индекс вычисляется с использованием операции побитового AND.
Поиск в бакете: В бакете выполняется последовательный поиск в связанном списке или дерево-поиск, если это красно-черное дерево.

Сложность поиска

В среднем: O(1) для поиска, вставки и удаления. Это достигается благодаря равномерному распределению элементов по бакетам с использованием хорошей хэш-функции.
В худшем случае: O(n), если все ключи попадают в один бакет, и при этом используется связанный список. В случае использования красно-черного дерева сложность поиска в худшем случае будет O(log n).

Пример работы с коллизиями

public class Main {
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>();

        // Эти два разных ключа могут дать одинаковый хэш-код
        map.put(1, "One");
        map.put(17, "Seventeen");

        // Оба ключа будут находиться в одном бакете
        System.out.println("Value for key 1: " + map.get(1));
        System.out.println("Value for key 17: " + map.get(17));
    }
}

В этом примере ключи 1 и 17 могут попасть в один бакет, в зависимости от размера массива и хэш-функции, что демонстрирует ситуацию с коллизией.

Полезные ссылки для более полного ознакомления с HashMap (спасибо авторам за их кропотливую работу):
https://habr.com/ru/articles/128017/
https://javarush.com/groups/posts/2496-podrobnihy-razbor-klassa-hashmap

#Java #Training #Medium #HashMap

Хабр

Структуры данных в картинках. HashMap

Приветствую вас, хабрачитатели! Продолжаю попытки визуализировать структуры данных в Java. В предыдущих сериях мы уже ознакомились с ArrayList и LinkedList , сегодня же рассмотрим HashMap. HashMap —...

178 viewsДен, 05:47

Java for Beginner

Основные методы HashMap и их устройство

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

1. put(K key, V value)
Метод put добавляет или обновляет значение для указанного ключа.

Устройство метода:
Вычисление хэш-кода ключа: Метод вызывает key.hashCode().
Вычисление индекса бакета: Используется побитовая операция AND с (n-1), где n - размер массива бакетов.
Поиск существующего ключа в бакете: Если ключ уже существует, значение обновляется.
Вставка новой пары в бакет: Если ключ не существует, создается новый узел и добавляется в бакет.

public V put(K key, V value) {
    // Вычисление хэш-кода
    int hash = hash(key);
    // Вычисление индекса бакета
    int bucketIndex = indexFor(hash, table.length);
    // Поиск существующего ключа и обновление значения
    for (Entry<K, V> e = table[bucketIndex]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }
    // Вставка новой пары ключ-значение
    addEntry(hash, key, value, bucketIndex);
    return null;
}

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

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("One", 1);
        map.put("Two", 2);
        System.out.println(map); // Output: {One=1, Two=2}
    }
}

2. get(Object key)
Метод get возвращает значение, связанное с указанным ключом.

Устройство метода:
Вычисление хэш-кода ключа: Метод вызывает key.hashCode().
Вычисление индекса бакета: Используется побитовая операция AND.
Поиск в бакете: Последовательно проверяются элементы в бакете.

public V get(Object key) {
    // Вычисление хэш-кода
    int hash = hash(key);
    // Поиск в бакете
    for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            return e.value;
        }
    }
    return null;
}

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

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("One", 1);
        System.out.println(map.get("One")); // Output: 1
    }
}

3. remove(Object key)
Метод remove удаляет пару "ключ-значение" по указанному ключу.

Устройство метода:
Вычисление хэш-кода ключа: Метод вызывает key.hashCode().
Вычисление индекса бакета: Используется побитовая операция AND.
Поиск и удаление: Ищется элемент в бакете и удаляется, если найден.

public V remove(Object key) {
    Entry<K, V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

private Entry<K, V> removeEntryForKey(Object key) {
    // Вычисление хэш-кода
    int hash = hash(key);
    int bucketIndex = indexFor(hash, table.length);
    Entry<K, V> prev = table[bucketIndex];
    Entry<K, V> e = prev;

    while (e != null) {
        Entry<K, V> next = e.next;
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            if (prev == e) {
                table[bucketIndex] = next;
            } else {
                prev.next = next;
            }
            return e;
        }
        prev = e;
        e = next;
    }
    return null;
}

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

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("One", 1);
        map.put("Two", 2);
        map.remove("One");
        System.out.println(map); // Output: {Two=2}
    }
}

#Java #Training #Medium #HashMap

170 viewsДен, 14:00

Java for Beginner

4. containsKey(Object key)
Метод containsKey проверяет, существует ли указанная ключ в HashMap.

Устройство метода:
Использует метод get: Если метод get возвращает не null, значит ключ существует.

public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

final Entry<K, V> getEntry(Object key) {
    // Вычисление хэш-кода
    int hash = (key == null) ? 0 : hash(key);
    // Поиск в бакете
    for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
            return e;
        }
    }
    return null;
}

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

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("One", 1);
        System.out.println(map.containsKey("One")); // Output: true
        System.out.println(map.containsKey("Two")); // Output: false
    }
}

5. containsValue(Object value)
Метод containsValue проверяет, существует ли указанное значение в HashMap.

Устройство метода:
Проходит по всем бакетам: Проверяет каждый элемент на наличие значения.

public boolean containsValue(Object value) {
    if (value == null) {
        for (Entry<K, V> e : table)
            for (Entry<K, V> ee = e; ee != null; ee = ee.next)
                if (ee.value == null)
                    return true;
    } else {
        for (Entry<K, V> e : table)
            for (Entry<K, V> ee = e; ee != null; ee = ee.next)
                if (value.equals(ee.value))
                    return true;
    }
    return false;
}

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

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("One", 1);
        System.out.println(map.containsValue(1)); // Output: true
        System.out.println(map.containsValue(2)); // Output: false
    }
}

6. size()
Метод size возвращает количество пар "ключ-значение" в HashMap.

Устройство метода:
Хранение размера: HashMap хранит размер как переменную size.

public int size() {
    return size;
}
Пример использования:
java
Копировать код
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("One", 1);
        map.put("Two", 2);
        System.out.println(map.size()); // Output: 2
    }
}

7. clear()
Метод clear удаляет все пары "ключ-значение" из HashMap.

Устройство метода:
Устанавливает массив бакетов в null: И обнуляет размер.

public void clear() {
    Entry<K, V>[] tab = table;
    for (int i = 0; i < tab.length; i++)
        tab[i] = null;
    size = 0;
}

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

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("One", 1);
        map.put("Two", 2);
        map.clear();
        System.out.println(map.size()); // Output: 0
    }
}

#Java #Training #Medium #HashMap

168 viewsДен, 14:00

Java for Beginner

Раздел 6. Коллекции в Java

Глава 5. Map — отображения (словари)

Реализации: HashMap, LinkedHashMap, TreeMap и остальные

JCF предоставляет богатый набор реализаций Map, каждая оптимизирована под конкретные нужды.

Все они реализуют Map<K, V>, но различаются по:
Хранению: Хэш-таблица (HashMap), связный список + хэш (LinkedHashMap), красно-черное дерево (TreeMap).
Порядку: Нет (HashMap), вставки (LinkedHashMap), сортировка по ключам (TreeMap).
Производительности: O(1) для хэш, O(log n) для дерево.
Дополнительно: Специальные для enum, слабых ссылок и т.д.

1. HashMap<K, V>: Основная реализация

Описание: HashMap — сердце Map в Java, основанная на хэш-таблице. Хранит пары в массиве "бакетов" (buckets), где каждый бакет — список узлов (node) с ключом, значением и хэш-кодом.

Внутренняя структура:
Массив Node<K,V>[] table (initial capacity 16, load factor 0.75).
При put: Вычисляет hash = key.hashCode() ^ (hash >>> 16) для равномерности.
Индекс бакета: hash & (table.length - 1).
Коллизия: LinkedList или Tree (с Java 8, если > 8 узлов — дерево для O(log n)).
Ресайз: При >75% заполнения — удваивает размер, перехэширует все элементы.

Big O:
put/get/remove/containsKey: O(1) средний, O(n) worst (плохие хэши).
Итерация: O(capacity).

Особенности:
Порядок: Нет (iteration order не гарантирован).
Null: Один null-ключ, несколько null-значений.
Thread-safe: Нет (ConcurrentModificationException при параллельном доступе).
Initial capacity/load factor: new HashMap<>(16, 0.75f) для оптимизации.

Нюансы и ловушки:
hashCode/equals: Критичны! Плохой hashCode — деградация до O(n). Изменение ключа после put — потеря элемента.
Ресайз: O(n) время, но редко.
Java 8+: Tree nodes для коллизий (>8 узлов).
Remove: Если null-ключ — специальная обработка.
Итерация: entrySet(), keySet(), values() — O(capacity), не size().

Пример кода:

javaimport java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Алексей", 35);
        ages.put("Мария", 28);
        ages.put("Алексей", 36);  // Перезапись

        System.out.println(ages.get("Алексей"));  // 36
        ages.put(null, 0);  // Null-ключ
        System.out.println(ages.size());  // 3

        // Итерация
        for (Map.Entry<String, Integer> entry : ages.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}
Когда использовать: 99% случаев — быстрый поиск/кэш (userId -> User).

2. LinkedHashMap<K, V>: HashMap с порядком

Описание: Расширение HashMap с двусвязным списком для сохранения порядка вставки (insertion-order) или доступа (access-order для LRU-кэша).

Внутренняя структура: HashMap + Entry с prev/next ссылками. Два режима: INSERTION_ORDER (default) или ACCESS_ORDER (constructor flag).

Big O: O(1) для put/get/remove, как HashMap.

Особенности:
Порядок: Вставки (по умолчанию) или доступа (get/put обновляет позицию).
Null: Да.
Thread-safe: Нет.

Нюансы:
LRU кэш: new LinkedHashMap<>(16, 0.75f, true) — access-order, removeEldestEntry для eviction.
Итерация: В порядке вставки/доступа.
Ресайз: Как HashMap, но сохраняет порядок.

Пример:

javaimport java.util.LinkedHashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("A", 1);
        map.put("B", 2);
        map.put("A", 3);  // Обновляет, но порядок сохраняется

        for (String key : map.keySet()) {
            System.out.println(key);  // A, B — порядок вставки
        }

        // Access-order
        Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true);
        lru.put("A", 1);
        lru.get("A");  // "A" перемещается в конец
    }
}
Когда использовать: Кэш с порядком (LRU), когда нужен predictable iteration.

#Java #для_новичков #beginner #Map #HashMap #LinkedHashMap #TreeMap #Hashtable #IdentityHashMap #EnumMap #WeakHashMap

👍1

45 views08:58

Java for Beginner

3. TreeMap<K, V>: Отсортированная Map

Описание: Реализация SortedMap<K, V> на красно-черном дереве (red-black tree). Ключи всегда отсортированы.

Внутренняя структура: Дерево узлов с left/right/child ссылками, цветом для баланса.

Big O: O(log n) для put/get/remove/containsKey.

Особенности:
Порядок: Сортировка по ключам (Comparable или Comparator).
Null-ключ: Нет (NPE).
Null-значение: Да.
Thread-safe: Нет.

Нюансы:
Comparator: new TreeMap<>(comparator) для custom сортировки.
Дополнительные методы: firstKey(), lastKey(), headMap(K to), tailMap(K from), subMap.
Custom ключи: Comparable<K> или Comparator.
Баланс: Автоматический, O(log n) гарантировано.

Пример:

javaimport java.util.TreeMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> map = new TreeMap<>();
        map.put(3, "Три");
        map.put(1, "Один");
        map.put(2, "Два");

        for (Integer key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));  // 1: Один, 2: Два, 3: Три
        }

        System.out.println(map.firstKey());  // 1
    }
}
Когда использовать: Отсортированные ключи (диапазонные запросы, алфавитный словарь).

Остальные реализации: Hashtable, IdentityHashMap, EnumMap, WeakHashMap

Hashtable<K, V> (устаревшая)

Описание: Первая Map в Java (1.0), synchronized версия HashMap.
Особенности: Thread-safe (synchronized методы), нет null, порядок нет.
Big O: O(1).
Нюансы: Медленнее HashMap (locks на каждый метод), legacy — используйте ConcurrentHashMap.
Когда: Только legacy код.

IdentityHashMap<K, V>

Описание: HashMap с == вместо equals/hashCode (по ссылке).
Особенности: Для объектов, где важна идентичность (graph algorithms).
Big O: O(1).
Нюансы: Load factor 0.5, double hash для коллизий.
Когда: Редко, для identity сравнения.

EnumMap<K extends Enum<K>, V>

Описание: Оптимизированная Map для enum ключей (массив вместо хэш).
Особенности: O(1), порядок enum, нет null-ключа.
Нюансы: Ключи — enum, values any.
Когда: State machines, enum configs.

WeakHashMap<K, V>

Описание: HashMap с weak keys (GC может удалить entry, если ключ недостижим).
Особенности: Для кэшей, где память критична.
Big O: O(1).
Нюансы: Values strong, cleanup не мгновенный.
Когда: Canonicalizing mappings (interning).

Полезные советы для новичков

HashMap 95% случаев: Начните с неё.
LinkedHashMap для кэша: removeEldestEntry для LRU.
TreeMap для сортировки: Comparator для reverse.
Custom ключи: IDE генерирует equals/hashCode.
Initial capacity: new HashMap<>(expectedSize) для избежания ресайза.
Ошибки: NPE в TreeMap с null-ключом; ClassCast в TreeMap без Comparable.

#Java #для_новичков #beginner #Map #HashMap #LinkedHashMap #TreeMap #Hashtable #IdentityHashMap #EnumMap #WeakHashMap

👍2

45 views08:58

About

Blog

Apps

Platform