Всем доброго субботнего утра! ☀️
Как ваше настроение, какие планы на выходные?
Делитесь с нами в чате - https://t.me/Java_Beginner_chat
Напоминаю, что завтра в 16:00 по МСК запланирована онлайн встреча, где мы наконец-то закончим наше консольное TODO приложение!)))
Как ваше настроение, какие планы на выходные?
Делитесь с нами в чате - https://t.me/Java_Beginner_chat
Напоминаю, что завтра в 16:00 по МСК запланирована онлайн встреча, где мы наконец-то закончим наше консольное TODO приложение!)))
Утро программиста.
#Mems
объекты: Жена, Будильник, Автомобиль;
переменные: совесть, желание_спать, сытость, злость
если Будильник = 1
{
перевести(5min);
перевести(5min);
выключить();
встать();
}
если Будильник = 0
{
пока (совесть < желание_спать)
{
спать();
}
встать();
}
умыться();
если Жена > 0
{
приготовить_завтрак(жена);
}
если Жена = 0
{
приготовить_завтрак(содержимое холодильника[0]);
}
сытость = сытость + 1;
если автомобиль !=1
{
добраться_до_работы(спать());
}
если автомобиль =1
{
добраться_до_работы(злость);
}
#Mems
Напоминаю про канал моего товарища 3D-шника) - https://t.me/model3ddd/3511
Если вас интересует данная тема, есть желание изучить ее подробнее, ознакомиться с примерами работ - залетайте не думая!
Если вас интересует данная тема, есть желание изучить ее подробнее, ознакомиться с примерами работ - залетайте не думая!
Telegram
3Dshnik
📱 Все: мы будем использовать ChatGPT для революций в науке и технике
Мы используем ChatGPT:
3Dshnik - Подписаться
Мы используем ChatGPT:
3Dshnik - Подписаться
А вы придете на онлайн встречу в 16:00 по МСК сегодня?
Anonymous Poll
42%
Да, я буду!)
50%
Хотел бы, но не могу(
0%
Нет, нафиг мне это надо?)))
8%
Что это за канал?)
This media is not supported in your browser
VIEW IN TELEGRAM
Запись нашей сегодняшней встречи -
https://youtu.be/QGPf_ki7V1c
Огромная благодарность тем кто был, за участие и подсказки, без Вас было б скучнее))))
Мы наконец то закончили консольную записную книжку, написанную в самом простом варианте, понятном даже для новичков.
Смотрите, комментируйте, задавайте вопросы! Обязательно подписывайтесь на ютуб канал!
Гит репозиторий с результатом - https://github.com/Oleborn/Notebook
Всем лучей добра)⭐️
https://youtu.be/QGPf_ki7V1c
Огромная благодарность тем кто был, за участие и подсказки, без Вас было б скучнее))))
Мы наконец то закончили консольную записную книжку, написанную в самом простом варианте, понятном даже для новичков.
Смотрите, комментируйте, задавайте вопросы! Обязательно подписывайтесь на ютуб канал!
Гит репозиторий с результатом - https://github.com/Oleborn/Notebook
Всем лучей добра)⭐️
HashMap структура и внутреннее устройство.
HashMap — это одна из наиболее часто используемых структур данных в программировании, обеспечивающая хранение пар "ключ-значение" с возможностью быстрой вставки, удаления и поиска данных.
Основные характеристики HashMap:
Ключи и значения: Хранит пары "ключ-значение".
Хэш-функция: Использует хэш-функцию для вычисления индекса, по которому будет храниться элемент.
Бакеты: Внутренне HashMap представляет собой массив бакетов (корзин).
Связанный список или дерево в бакетах: При коллизии (когда разные ключи имеют одинаковый хэш) используется либо связанный список, либо сбалансированное дерево (в современных реализациях).
Внутреннее устройство HashMap
HashMap использует массив, где каждый элемент называется бакетом. Каждому ключу через хэш-функцию сопоставляется индекс бакета.
Бакеты
Бакет — это место для хранения пары "ключ-значение". Если несколько ключей попадают в один и тот же бакет (коллизия), они хранятся в виде связанного списка или красно-черного дерева.
Связанный список и дерево в бакетах
Когда происходит коллизия, в бакете начинается формироваться структура данных:
Связанный список: В более старых реализациях Java при коллизии использовался связанный список.
Красно-черное дерево: Начиная с Java 8, при определенном числе элементов в бакете связанный список преобразуется в красно-черное дерево для улучшения производительности.
Хэш-функция
HashMap использует метод hashCode() ключа для вычисления его хэш-кода, который затем преобразуется в индекс бакета с использованием операции побитового AND с размером массива минус один.
Алгоритм поиска
Вычисление хэш-кода: Сначала вычисляется хэш-код ключа.
Вычисление индекса бакета: Индекс вычисляется с использованием операции побитового AND.
Поиск в бакете: В бакете выполняется последовательный поиск в связанном списке или дерево-поиск, если это красно-черное дерево.
Сложность поиска
В среднем: O(1) для поиска, вставки и удаления. Это достигается благодаря равномерному распределению элементов по бакетам с использованием хорошей хэш-функции.
В худшем случае: O(n), если все ключи попадают в один бакет, и при этом используется связанный список. В случае использования красно-черного дерева сложность поиска в худшем случае будет O(log n).
Пример работы с коллизиями
В этом примере ключи 1 и 17 могут попасть в один бакет, в зависимости от размера массива и хэш-функции, что демонстрирует ситуацию с коллизией.
Полезные ссылки для более полного ознакомления с HashMap (спасибо авторам за их кропотливую работу):
https://habr.com/ru/articles/128017/
https://javarush.com/groups/posts/2496-podrobnihy-razbor-klassa-hashmap
#Java #Training #Medium #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 —...
Что выведет код?
#Tasks
public class ArithmeticChallenge {
public static void main(String[] args) {
int result = mysteriousArithmetic(3, 2);
System.out.println(result);
}
public static int mysteriousArithmetic(int a, int b) {
int result = 0;
for (int i = 1; i <= a; i++) {
result += (i % 2 == 0) ? (i * b) : (i + b);
}
return result;
}
}
#Tasks
Основные методы HashMap и их устройство
HashMap предоставляет множество методов для работы с парами "ключ-значение". Рассмотрим основные методы и разберем их внутреннее устройство.
1. put(K key, V value)
Метод put добавляет или обновляет значение для указанного ключа.
Устройство метода:
Вычисление хэш-кода ключа: Метод вызывает key.hashCode().
Вычисление индекса бакета: Используется побитовая операция AND с (n-1), где n - размер массива бакетов.
Поиск существующего ключа в бакете: Если ключ уже существует, значение обновляется.
Вставка новой пары в бакет: Если ключ не существует, создается новый узел и добавляется в бакет.
Пример использования:
2. get(Object key)
Метод get возвращает значение, связанное с указанным ключом.
Устройство метода:
Вычисление хэш-кода ключа: Метод вызывает key.hashCode().
Вычисление индекса бакета: Используется побитовая операция AND.
Поиск в бакете: Последовательно проверяются элементы в бакете.
Пример использования:
3. remove(Object key)
Метод remove удаляет пару "ключ-значение" по указанному ключу.
Устройство метода:
Вычисление хэш-кода ключа: Метод вызывает key.hashCode().
Вычисление индекса бакета: Используется побитовая операция AND.
Поиск и удаление: Ищется элемент в бакете и удаляется, если найден.
Пример использования:
#Java #Training #Medium #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
4. containsKey(Object key)
Метод containsKey проверяет, существует ли указанная ключ в HashMap.
Устройство метода:
Использует метод get: Если метод get возвращает не null, значит ключ существует.
Пример использования:
5. containsValue(Object value)
Метод containsValue проверяет, существует ли указанное значение в HashMap.
Устройство метода:
Проходит по всем бакетам: Проверяет каждый элемент на наличие значения.
Пример использования:
6. size()
Метод size возвращает количество пар "ключ-значение" в HashMap.
Устройство метода:
Хранение размера: HashMap хранит размер как переменную size.
7. clear()
Метод clear удаляет все пары "ключ-значение" из HashMap.
Устройство метода:
Устанавливает массив бакетов в null: И обнуляет размер.
Пример использования:
#Java #Training #Medium #HashMap
Метод 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
ConcurrentHashMap, отличие от HashMap
ConcurrentHashMap — это класс в пакете java.util.concurrent, который представляет собой потокобезопасную версию HashMap. Он разработан для использования в многопоточных приложениях, где необходимо гарантировать корректность и производительность при одновременном доступе к коллекции из нескольких потоков.
Основные характеристики ConcurrentHashMap
Потокобезопасность: ConcurrentHashMap реализует эффективные механизмы блокировок для обеспечения потокобезопасного доступа к данным. В отличие от Hashtable, который синхронизирует все методы, ConcurrentHashMap использует более изящные механизмы управления доступом.
Производительность: За счет использования сегментации (в старых версиях) или уменьшенных блокировок (в новых версиях), ConcurrentHashMap обеспечивает высокую производительность в условиях многопоточного доступа.
Структура ConcurrentHashMap
Сегментация (в старых версиях): В старых версиях ConcurrentHashMap использовалась сегментация, при которой таблица хешей разбивалась на сегменты, каждый из которых был самостоятельной хеш-таблицей с собственной блокировкой. Это позволяло одновременно выполнять операции в разных сегментах без конфликтов.
Lock Striping (в новых версиях): В новых версиях ConcurrentHashMap используется механизм Lock Striping, который включает в себя более мелкие блокировки на уровне бакетов или групп бакетов, что снижает вероятность блокировок и увеличивает производительность.
Отличия ConcurrentHashMap от HashMap
Потокобезопасность: HashMap не является потокобезопасным. При одновременном доступе нескольких потоков к HashMap могут возникнуть состояния гонки и непредсказуемое поведение. В отличие от этого, ConcurrentHashMap специально разработан для безопасного использования в многопоточной среде.
Блокировки: HashMap не использует блокировки, что делает его небезопасным для многопоточного использования. ConcurrentHashMap, напротив, использует сегментацию или мелкие блокировки, что позволяет безопасно выполнять параллельные операции.
Производительность: В условиях многопоточного доступа HashMap может демонстрировать низкую производительность и некорректное поведение. ConcurrentHashMap оптимизирован для многопоточного доступа и обеспечивает более высокую производительность за счет эффективного управления блокировками.
Методы атомарных операций: ConcurrentHashMap предоставляет методы атомарных операций, такие как putIfAbsent, remove с проверкой значения и replace, которые отсутствуют в HashMap.
Пример использования ConcurrentHashMap
Полезные ссылки для более полного ознакомления с ConcurrentHashMap (спасибо авторам за их кропотливую работу):
https://habr.com/ru/articles/132884/
https://www.baeldung.com/java-concurrent-map
#Java #Training #Medium #ConcurrentHashMap
ConcurrentHashMap — это класс в пакете java.util.concurrent, который представляет собой потокобезопасную версию HashMap. Он разработан для использования в многопоточных приложениях, где необходимо гарантировать корректность и производительность при одновременном доступе к коллекции из нескольких потоков.
Основные характеристики ConcurrentHashMap
Потокобезопасность: ConcurrentHashMap реализует эффективные механизмы блокировок для обеспечения потокобезопасного доступа к данным. В отличие от Hashtable, который синхронизирует все методы, ConcurrentHashMap использует более изящные механизмы управления доступом.
Производительность: За счет использования сегментации (в старых версиях) или уменьшенных блокировок (в новых версиях), ConcurrentHashMap обеспечивает высокую производительность в условиях многопоточного доступа.
Структура ConcurrentHashMap
Сегментация (в старых версиях): В старых версиях ConcurrentHashMap использовалась сегментация, при которой таблица хешей разбивалась на сегменты, каждый из которых был самостоятельной хеш-таблицей с собственной блокировкой. Это позволяло одновременно выполнять операции в разных сегментах без конфликтов.
Lock Striping (в новых версиях): В новых версиях ConcurrentHashMap используется механизм Lock Striping, который включает в себя более мелкие блокировки на уровне бакетов или групп бакетов, что снижает вероятность блокировок и увеличивает производительность.
Отличия ConcurrentHashMap от HashMap
Потокобезопасность: HashMap не является потокобезопасным. При одновременном доступе нескольких потоков к HashMap могут возникнуть состояния гонки и непредсказуемое поведение. В отличие от этого, ConcurrentHashMap специально разработан для безопасного использования в многопоточной среде.
Блокировки: HashMap не использует блокировки, что делает его небезопасным для многопоточного использования. ConcurrentHashMap, напротив, использует сегментацию или мелкие блокировки, что позволяет безопасно выполнять параллельные операции.
Производительность: В условиях многопоточного доступа HashMap может демонстрировать низкую производительность и некорректное поведение. ConcurrentHashMap оптимизирован для многопоточного доступа и обеспечивает более высокую производительность за счет эффективного управления блокировками.
Методы атомарных операций: ConcurrentHashMap предоставляет методы атомарных операций, такие как putIfAbsent, remove с проверкой значения и replace, которые отсутствуют в HashMap.
Пример использования ConcurrentHashMap
import java.util.concurrent.ConcurrentHashMap;
import java.util.Map;
public class ConcurrentHashMapExample {
public static void main(String[] args) {
// Создание ConcurrentHashMap
Map<String, Integer> map = new ConcurrentHashMap<>();
// Добавление элементов
map.put("Apple", 50);
map.put("Banana", 30);
map.put("Orange", 20);
// Получение значения по ключу
System.out.println("Price of Apple: " + map.get("Apple"));
// Проверка наличия ключа
if (map.containsKey("Banana")) {
System.out.println("Banana is in the list.");
}
// Удаление элемента
map.remove("Orange");
// Перебор элементов
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
// Использование атомарных операций
map.putIfAbsent("Grapes", 40);
map.replace("Banana", 35);
// Перебор элементов после атомарных операций
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
Полезные ссылки для более полного ознакомления с ConcurrentHashMap (спасибо авторам за их кропотливую работу):
https://habr.com/ru/articles/132884/
https://www.baeldung.com/java-concurrent-map
#Java #Training #Medium #ConcurrentHashMap
Baeldung
A Guide to ConcurrentMap | Baeldung
A quick and practical guide to ConcurrentMap in Java.
Как вы относитесь к тому, что посты иногда разорваны? (Это из-за большого объема информации)
Anonymous Poll
67%
Все нормально
17%
Очень неудобно читать
17%
Без разницы
Что выведет код?
#Tasks
import java.util.HashMap;
import java.util.Map;
public class HashMapChallenge {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("one", 1);
map.put("two", 2);
map.put("three", 3);
map.put("four", 4);
int result = processMap(map);
System.out.println(result);
}
public static int processMap(Map<String, Integer> map) {
int sum = 0;
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (entry.getKey().length() % 2 == 0) {
sum += entry.getValue() * 2;
} else {
sum += entry.getValue() * 3;
}
}
return sum;
}
}
#Tasks
Внутренняя структура ConcurrentHashMap
ConcurrentHashMap состоит из хеш-таблицы, которая делится на сегменты (в старых версиях) или использует мелкие блокировки (в новых версиях), чтобы минимизировать блокировки и увеличить параллелизм.
Бакеты (Buckets):
Подобно HashMap, ConcurrentHashMap использует массив бакетов для хранения пар "ключ-значение".
Внутри каждого бакета используется связанный список (или дерево в случае большого числа элементов) для хранения элементов, что позволяет управлять коллизиями.
Сегменты (Segments) (в старых версиях):
В старых версиях ConcurrentHashMap массив бакетов разбивался на сегменты, каждый из которых имел свою собственную блокировку. Это позволяло нескольким потокам одновременно модифицировать разные сегменты без взаимных блокировок.
Каждый сегмент был отдельной хеш-таблицей с собственными методами вставки, поиска и удаления.
Lock Striping (в новых версиях):
В новых версиях (Java 8 и позже) ConcurrentHashMap использует более мелкие блокировки, известные как lock striping.
Вместо сегментов используется механизм блокировок на уровне бакетов или групп бакетов, что уменьшает вероятность блокировок и увеличивает производительность.
Механизмы синхронизации
Мелкие блокировки (Fine-Grained Locks):
ConcurrentHashMap использует мелкие блокировки для управления доступом к отдельным бакетам или небольшим группам бакетов.
Это позволяет нескольким потокам одновременно выполнять операции над различными частями хеш-таблицы, минимизируя блокировки и повышая параллелизм.
CAS (Compare-And-Swap):
Для некоторых операций, таких как вставка и обновление значений, используется механизм CAS, который позволяет атомарно обновлять значения без использования явных блокировок.
CAS операции обеспечивают высокую производительность и минимизируют затраты на синхронизацию.
Механизм Reentrant Lock:
Внутренне для блокировок ConcurrentHashMap использует ReentrantLock, что позволяет потокам безопасно входить в блокировку несколько раз.
ReentrantLock предоставляет больше возможностей управления, таких как блокировка с тайм-аутом и попытка блокировки без ожидания.
Внутреннее устройство бакетов
Каждый бакет в ConcurrentHashMap представлен объектом типа Node:
#Java #Training #Medium #ConcurrentHashMap
ConcurrentHashMap состоит из хеш-таблицы, которая делится на сегменты (в старых версиях) или использует мелкие блокировки (в новых версиях), чтобы минимизировать блокировки и увеличить параллелизм.
Бакеты (Buckets):
Подобно HashMap, ConcurrentHashMap использует массив бакетов для хранения пар "ключ-значение".
Внутри каждого бакета используется связанный список (или дерево в случае большого числа элементов) для хранения элементов, что позволяет управлять коллизиями.
Сегменты (Segments) (в старых версиях):
В старых версиях ConcurrentHashMap массив бакетов разбивался на сегменты, каждый из которых имел свою собственную блокировку. Это позволяло нескольким потокам одновременно модифицировать разные сегменты без взаимных блокировок.
Каждый сегмент был отдельной хеш-таблицей с собственными методами вставки, поиска и удаления.
Lock Striping (в новых версиях):
В новых версиях (Java 8 и позже) ConcurrentHashMap использует более мелкие блокировки, известные как lock striping.
Вместо сегментов используется механизм блокировок на уровне бакетов или групп бакетов, что уменьшает вероятность блокировок и увеличивает производительность.
Механизмы синхронизации
Мелкие блокировки (Fine-Grained Locks):
ConcurrentHashMap использует мелкие блокировки для управления доступом к отдельным бакетам или небольшим группам бакетов.
Это позволяет нескольким потокам одновременно выполнять операции над различными частями хеш-таблицы, минимизируя блокировки и повышая параллелизм.
CAS (Compare-And-Swap):
Для некоторых операций, таких как вставка и обновление значений, используется механизм CAS, который позволяет атомарно обновлять значения без использования явных блокировок.
CAS операции обеспечивают высокую производительность и минимизируют затраты на синхронизацию.
Механизм Reentrant Lock:
Внутренне для блокировок ConcurrentHashMap использует ReentrantLock, что позволяет потокам безопасно входить в блокировку несколько раз.
ReentrantLock предоставляет больше возможностей управления, таких как блокировка с тайм-аутом и попытка блокировки без ожидания.
Внутреннее устройство бакетов
Каждый бакет в ConcurrentHashMap представлен объектом типа Node:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V value;
volatile 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 int hashCode() {
return key.hashCode() ^ value.hashCode();
}
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
public final boolean equals(Object o) {
Object k, v, u;
Map.Entry<?,?> e;
return ((o instanceof Map.Entry) &&
(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
(v = e.getValue()) != null &&
(k == key || k.equals(key)) &&
(v == (u = value) || v.equals(u)));
}
}
#Java #Training #Medium #ConcurrentHashMap
Механизмы синхронизации
Пример использования CAS для вставки элемента:
#Java #Training #Medium #ConcurrentHashMap
Пример использования CAS для вставки элемента:
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.value;
if (!onlyIfAbsent)
e.value = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.value;
if (!onlyIfAbsent)
p.value = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
#Java #Training #Medium #ConcurrentHashMap
LinkedHashMap
LinkedHashMap — это класс из пакета java.util, который является расширением HashMap и сохраняет порядок вставки или порядок доступа к элементам. Это достигается за счет использования связанного списка, который поддерживает порядок элементов.
Основные характеристики LinkedHashMap
Порядок элементов: LinkedHashMap поддерживает порядок элементов, либо порядок вставки, либо порядок последнего доступа, в зависимости от конфигурации.
Производительность: Поиск, вставка и удаление элементов имеют сложность O(1), аналогично HashMap.
Связанный список: Внутренне LinkedHashMap использует связанный список для поддержания порядка элементов.
Структура LinkedHashMap
Бакеты (Buckets):
LinkedHashMap использует массив бакетов, аналогично HashMap. Каждый бакет представлен связным списком элементов, у которых произошла коллизия по хеш-коду.
Связанный список:
В дополнение к бакетам, LinkedHashMap использует связанный список, который соединяет все элементы в порядке их вставки или доступа. Каждый элемент содержит ссылки на предыдущий и следующий элемент, что позволяет поддерживать порядок.
Два порядка:
Порядок вставки (Insertion Order): Элементы хранятся в порядке их добавления в карту.
Порядок доступа (Access Order): Элементы перемещаются в конец списка при их доступе, что полезно для реализации LRU-кэшей (Least Recently Used).
Создание и использование LinkedHashMap
Внутреннее устройство LinkedHashMap
LinkedHashMap расширяет HashMap и добавляет дополнительную функциональность для поддержания порядка элементов.
Класс Entry:
Внутренний класс Entry наследуется от HashMap.Entry и добавляет ссылки на предыдущий и следующий элементы, что образует двусвязный список.
Указатели на первый и последний элементы:
LinkedHashMap содержит указатели на первый и последний элементы списка, что позволяет быстро выполнять вставку и удаление элементов в конец списка.
#Java #Training #Medium #LinkedHashMap
LinkedHashMap — это класс из пакета java.util, который является расширением HashMap и сохраняет порядок вставки или порядок доступа к элементам. Это достигается за счет использования связанного списка, который поддерживает порядок элементов.
Основные характеристики LinkedHashMap
Порядок элементов: LinkedHashMap поддерживает порядок элементов, либо порядок вставки, либо порядок последнего доступа, в зависимости от конфигурации.
Производительность: Поиск, вставка и удаление элементов имеют сложность O(1), аналогично HashMap.
Связанный список: Внутренне LinkedHashMap использует связанный список для поддержания порядка элементов.
Структура LinkedHashMap
Бакеты (Buckets):
LinkedHashMap использует массив бакетов, аналогично HashMap. Каждый бакет представлен связным списком элементов, у которых произошла коллизия по хеш-коду.
Связанный список:
В дополнение к бакетам, LinkedHashMap использует связанный список, который соединяет все элементы в порядке их вставки или доступа. Каждый элемент содержит ссылки на предыдущий и следующий элемент, что позволяет поддерживать порядок.
Два порядка:
Порядок вставки (Insertion Order): Элементы хранятся в порядке их добавления в карту.
Порядок доступа (Access Order): Элементы перемещаются в конец списка при их доступе, что полезно для реализации LRU-кэшей (Least Recently Used).
Создание и использование LinkedHashMap
import java.util.LinkedHashMap;
import java.util.Map;
public class LinkedHashMapExample {
public static void main(String[] args) {
// Создание LinkedHashMap с порядком вставки
LinkedHashMap<String, Integer> insertionOrderMap = new LinkedHashMap<>();
// Добавление элементов
insertionOrderMap.put("Apple", 50);
insertionOrderMap.put("Banana", 30);
insertionOrderMap.put("Orange", 20);
// Перебор элементов в порядке вставки
System.out.println("Insertion Order:");
for (Map.Entry<String, Integer> entry : insertionOrderMap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
// Создание LinkedHashMap с порядком доступа
LinkedHashMap<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);
// Добавление элементов
accessOrderMap.put("Apple", 50);
accessOrderMap.put("Banana", 30);
accessOrderMap.put("Orange", 20);
// Доступ к элементу, что изменит его порядок
accessOrderMap.get("Banana");
// Перебор элементов в порядке доступа
System.out.println("\nAccess Order:");
for (Map.Entry<String, Integer> entry : accessOrderMap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
Внутреннее устройство LinkedHashMap
LinkedHashMap расширяет HashMap и добавляет дополнительную функциональность для поддержания порядка элементов.
Класс Entry:
Внутренний класс Entry наследуется от HashMap.Entry и добавляет ссылки на предыдущий и следующий элементы, что образует двусвязный список.
static class Entry<K, V> extends HashMap.Node<K, V> {
Entry<K, V> before, after;
Entry(int hash, K key, V value, HashMap.Node<K, V> next) {
super(hash, key, value, next);
}
}
Указатели на первый и последний элементы:
LinkedHashMap содержит указатели на первый и последний элементы списка, что позволяет быстро выполнять вставку и удаление элементов в конец списка.
transient LinkedHashMap.Entry<K, V> head;
transient LinkedHashMap.Entry<K, V> tail;
#Java #Training #Medium #LinkedHashMap