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 —...

169 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

164 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

161 viewsДен, 14:00

About

Blog

Apps

Platform