ConcurrentMap

ConcurrentHashMap is a multi-threaded implementation of the Map interface from the java.util.concurrent package. Its main goal is to provide efficient data storage in a multi-threaded environment, where concurrent access from multiple threads is necessary, and this is achieved without fully locking the entire data structure. ConcurrentHashMap allows simultaneous read and write operations by different threads thanks to a specific internal implementation that reduces conflicts during access.

Key Features of ConcurrentHashMap

• Concurrent Access: ConcurrentHashMap provides concurrent access to data for both read and write operations, allowing multiple threads to operate on the map simultaneously. This is achieved through a special segmentation or partitioning mechanism.
• Partial Locking for Write Operations: Instead of locking the entire map, ConcurrentHashMap only locks specific parts of the map during write operations, allowing other threads to access different parts at the same time.
• No Locking for Read Operations: Read operations (get()) are performed without locking, which significantly reduces latency in a multi-threaded environment.

How ConcurrentHashMap Works Under the Hood

ConcurrentHashMap uses various approaches to achieve safe and efficient multi-threaded data access. The key principles of its implementation include:

Bucket Segmentation (Sharding):

• The map is divided into multiple segments or buckets, each of which can be locked independently of the others. This allows multiple threads to simultaneously perform operations in different segments of the map, significantly reducing synchronization overhead and increasing parallelism.
• In earlier versions of Java (before Java 8), the concept of Segment was used, which represented individually locked parts of the map. Starting from Java 8, ConcurrentHashMap uses an array of Node<K,V>, where each segment is a bucket with its own synchronization.

CAS (Compare-And-Swap):

• To ensure atomic operations, ConcurrentHashMap uses the CAS algorithm. CAS allows an operation to proceed only if the value being checked has not changed since the start of the operation. This avoids additional locking during simultaneous data updates and improves performance.
• Advantage: High efficiency for small, frequently repeated operations such as updating counters.
• Disadvantage: If many threads attempt to change the same value, frequent failed attempts (known as "spin cycles") can reduce performance.

Lock-Free Reads:

• Most read operations (get()) are performed without locking by using volatile and special memory access control mechanisms. This allows threads to get up-to-date data without needing to lock the entire structure.
• Advantage: This significantly reduces latency for reads, especially in scenarios where the map is accessed mainly for reading.
• Disadvantage: In case of structural changes (e.g., resizing or deletion), there may be consistency issues that require additional mechanisms.

Resizing:

• When the number of elements in ConcurrentHashMap exceeds a certain threshold, automatic resizing (increasing the size of the bucket array) is performed. Resizing is done gradually to avoid the need to stop all threads.
• Increasing the Table Size: To increase the table size, ConcurrentHashMap uses a gradual expansion mechanism where each thread that performs operations on the map also participates in the element transfer process (rehashing). This means that new buckets are gradually filled with elements, and this process occurs in parts, avoiding stopping all threads.
• Redistributing Objects in Buckets: During resizing, objects are redistributed to new buckets. Each element is moved to a new bucket according to the new hash value and table size. This ensures load balancing between buckets and reduces collisions.
• Reducing Table Size: ConcurrentHashMap does not have an automatic mechanism to reduce the table size, as the main focus is on maintaining stable performance in a multi-threaded environment. Reducing the table size could lead to significant overhead for resizing, so this option is not available.

Requirements for Objects Added to the Map

There is no need to implement special interfaces for using objects in ConcurrentHashMap. However, there are some recommendations:

• Immutability of Keys: Keys added to ConcurrentHashMap should be immutable. This is necessary so that the hash value does not change after adding to the map, which could lead to access errors.
• Implementation of equals() and hashCode(): Objects used as keys should correctly implement the equals() and hashCode() methods to ensure the correctness of search and insertion operations. This is particularly important to avoid collisions and to correctly distribute elements across buckets.
• Serialization: If ConcurrentHashMap is to be used in environments where serialization is required (e.g., for state persistence or network transfer), the objects stored in the map must implement the Serializable interface.

Implementation of ConcurrentSkipListMap

ConcurrentSkipListMap is another implementation of a multi-threaded map that provides ordered storage of keys. It uses a skip list structure to achieve high efficiency in sorted operations such as search, insert, and delete.

Key Features of ConcurrentSkipListMap

• Ordering: Unlike ConcurrentHashMap, ConcurrentSkipListMap ensures elements are ordered based on the natural order of keys or a comparator.
• Multi-Threaded Access: Using synchronization mechanisms allows read and write operations to be performed concurrently by multiple threads, similar to ConcurrentHashMap.
• High Efficiency for Ordered Operations: Thanks to the skip list, ordering operations are performed with logarithmic complexity (O(log n)), which is very efficient for large data sets.

How ConcurrentSkipListMap Works Under the Hood

Skip List:

• ConcurrentSkipListMap uses a skip list, which is an alternative to balanced trees. A skip list allows ordered operations (search, insert, delete) with efficiency similar to trees, but with a simpler implementation.
• The skip list structure consists of several levels of linked lists that allow quick traversal between elements, reducing the number of required steps.

CAS and Lock-Free Operations:

• Like ConcurrentHashMap, ConcurrentSkipListMap uses the CAS mechanism to ensure atomicity and avoid locks where possible.
• Advantage: High efficiency when multiple threads are performing concurrent operations.
• Disadvantage: It may be less efficient in cases with a high number of key collisions, as ordering requires additional resources.

Minimal Locking:

Thanks to the use of skip lists and the CAS algorithm, ConcurrentSkipListMap provides minimal locking during operations, which allows high efficiency in a multi-threaded environment.

Advantages and Disadvantages of ConcurrentSkipListMap

Advantages:

• Ordering: Thanks to the ordered structure, ConcurrentSkipListMap is ideal for scenarios where access to elements in a certain order is needed.
• High Efficiency for Ordered Operations: Insert, delete, and search operations are performed with logarithmic complexity.

Disadvantages:

• Additional Overhead: Maintaining ordering requires additional resources, which can reduce performance compared to unordered structures like ConcurrentHashMap.
• Complexity in Implementation: Using a skip list makes the structure more complex, which can complicate debugging.

import java.util.concurrent.ConcurrentSkipListMap;
import java.util.Comparator;

@Data
class HotTea implements Comparable<HotTea> {
    private String name;
    private boolean hasSugar;
    private boolean hasLemon;

    public HotTea(String name, boolean hasSugar, boolean hasLemon) {
        this.name = name;
        this.hasSugar = hasSugar;
        this.hasLemon = hasLemon;
    }

// used to sort by tea name
    @Override
    public int compareTo(HotTea other) {
        return this.name.compareTo(other.name);
    }
}

public class SkipListMapExample {
    public static void main(String[] args) {

  ConcurrentSkipListMap<HotTea, String> teaMap = new ConcurrentSkipListMap<>();

        teaMap.put(new HotTea("Earl Grey", true, false), "Strong");
        teaMap.put(new HotTea("Green Tea", false, true), "Light");
        teaMap.put(new HotTea("Black Tea", true, true), "Strong");
        teaMap.forEach((key, value) -> {
            System.out.println(key + " -> " + value);
        });
    }
}
        

Comparison of ConcurrentHashMap and ConcurrentSkipListMap

Let’s take a closer look at some of the issues that arise during the implementation and use of this technology. In particular, it is important to focus on practical aspects of integration that developers may encounter, such as performance optimization, ensuring security, and managing scalability and system resilience. By analyzing these issues, we can better understand how to avoid potential problems and achieve maximum efficiency from using the technology in real-world scenarios.

Why is ConcurrentHashMap needed when HashMap and Hashtable are already available?

ConcurrentHashMap focuses on performance and safety in a multi-threaded environment. Hashtable is thread-safe but has poor performance due to synchronization of all methods, including get(). HashMap allows parallel access but is not thread-safe, which can cause problems during simultaneous reads and writes.

ConcurrentHashMap combines the advantages of HashMap and Hashtable, effectively solving performance and thread-safety issues.

Can multiple threads read and write to the same or different segments of ConcurrentHashMap simultaneously?

• Read Operation (get()): Two threads can read data from the same or different segments simultaneously without blocking each other.
• Write Operation (put()): Threads can write data to different segments simultaneously, but not to the same segment.
• Read-Write Operation: A thread writing to a segment and another thread reading from the same segment can operate simultaneously. Reads are not blocked even during updates.

Is the segment array size always the same as the concurrencyLevel?

No, the segment array size does not necessarily match the concurrencyLevel. For example, if concurrencyLevel is 10, the segment size will be 16, as it must be a power of two greater than or equal to concurrencyLevel.

How does ConcurrentHashMap handle rehashing while other threads are writing?

Rehashing in ConcurrentHashMap is done separately for each segment, allowing other segments to continue working while one is being rehashed.

Conclusion

ConcurrentHashMap and ConcurrentSkipListMap are powerful tools for working with data in a multi-threaded environment, each with its own advantages and disadvantages. ConcurrentHashMap is an excellent choice for unordered storage with high efficiency, while ConcurrentSkipListMap is suitable for scenarios requiring ordered access to data. The choice between these implementations depends on the specific requirements for ordering, performance, and implementation complexity.

Fun Fact: Why is the thread always so tense? – Because it doesn't have a join! ??