Internal Implementation of ConcurrentHashMap in Java

ConcurrentHashMap is a part of the java.util.concurrent package and is designed to handle concurrent access to the map without compromising thread safety or performance. This article provides an in-depth look at the internal implementation of ConcurrentHashMap in Java.

1. Introduction to ConcurrentHashMap

ConcurrentHashMap is a thread-safe variant of HashMap designed for concurrent access. It provides high concurrency with performance optimized for multi-threaded environments. Unlike Hashtable, ConcurrentHashMap does not lock the entire map but uses finer-grained locking mechanisms to allow concurrent reads and writes.

2. Key Concepts and Data Structures

The internal implementation of ConcurrentHashMap involves several key concepts and data structures:

2.1 Segments

In earlier versions of Java (prior to Java 8), ConcurrentHashMap was divided into segments, each acting as a separate hash table. This segmentation allowed finer-grained locking. However, in Java 8, the segmentation strategy was replaced with a more optimized approach using a single array of nodes.

2.2 Node

The Node class represents an entry in the ConcurrentHashMap. Each node contains a key-value pair, the hash of the key, and a reference to the next node in the chain (for handling collisions).

static class Node implements Map.Entry {
    final int hash;
    final K key;
    volatile V val;
    volatile Node next;

    Node(int hash, K key, V val, Node next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }

    public final K getKey() { return key; }
    public final V getValue() { return val; }
    public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
    public final String toString() { return key + "=" + val; }
    public final V setValue(V value) { throw new UnsupportedOperationException(); }
    public final boolean equals(Object o) { ... }
}

2.3 TreeBin

When the number of nodes in a bin exceeds a certain threshold, the bin is converted to a balanced tree (TreeBin) to improve performance. This structure is similar to a red-black tree.

static final class TreeBin extends Node {
    TreeNode root;
    volatile TreeNode first;
    volatile Thread waiter;
    volatile int lockState;
    // other tree-related fields and methods
}

3. Locking Mechanism

ConcurrentHashMap uses a variety of locking mechanisms to ensure thread safety while maintaining high performance. In Java 8, the primary techniques are:

3.1 CAS (Compare-And-Swap)

CAS operations are used extensively in ConcurrentHashMap to achieve lock-free reads and writes. CAS is a low-level atomic instruction that compares the current value with an expected value and, if they match, updates the value atomically.

3.2 Synchronized Blocks

For certain operations where CAS is not sufficient, synchronized blocks are used to ensure thread safety. These blocks are used sparingly to minimize contention and performance overhead.

4. Internal Operations

Let's explore some key internal operations of ConcurrentHashMap, such as get, put, and remove.

4.1 get Operation

The get operation is lock-free and uses volatile reads to ensure visibility of changes made by other threads. It traverses the bin list or tree to find the matching key.

public V get(Object key) {
    Node[] tab; Node e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

4.2 put Operation

The put operation uses CAS to insert a new node if the bin is empty. If the bin is not empty, it locks the bin and inserts the new node, converting the bin to a tree if necessary.

final V putVal(K key, V value, boolean onlyIfAbsent) {
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node[] tab = table;;) {
        Node f; int n, i, fh; K fk;
        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(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 e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node(hash, key,
                                                         value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node p;
                        binCount = 2;
                        if ((p = ((TreeBin)f).putTreeVal(hash, key,
                                                              value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

4.3 remove Operation

The remove operation also uses synchronized blocks to ensure thread safety when removing a node. It traverses the bin list or tree to find and remove the matching node.

public V remove(Object key) {
    return replaceNode(key, null, null);
}

final V replaceNode(Object key, V value, Object cv) {
    int hash = spread(key.hashCode());
    for (Node[] tab = table;;) {
        Node f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0 ||
            (f = tabAt(tab, i = (n - 1) & hash)) == null)
            break;
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
            else {
V oldVal = null;
boolean validated = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
validated = true;
for (Node e = f, pred = null;;) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key || (ek != null && key.equals(ek)))) {
V ev = e.val;
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
oldVal = ev;
if (value != null)
e.val = value;
else if (pred != null)
pred.next = e.next;
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}
}
else if (f instanceof TreeBin) {
validated = true;
TreeBin t = (TreeBin)f;
TreeNode r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val;
if (cv == null || cv == pv ||
(pv != null && cv.equals(pv))) {
oldVal = pv;
if (value != null)
p.val = value;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
if (validated) {
if (oldVal != null) {
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
return null;
}

Conclusion

ConcurrentHashMap is a powerful and efficient implementation of a thread-safe hash map in Java. Its internal design, including the use of CAS operations, synchronized blocks, and tree bins, allows it to handle high concurrency with minimal performance overhead. Understanding the internal workings of ConcurrentHashMap can help developers make better use of this data structure in their concurrent applications.

Jakarta EE Framework in Java: A Comprehensive Guide

Jakarta EE, formerly known as Java EE (Java Platform, Enterprise Edition), is a set of specifications that extend the Java SE (Standard Edition) with specifications for enterprise features such as distributed computing and web services. This article explores the key components of the Jakarta EE framework and how it can be used to build robust, scalable enterprise applications in Java.

1. Introduction to Jakarta EE

Jakarta EE is a collection of APIs and libraries that simplify the development of large-scale, multi-tiered, scalable, and secure enterprise applications. The transition from Java EE to Jakarta EE represents the move from Oracle stewardship to the Eclipse Foundation, which now manages the evolution of the platform.

2. Core Components of Jakarta EE

Jakarta EE consists of several APIs that provide a wide range of functionalities. Here are some of the core components:

2.1 Jakarta Servlet

Jakarta Servlet defines the APIs to generate dynamic web content. It allows Java objects (servlets) to respond to requests from clients, typically browsers.

// Example of a simple servlet
import jakarta.servlet.ServletException;
import jakarta.servlet.annotation.WebServlet;
import jakarta.servlet.http.HttpServlet;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;
import java.io.IOException;
import java.io.PrintWriter;

@WebServlet("/hello")
public class HelloServlet extends HttpServlet {
    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        resp.setContentType("text/html");
        PrintWriter out = resp.getWriter();
        out.println("<h1>Hello, Jakarta EE!</h1>");
    }
}

2.2 Jakarta Server Faces (JSF)

Jakarta Server Faces (JSF) is a framework for building user interfaces for web applications. It simplifies the development of web-based user interfaces by using reusable UI components.

<!-- Example of a simple JSF page -->
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml"
      xmlns:h="http://xmlns.jcp.org/jsf/html">
<h:head>
    <title>Hello JSF</title>
</h:head>
<h:body>
    <h:form>
        <h:outputText value="Hello, JSF!" />
    </h:form>
</h:body>
</html>

2.3 Jakarta Persistence (JPA)

Jakarta Persistence (JPA) is a specification for object-relational mapping and data persistence. It simplifies database operations by mapping Java objects to database tables.

// Example of a JPA entity
import jakarta.persistence.Entity;
import jakarta.persistence.Id;

@Entity
public class User {
    @Id
    private Long id;
    private String name;

    // Getters and setters
    public Long getId() {
        return id;
    }

    public void setId(Long id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

2.4 Jakarta Dependency Injection (CDI)

Jakarta Contexts and Dependency Injection (CDI) provides a powerful type-safe dependency injection framework. It enables loose coupling between components and helps manage the lifecycle and interaction of stateful components.

// Example of CDI injection
import jakarta.enterprise.context.RequestScoped;
import jakarta.inject.Inject;
import jakarta.inject.Named;

@Named
@RequestScoped
public class UserBean {
    @Inject
    private UserService userService;

    public String getUserName() {
        return userService.getUserName();
    }
}

import jakarta.enterprise.context.ApplicationScoped;

@ApplicationScoped
public class UserService {
    public String getUserName() {
        return "John Doe";
    }
}

2.5 Jakarta RESTful Web Services (JAX-RS)

Jakarta RESTful Web Services (JAX-RS) is a specification for creating RESTful web services in Java. It provides a set of APIs to create, consume, and secure RESTful web services.

// Example of a simple JAX-RS resource
import jakarta.ws.rs.GET;
import jakarta.ws.rs.Path;
import jakarta.ws.rs.Produces;
import jakarta.ws.rs.core.MediaType;

@Path("/greeting")
public class GreetingResource {
    @GET
    @Produces(MediaType.TEXT_PLAIN)
    public String getGreeting() {
        return "Hello, Jakarta EE!";
    }
}

3. Benefits of Jakarta EE

Using Jakarta EE for enterprise application development offers several benefits:

• Standardization: Jakarta EE provides a set of standardized APIs and libraries, ensuring consistency and compatibility across different implementations.
• Scalability: Jakarta EE applications can be easily scaled to handle large volumes of transactions and users.
• Security: Jakarta EE includes built-in security features and standards to protect applications from common vulnerabilities.
• Community Support: Jakarta EE is supported by a large and active community, providing extensive resources, documentation, and support.

4. Getting Started with Jakarta EE

To get started with Jakarta EE, you need to set up your development environment. Here are the steps to create a simple Jakarta EE application:

4.1 Set Up Your Development Environment

• Install JDK (Java Development Kit).
• Choose an IDE (Integrated Development Environment) such as Eclipse, IntelliJ IDEA, or NetBeans.
• Set up a Jakarta EE-compatible application server such as Payara, WildFly, or Apache TomEE.

4.2 Create a New Jakarta EE Project

// Example of Maven configuration (pom.xml)
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0
                             http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>com.example</groupId>
    <artifactId>jakartaee-example</artifactId>
    <version>1.0-SNAPSHOT</version>

    <dependencies>
        <dependency>
            <groupId>jakarta.platform</groupId>
            <artifactId>jakarta.jakartaee-api</artifactId>
            <version>9.1.0</version>
            <scope>provided</scope>
        </dependency>
    </dependencies>

    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-war-plugin</artifactId>
                <version>3.3.1</version>
                <configuration>
                    <failOnMissingWebXml>false</failOnMissingWebXml>
                </configuration>
            </plugin>
        </plugins>
    </build>
</project>

4.3 DeployYour Application

Deploy your application to the application server and access it through the provided URL to see it in action.

Conclusion

Jakarta EE provides a robust framework for building enterprise applications in Java. Its comprehensive set of APIs and standards simplifies the development process, ensuring scalability, security, and maintainability. By following this guide, you can get started with Jakarta EE and leverage its powerful features to develop high-quality enterprise applications.