Welcome back! In our previous lesson, we explored how to implement a concurrent inventory system using ConcurrentHashMap. Today, we will take your skills further by designing a real-time, thread-safe game leaderboard using ConcurrentSkipListMap. This lesson will help you understand how to manage sorted data in a concurrent environment—an essential feature for real-time applications such as online games or financial systems.

By the end of this lesson, you will:

• Understand how ConcurrentSkipListMap maintains sorted data in a thread-safe manner.
• Learn how to update entries safely while handling concurrent modifications.
• Retrieve top-scoring entries efficiently, which is crucial for leaderboard management.

These skills will ensure you are well-equipped to handle concurrent data access challenges in applications that require real-time data sorting and updates.

Let’s dive in and start building our concurrent game leaderboard!

Before we start implementing the leaderboard, let's quickly recap ConcurrentSkipListMap and why it's well-suited for our use case.

ConcurrentSkipListMap is part of Java's java.util.concurrent package and is a thread-safe variant of TreeMap. It maintains keys in a sorted order and allows efficient retrieval of data in real time. One of the primary reasons to use ConcurrentSkipListMap is that it provides thread-safe access to the elements while ensuring that the entries are always sorted by key.

This makes it ideal for use cases like leaderboards, where you want to maintain a ranking of players by score and allow concurrent updates.

• Thread Safety: Unlike traditional collections, ConcurrentSkipListMap allows multiple threads to update the map without the need for explicit synchronization or locking.
• Sorted Order: The map automatically sorts entries based on keys (in our case, player scores), making it easy to retrieve the highest-scoring players.

However, by default, ConcurrentSkipListMap sorts the keys in ascending order. Since we want the leaderboard to rank players with the highest scores first, we need to modify the natural ordering.

To ensure that the highest scores come first, we use Collections.reverseOrder() when initializing ConcurrentSkipListMap. This reverses the natural ordering of the keys.

Java
Copy to clipboard
1private final ConcurrentSkipListMap<Double, Set<String>> scoreMap =
2    new ConcurrentSkipListMap<>(Collections.reverseOrder());

• Why Use reverseOrder(): By passing Collections.reverseOrder() to the constructor, we tell the map to sort the keys in descending order. This way, when we iterate over the map, we start with the highest scores.

We'll begin by constructing the Leaderboard class, which maintains player scores and ensures they are always sorted with the highest scores first.

Java
Copy to clipboard
1import java.util.*;
2import java.util.concurrent.*;
3
4public class Leaderboard {
5    // Map scores to players, with scores in reverse order (highest first)
6    private final ConcurrentSkipListMap<Double, Set<String>> scoreMap =
7        new ConcurrentSkipListMap<>(Collections.reverseOrder());
8    // Map players to their current scores
9    private final ConcurrentHashMap<String, Double> playerScores = new ConcurrentHashMap<>();
10}

This class uses two concurrent maps:

• ConcurrentSkipListMap (scoreMap): Stores scores mapped to sets of player names, ensuring the scores are always in descending order.
• ConcurrentHashMap (playerScores): Quickly retrieves a player’s current score, ensuring we can efficiently update a player's score.

Let’s implement the addScore() method, which will add or update a player’s score in the leaderboard:

Java
Copy to clipboard
1public void addScore(String player, double score) {
2    Double oldScore = playerScores.put(player, score);
3    if (oldScore != null) {
4        // Remove player from old score set
5        scoreMap.computeIfPresent(oldScore, (k, v) -> {
6            v.remove(player);
7            return v.isEmpty() ? null : v;
8        });
9    }
10    // Add player to new score set
11    scoreMap.compute(score, (k, v) -> {
12        if (v == null) v = ConcurrentHashMap.newKeySet();
13        v.add(player);
14        return v;
15    });
16}

• playerScores.put(): Stores the player's current score in playerScores. If the player already had a score (oldScore is not null), we remove the old score from scoreMap.

• Removing Old Score:

  • computeIfPresent(): Checks if the old score exists in scoreMap. If it does, it removes the player from the set of players with that old score.
  • Cleanup: If no players are left for that score, the score is removed from the map to prevent memory leaks.

• Adding New Score:

  • compute(): Adds the player to the new score in scoreMap. If the score isn’t already present, a new set is created, and the player is added.
  • Thread Safety: Using compute() ensures atomic updates to the map, preventing race conditions.

This method ensures that each player has only one score entry, and the leaderboard remains sorted by score at all times.

Next, let's implement the getTopNPlayers() method, which retrieves the top n players from the leaderboard. This method is crucial because it allows us to efficiently extract the highest-scoring players based on their scores, leveraging the built-in sorting mechanism of ConcurrentSkipListMap.

Java
Copy to clipboard
1public List<String> getTopNPlayers(int n) {
2    List<String> topPlayers = new ArrayList<>();
3    for (Map.Entry<Double, Set<String>> entry : scoreMap.entrySet()) {
4        for (String player : entry.getValue()) {
5            topPlayers.add(player);
6            if (topPlayers.size() == n) return topPlayers;
7        }
8    }
9    return topPlayers;
10}

Here’s how it works:

• Iterating Over the scoreMap: The ConcurrentSkipListMap is already sorted in descending order due to reverseOrder(). This allows us to start from the highest score and work our way down. We use the entrySet() to iterate over the scores and the corresponding players.

• Fetching Players for Each Score: Since the scoreMap stores scores as keys and sets of players as values, we loop through the set of players for each score. Each player is then added to our topPlayers list.

• Limiting to n Players: To ensure we only retrieve the top n players, we check the size of the topPlayers list in each iteration. As soon as the list reaches the size n, we stop the process and return the result.

This method efficiently fetches the top players in real time by leveraging the sorted order of the ConcurrentSkipListMap. As scores are updated, this method can quickly return the current highest-ranked players without additional sorting operations.

The design ensures thread safety as well. The ConcurrentSkipListMap allows concurrent reads and updates without external synchronization, making this method suitable for highly concurrent environments where multiple threads update player scores.

This approach is scalable, allowing you to retrieve top players even in large leaderboards without performance concerns, as the ConcurrentSkipListMap keeps scores sorted at all times.

Finally, we implement the displayLeaderboard() method to print the entire leaderboard in order of scores:

Java
Copy to clipboard
1public void displayLeaderboard() {
2    scoreMap.forEach((score, players) ->
3        players.forEach(player ->
4            System.out.println(player + ": " + score)));
5}

This method uses the forEach method to print each player and their score, maintaining the leaderboard’s sorted order.

• Order Maintained: Due to the reverseOrder() in scoreMap, players are displayed from the highest score to the lowest.

Here’s the full implementation of the Leaderboard class, incorporating all the methods and ensuring the highest scores are ranked first:

Java
Copy to clipboard
1import java.util.*;
2import java.util.concurrent.*;
3
4public class Leaderboard {
5    // Map scores to players, with scores in reverse order (highest first)
6    private final ConcurrentSkipListMap<Double, Set<String>> scoreMap =
7        new ConcurrentSkipListMap<>(Collections.reverseOrder());
8    // Map players to their current scores
9    private final ConcurrentHashMap<String, Double> playerScores = new ConcurrentHashMap<>();
10
11    // Add or update a player's score
12    public void addScore(String player, double score) {
13        Double oldScore = playerScores.put(player, score);
14        if (oldScore != null) {
15            // Remove player from old score set
16            scoreMap.computeIfPresent(oldScore, (k, v) -> {
17                v.remove(player);
18                return v.isEmpty() ? null : v;
19            });
20        }
21        // Add player to new score set
22        scoreMap.compute(score, (k, v) -> {
23            if (v == null) v = ConcurrentHashMap.newKeySet();
24            v.add(player);
25            return v;
26        });
27    }
28
29    // Get the top n players
30    public List<String> getTopNPlayers(int n) {
31        List<String> topPlayers = new ArrayList<>();
32        for (Map.Entry<Double, Set<String>> entry : scoreMap.entrySet()) {
33            for (String player : entry.getValue()) {
34                topPlayers.add(player);
35                if (topPlayers.size() == n) return topPlayers;
36            }
37        }
38        return topPlayers;
39    }
40
41    // Display the entire leaderboard
42    public void displayLeaderboard() {
43        scoreMap.forEach((score, players) ->
44            players.forEach(player ->
45                System.out.println(player + ": " + score)));
46    }
47}

Now, let’s simulate multiple threads updating the leaderboard concurrently.

Java
Copy to clipboard
1public class Main {
2    public static void main(String[] args) throws InterruptedException {
3        Leaderboard leaderboard = new Leaderboard();
4
5        // Thread 1 - Adding scores for group 1 of players
6        Thread t1 = new Thread(() -> {
7            leaderboard.addScore("Alice", 1500);
8            leaderboard.addScore("Bob", 1200);
9        });
10
11        // Thread 2 - Adding scores for group 2 of players
12        Thread t2 = new Thread(() -> {
13            leaderboard.addScore("Charlie", 1800);
14            leaderboard.addScore("Diana", 1600);
15        });
16
17        // Thread 3 - Updating existing scores
18        Thread t3 = new Thread(() -> {
19            leaderboard.addScore("Alice", 1900);
20            leaderboard.addScore("Eve", 1700);
21        });
22
23        // Start the threads
24        t1.start();
25        t2.start();
26        t3.start();
27
28        // Wait for all threads to finish
29        t1.join();
30        t2.join();
31        t3.join();
32
33        // Display the final leaderboard
34        System.out.println("=== Final Leaderboard ===");
35        leaderboard.displayLeaderboard();
36
37        // Display the top 3 players
38        System.out.println("\n=== Top 3 Players ===");
39        leaderboard.getTopNPlayers(3).forEach(player -> System.out.println(player));
40    }
41}

This Main class simulates multiple threads updating the leaderboard simultaneously. Each thread represents a different group of players adding or updating their scores.

• Thread Coordination: We use join() to ensure all threads complete their updates before the final leaderboard is displayed.
• Concurrency: Thanks to ConcurrentSkipListMap and ConcurrentHashMap, updates are handled in a thread-safe way without explicit locking.

Implementing a real-time, thread-safe leaderboard is essential for many applications, such as games or any competitive environment where rankings are critical. Here's why this matters:

• Real-Time Data Handling: The ConcurrentSkipListMap ensures that all updates and reads happen in a thread-safe and efficient manner.

• Data Consistency: By maintaining a sorted structure, we can easily retrieve the top-performing players in real time.

• Concurrency: Using concurrent collections like ConcurrentSkipListMap allows multiple threads to update the leaderboard without blocking each other, providing smooth and scalable performance.

Incorporating these techniques into your applications will give you the skills to manage real-time data and concurrent updates efficiently.

Now, let’s move on to the practice section and apply these concepts to more advanced challenges!