Блог о программировании Лесних Виталия IT-блог
Аккаунт Войти / Регистрация
Тема
Размер текста
Главная > Блог — IT-Блог > Understanding multithreading in Java through collections and atomics
Understanding multithreading in Java through collections and atomics
Оглавление:

Understanding multithreading in Java through collections and atomics

Understanding Multithreading in Java through Collections and Atomics

1️⃣ HashMap / TreeMap / TreeSet (not thread-safe)

HashMap:
  • Structure: array of buckets + linked lists / trees (for collisions).
  • Under the hood: on put/remove, the array of buckets is modified and, possibly, the chains are reordered.
  • Problem with multithreading: two threads can simultaneously change one bucket → corrupt structures, loss of elements, infinite loop during iteration.
TreeMap / TreeSet:
  • Structure: red-black tree.
  • On insertion/deletion, the thread modifies several nodes of the tree.
  • Concurrent modifications → the structure of the tree can break, get/put/rebalance can throw ConcurrentModificationException or damage the balancing.

✅ Conclusion: external synchronization is needed; otherwise, the map/set easily gets corrupted.

2️⃣ SynchronizedMap / SynchronizedSortedMap / SynchronizedSortedSet

Under the hood: All methods are wrapped in synchronized (this) on the map/set object. Any operation locks the entire map/set during execution. Guarantees data integrity, but no parallel operation.

public V put(K key, V value) {
    synchronized (this) {
        return m.put(key, value);
    }
}

Read/write → one operation at a time, which eliminates race condition.

3️⃣ ConcurrentHashMap

Under the hood (Java 8+):

  • Array of buckets + nodes in trees for collisions.
  • Main synchronization:
    • get — completely lock-free.
    • put — CAS (Compare-And-Swap) at the bucket level or synchronized at the tree node, only if needed.
    • Table resizing partially synchronized at segments.
  • Concurrent put/get on different keys — executed in parallel without locking the entire map.
  • Race condition on value: if it is a mutable object inside the map, CHM does not synchronize its fields.

4️⃣ ConcurrentSkipListMap / ConcurrentSkipListSet

  • Structure: Skip List (multi-layer linked list).
  • Operations use lock-free algorithms + CAS.
  • Each level of the list is partially blocked or updated atomically.
  • Allows parallel operations on different keys.
  • Simultaneous changes of one key → race condition, if atomic methods (compute, putIfAbsent) are not used.

5️⃣ AtomicInteger / AtomicReference / AtomicLong

  • Uses CPU instructions CAS (Compare-And-Swap).
  • Update is atomic and lock-free: the same value will not be lost in concurrent threads.
  • Example: 
    AtomicInteger ai = new AtomicInteger(0);
ai.incrementAndGet(); // atomic
  • No locks at the JVM or object level — pure CAS on CPU.

Tables for Comparison: One Element, Two Threads

Collection / Object Thread 1 → Thread 2 Arrived a Little Later Thread 1 ↔ Thread 2 Started Simultaneously Under the Hood / Comment
HashMap ❌ race condition → value may be lost, structure is fine (if only one field) ❌ race condition → may corrupt the structure, data loss No synchronization, everything at the discretion of CPU threads
TreeMap / TreeSet ❌ race condition → corrupt tree or data loss ❌ race condition → corrupt tree No thread-safety, node manipulations are not atomic
SynchronizedMap / SynchronizedSortedMap / SynchronizedSortedSet ✅ safe, thread 2 waits ✅ safe, one thread waits for another Monitor blocks the entire map/set for operation
ConcurrentHashMap ⚠️ map structure is fine, but value race condition: last assignment wins ⚠️ CAS at bucket or node level → last assignment wins Map structure lock-free, object field is not protected
ConcurrentSkipListMap / Set ⚠️ skip list structure is correct, value race condition ⚠️ last assignment wins CAS at node level, value object is not atomic
AtomicInteger / AtomicReference / AtomicLong ✅ atomic, thread 2 waits in CAS only on conflict, value increases correctly ✅ atomic, CAS guarantees one update → second retries CPU CAS, lock-free, race condition excluded
Now let's consider a more complex case with simultaneous modification by two threads and at the same time a new key is added by a third thread.

Table: one element is edited by two threads + new key is added

Collection / object Code example Thread 1+2 edit element Thread 3 adds new key Under the hood / comment Data loss / corrupt
HashMap 
static Map<String,Integer> map = new HashMap<>();
 ❌ race condition, one update may be lost ❌ adding a new key may break the structure No synchronization, all threads change buckets simultaneously High risk of corrupt
TreeMap / TreeSet 
static TreeMap<String,Integer> map = new TreeMap<>();
 ❌ race condition, the tree structure may break ❌ adding a new key changes the nodes of the tree No thread safety, tree balancing breaks High risk of corrupt
SynchronizedMap / SynchronizedSortedMap / SynchronizedSortedSet 
static Map<String,Integer> map = Collections.synchronizedMap(new HashMap<>());
 ✅ Thread 1 and 2 execute sequentially (monitor lock) ✅ Thread 3 waits for completion All methods are synchronized on the object, iteration requires a lock Low, safe
ConcurrentHashMap 
static ConcurrentHashMap<String,AtomicInteger> map = new ConcurrentHashMap<>(); 
map.computeIfAbsent("key", k -> new AtomicInteger()).incrementAndGet();
 ⚠️ Race condition on value, map structure is correct ✅ Adding new key in parallel Lock-free buckets + CAS, reading lock-free Value may be lost, structure is fine
ConcurrentSkipListMap / Set 
static ConcurrentSkipListMap<String,AtomicInteger> map = new ConcurrentSkipListMap<>();
 ⚠️ Race condition on value ✅ Adding new key in parallel Skip list + CAS, lock-free Value may be lost, structure is fine
AtomicInteger / AtomicReference 
AtomicInteger ai = new AtomicInteger(); 
ai.incrementAndGet();
 ✅ atomically, both threads correctly update the value ✅ adding a new key through a separate AtomicReference object is safe CAS at the CPU level, lock-free Low, safe

🔹 Key points:

  • SynchronizedMap — methods lock the entire object, so Thread 1 and Thread 2 never execute simultaneously.
  • ConcurrentHashMap — the map structure is safe, but the object value is not atomic, so AtomicInteger or the compute method is needed.
  • Atomic objects — completely atomic, race condition is excluded.

Comparison of Thread-Safe Sorted Collections

1️⃣ Collections.synchronizedSortedMap(new TreeMap<>())
Collections.synchronizedSortedMap(new TreeMap<>())
Thread A: ─────[took monitor]─────────────> working
Thread B: ─────[waiting, monitor busy]─────┐
Thread C: ─────[waiting, monitor busy]─────┘
All operations block each other: get, put, remove, containsKey — only one thread inside at the same time.
Output:
Real tree (red-black).
Full sorting is preserved.
But there is no parallelism — everyone is waiting.

2️⃣ ConcurrentSkipListMap
Level 3: 10 --------- 30 ---------------- 75 --------- 90
Level 2: 10 ---- 25 ---- 50 ---- 60 ---- 75 ---- 90
Level 1: 10  20  25  30  40  50  60  70  75  80  90

Thread A: inserts 35
Thread B: inserts 55
Thread C: reads 30

✔ All three operations can be executed simultaneously because locks are only taken on small segments of the list.
✔ The order of keys is preserved, submaps work.
Output:
Not a tree, but a skip-list.
Sorted keys as in TreeMap.
Multithreaded, parallel, without global locking.

Property SynchronizedSortedMap(TreeMap) ConcurrentSkipListMap
Structure Red-black tree Skip-list
Order of keys Yes Yes
Thread-safety Yes, via synchronized Yes, via fine-grained locks
Parallel operation No, one thread Yes, multiple threads simultaneously
Support for subMap/headMap Yes Yes
Performance with many threads Decreases Good

🔹 Conclusions

HashMap / TreeMap / TreeSet

  • Not thread-safe.
  • Any simultaneous changes can lead to data loss, structure corruption, and infinite iterations.
  • External synchronization is required (e.g., synchronized block).

SynchronizedMap / SynchronizedSortedMap / SynchronizedSortedSet

  • Thread-safe, but all operations block the entire collection.
  • Good for infrequent operations, but poor under high concurrency.
  • Iteration requires separate synchronization on the object.

ConcurrentHashMap

  • The map structure is safe for parallel reading and writing of different keys (lock-free at the bucket level).
  • Race condition is possible only on mutable values if you just store objects without atomic operations.
  • Solution: use AtomicInteger, AtomicReference or methods like compute, computeIfAbsent.

ConcurrentSkipListMap / ConcurrentSkipListSet

  • The structure is correct, lock-free operations through CAS.
  • Parallel changes to the same key are not atomic at the value level — atomicity is needed.
  • Suitable if a sorted thread-safe set/map is required.

AtomicInteger / AtomicLong / AtomicReference

  • Completely atomic operations, lock-free.
  • No risk of losing updates, even if multiple threads change the value simultaneously.
  • Often used together with ConcurrentHashMap for safe value updates.

🔹 Practical Rule

  • If the collection is not thread-safe → either use external synchronization or replace it with a thread-safe version (ConcurrentHashMap, ConcurrentSkipListMap).
  • If you store mutable objects inside the map → use atomics or compute methods, otherwise values may be lost.
  • If maximum parallelism is needed → ConcurrentHashMap + AtomicInteger/Reference is the best option.
  • If simple synchronization without hassle is needed → Collections.synchronizedMap/Set — but remember about locking the entire collection.

Оставить комментарий

Мой канал в социальных сетях
Отправляя email, вы принимаете условия политики конфиденциальности

Полезные статьи:

Pointers, functions, and execution control in Go vs Java | Types - Language
Pointers, functions, and execution control in Go vs Java | Types - Language
Series: Go for Java Developers — analyzing pointer, closures, defer, panic/recover In this article, we will analyze how Go manages the state and lifecycle of functions. A feature of Go is the ease of…
About the author
Welcome to my IT blog, my name is Vitaly Lesnykh. I ve been in IT since 2004: I created my first website as a thesis in college, and I ve been developing apps and websites since then. I ve worked as …
Breaking down: Rate-limiter, non-blocking operations, scheduler Go vs Java | Concurrency part 4
Breaking down: Rate-limiter, non-blocking operations, scheduler Go vs Java | Concurrency part 4
This article is dedicated to understanding the principles of working with concurrency and synchronization in Go and Java. We will look at key approaches such as rate-limiter, non-blocking operations, …

Новые статьи:

🧩 Coordination: how to synchronize chaos — Java Blocking vs Reactor vs Go
Concurrency is not about “starting many threads”. It’s about agreements between them. Imagine a restaurant kitchen: — cooks (threads / goroutines) — orders (tasks) — and the main question: how do th…
When HashMap starts killing production: the engineering story of ConcurrentHashMap
When HashMap starts killing production: the engineering story of ConcurrentHashMap
Imagine a typical production service. 32 CPU hundreds of threads configuration / session / rate limits cache tens of thousands of operations per second And somewhere inside — a regular Map. At first…
Zero Allocation in Java: what it is and why it matters
Zero Allocation in Java: what it is and why it matters
Zero Allocation — is an approach to writing code in which no unnecessary objects are created in heap memory during runtime. The main idea: fewer objects → less GC → higher stability and performance. …
© 2026 IT-блог
Главная Статьи Об авторе Карта сайта
Соглашение об использовании