如果是线程安全的，任何增加并发的机会

Question

class AnagramGameDefault 模拟一个 Anagram 游戏。

submitScore()要重新计算位置，得分最高的位置为1，同一位置可以有多个玩家。

getLeaderBoard() 为用户获取条目加上上面两个和下面两个。

我的顾虑：

我测试了多个线程的代码，我想它可以工作，但我想知道代码中是否存在竞争条件或共享状态失败

我通过 'synchronized' 使用了相当严格的互斥锁。我不认为这可以避免，因为 submitScore() 和 getLeaderBoard() 严重依赖于分数的排序和正确位置，但有可能吗？我读了一些关于 ReentrantLock 的内容，但它更适合有多次读取和较少写入的情况，在这种情况下，即使读取也需要计算。

public enum AnagramGameDefault{

INSTANCE;

private Map<String, Entry> leaderBoardUserEntryMap;

{
    leaderBoardUserEntryMap = new LinkedHashMap<>();
}

public int calculateScore(String word, String anagram) {

    if (word == null || anagram == null) {
        throw new NullPointerException("Both, word and anagram, must be non-null");
    }

    char[] wordArray = word.trim().toLowerCase().toCharArray();
    char[] anagramArray = anagram.trim().toLowerCase().toCharArray();

    int[] alphabetCountArray = new int[26];

    int reference = 'a';

    for (int i = 0; i < wordArray.length; i++) {
        if (!Character.isWhitespace(wordArray[i])) {
            alphabetCountArray[wordArray[i] - reference]++;
        }
    }
    for (int i = 0; i < anagramArray.length; i++) {
        if (!Character.isWhitespace(anagramArray[i])) {
            alphabetCountArray[anagramArray[i] - reference]--;
        }
    }

    for (int i = 0; i < 26; i++)
        if (alphabetCountArray[i] != 0)
            return 0;

    return word.length();

}

public void submitScore(String uid, int score) {

    Entry newEntry = new Entry(uid, score);
    sortLeaderBoard(newEntry);
}

private void sortLeaderBoard(Entry newEntry) {

    synchronized (leaderBoardUserEntryMap) {
        leaderBoardUserEntryMap.put(newEntry.getUid(), newEntry);

        // System.out.println("Sorting for " + newEntry);

        List<Map.Entry<String, Entry>> list = leaderBoardUserEntryMap.entrySet().stream()
                .sorted(Map.Entry.comparingByValue(Collections.reverseOrder())).collect(Collectors.toList());
        leaderBoardUserEntryMap.clear();

        int position = 0;
        int previousPosition = 0;
        int currentPosition = 0;

        for (Map.Entry<String, Entry> entry : list) {
            currentPosition = entry.getValue().getScore();
            if (!(currentPosition == previousPosition))
                position++;

            entry.getValue().setPosition(position);
            leaderBoardUserEntryMap.put(entry.getKey(), entry.getValue());

            previousPosition = currentPosition;

        }
    }

}

public List<Entry> getLeaderBoard(String uid) {

    final int maxEntriesAroundAnEntry = 2;

    if (!leaderBoardUserEntryMap.containsKey(uid))
        return Collections.emptyList();

    Entry userEntry = null;

    final List<Entry> leaderBoard = new ArrayList<>();
    List<Entry> lowerEntries = null;
    List<Entry> higherEntries = null;

    synchronized (leaderBoardUserEntryMap) {

        printBoard();

        userEntry = leaderBoardUserEntryMap.get(uid);
        int userPosition = userEntry.getPosition();
        int upperPosition = userPosition - maxEntriesAroundAnEntry;
        int lowerPosition = userPosition + maxEntriesAroundAnEntry;

        // Higher entries
        higherEntries = leaderBoardUserEntryMap.values().stream()
                .filter(entry -> (entry.getPosition() < userPosition && entry.getPosition() >= upperPosition))
                .map(entry -> new Entry(entry.getUid(), entry.getScore(), entry.getPosition()))
                .collect(Collectors.toList());

        // Lower entries
        lowerEntries = leaderBoardUserEntryMap.values().stream()
                .filter(entry -> (entry.getPosition() > userPosition && entry.getPosition() <= lowerPosition))
                .map(entry -> new Entry(entry.getUid(), entry.getScore(), entry.getPosition()))
                .collect(Collectors.toList());

        userEntry = new Entry(userEntry.getUid(), userEntry.getScore(), userEntry.getPosition());

        // }

        if (higherEntries != null && !higherEntries.isEmpty()) {

            if (higherEntries.size() >= maxEntriesAroundAnEntry) {
                higherEntries = higherEntries.subList(higherEntries.size() - maxEntriesAroundAnEntry,
                        higherEntries.size());
            }

            leaderBoard.addAll(higherEntries);
        }

        leaderBoard.add(userEntry);

        if (lowerEntries != null && !lowerEntries.isEmpty()) {

            if (lowerEntries.size() >= maxEntriesAroundAnEntry) {
                lowerEntries = lowerEntries.subList(0, maxEntriesAroundAnEntry);
            }

            leaderBoard.addAll(lowerEntries);
        }
    }

    return leaderBoard;
}

public void printBoard() {

    System.out.println("---------Start : Current leader board---------");
    leaderBoardUserEntryMap.forEach((key, value) -> {
        System.out.println("BOARD ENTRY : " + key + " : " + value);
    });
    System.out.println("---------End : Current leader board---------");
}

}

POJO 条目：

public class Entry implements Comparable<Entry> {

    private String uid;
    private int score;
    private int position;

    public Entry(String uid, int score) {

        this.uid = uid;
        this.score = score;

    }

    public Entry(String uid, int score, int position) {

        this.uid = uid;
        this.score = score;
        this.position = position;
    }

    public Entry() {

    }

    public String getUid() {
        return uid;
    }

    public void setUid(String uid) {
        this.uid = uid;
    }

    public int getScore() {
        return score;
    }

    public void setScore(int score) {
        this.score = score;
    }

    public int getPosition() {
        return position;
    }

    public void setPosition(int position) {
        this.position = position;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + score;
        result = prime * result + ((uid == null) ? 0 : uid.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Entry other = (Entry) obj;
        if (score != other.score)
            return false;
        if (uid == null) {
            if (other.uid != null)
                return false;
        } else if (!uid.equals(other.uid))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return "Entry [uid=" + uid + ", score=" + score + ", position=" + position + "]";
    }

    @Override
    public int compareTo(Entry o) {
        // TODO Auto-generated method stub
        if (o == null)
            return -1;

        return Integer.compare(score, o.getScore());
    }

}

测试人员class：

public class AnagramGameDefaultDemo {

    public static void main(String[] args) {

        if (args == null || args.length < 1) {
            System.out.println("Enter testing approach - 1 for single threaded, 2 for multi-threaded");
            return;
        }

        switch (args[0]) {

        case "1": {
            new AnagramGameDefaultDemo().testSingleThreaded();
            break;
        }

        case "2": {
            new AnagramGameDefaultDemo().testMultithreaded();
            break;
        }

        default: {
            System.out.println("Enter proper option(1 or 2)");
            break;
        }
        }

    }

    private void testMultithreaded() {

        Map<String, String> stringAnagramMap = new HashMap<>();

        CountDownLatch countDownLatchOne = new CountDownLatch(1);

        stringAnagramMap.put("raw", "war");
        stringAnagramMap.put("raw", "wars");
        AnagramGamePlayer jake = new AnagramGamePlayer("jake", stringAnagramMap, countDownLatchOne);
        new Thread(jake, "jake").start();

        stringAnagramMap.clear();

        stringAnagramMap.put("tool", "loot");
        AnagramGamePlayer ace = new AnagramGamePlayer("ace", stringAnagramMap, countDownLatchOne);
        new Thread(ace, "ace").start();

        stringAnagramMap.clear();

        stringAnagramMap.put("William Shakespeare", "I am a weakish speller");
        AnagramGamePlayer max = new AnagramGamePlayer("max", stringAnagramMap, countDownLatchOne);
        new Thread(max, "max").start();

        stringAnagramMap.clear();

        stringAnagramMap.put("School master", "The classroom");
        AnagramGamePlayer tBone = new AnagramGamePlayer("tBone", stringAnagramMap, countDownLatchOne);
        new Thread(tBone, "tBone").start();

        stringAnagramMap.clear();

        countDownLatchOne.countDown();

        CountDownLatch countDownLatchTwo = new CountDownLatch(1);

        stringAnagramMap.put("Punishments", "Nine Thumps");
        AnagramGamePlayer razor = new AnagramGamePlayer("razor", stringAnagramMap, countDownLatchTwo);
        new Thread(razor, "razor").start();

        stringAnagramMap.clear();

        stringAnagramMap.put("Dormitory", "Dirty Room");
        AnagramGamePlayer chip = new AnagramGamePlayer("chip", stringAnagramMap, countDownLatchTwo);
        new Thread(chip, "chip").start();

        stringAnagramMap.clear();

        countDownLatchTwo.countDown();

        CountDownLatch countDownLatchThree = new CountDownLatch(1);

        stringAnagramMap.put("Mother in law", "Hitler woman");
        AnagramGamePlayer dale = new AnagramGamePlayer("dale", stringAnagramMap, countDownLatchThree);
        new Thread(dale, "dale").start();

        countDownLatchThree.countDown();

        stringAnagramMap.clear();
    }

    private final class AnagramGamePlayer implements Runnable {

        private Map<String, String> stringAnagramMap = new HashMap<>();
        private String uid;
        private CountDownLatch countDownLatch;

        public AnagramGamePlayer(String uid, Map<String, String> stringAnagramMap, CountDownLatch countDownLatch) {
            this.stringAnagramMap.putAll(stringAnagramMap);
            this.uid = uid;
            this.countDownLatch = countDownLatch;
        }

        @Override
        public void run() {
            AnagramGameDefault anagramGameDefault = AnagramGameDefault.INSTANCE;

            try {
                countDownLatch.await();
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }

            System.out.println("Player " + uid + " started playing with " + stringAnagramMap);
            stringAnagramMap.entrySet().forEach(entry -> {
                anagramGameDefault.submitScore(uid,
                        anagramGameDefault.calculateScore(entry.getKey(), entry.getValue()));
                printLeaderBoard(uid, anagramGameDefault.getLeaderBoard(uid));

            });

            System.out.println("Player " + uid + " completed playing");
        }

    }

    private void testSingleThreaded() {
        AnagramGameDefault anagramGameDefault = AnagramGameDefault.INSTANCE;
        anagramGameDefault.submitScore("Jake", 3);
        anagramGameDefault.submitScore("Ace", 7);
        anagramGameDefault.submitScore("Max", 1);
        anagramGameDefault.submitScore("T-Bone", 14);
        anagramGameDefault.submitScore("Razor", 6);
        anagramGameDefault.submitScore("Razor", 7);
        anagramGameDefault.submitScore("He-Man", 4);
        anagramGameDefault.submitScore("Men-at-Arms", 8);
        anagramGameDefault.submitScore("BattleCat", 3);
        anagramGameDefault.submitScore("Jake", 2);
        anagramGameDefault.submitScore("BattleCat", 3);
        anagramGameDefault.printBoard();

        anagramGameDefault.submitScore("Men-at-Arms", 21);
        anagramGameDefault.submitScore("Orko", 20);
        anagramGameDefault.submitScore("Jake", 4);
        anagramGameDefault.printBoard();

        System.out.println();
        printLeaderBoard("user5", anagramGameDefault.getLeaderBoard("user5"));
        System.out.println();
        printLeaderBoard("user4", anagramGameDefault.getLeaderBoard("user4"));
        System.out.println();
        printLeaderBoard("user15", anagramGameDefault.getLeaderBoard("user15"));
        System.out.println();
        List<Entry> entries = anagramGameDefault.getLeaderBoard("user1");
        printLeaderBoard("user1", entries);

        System.out.println("Changing state of the received entries");
        entries.forEach(entry -> {
            entry.setPosition(1);
            entry.setScore(0);
        });

        anagramGameDefault.printBoard();
        printLeaderBoard("user1", anagramGameDefault.getLeaderBoard("user1"));
    }

    private static void printLeaderBoard(String user, List<Entry> leaderBoard) {

        if (user == null || leaderBoard.isEmpty()) {
            System.out.println("Either user " + user + " doesn't exist or leader board is empty " + leaderBoard);
        }

        System.out.println("**********Printing leader board for " + user);
        leaderBoard.forEach(System.out::println);
        System.out.println("**********");
    }

}

Answer 1

看起来你在整个事情中唯一的共享状态是 leaderBoardUserEntryMap。您在 sortLeaderBoard 中更新时同步它。在 getLeaderBoard 中，出于某种原因，您在检查 if (!leaderBoardUserEntryMap.containsKey(uid)) 时尚未对其进行同步。这是次要的，但你也应该这样做。以后建排行榜的时候在上面同步

从这个角度来看，您的同步似乎足够了。

我觉得有点问题的是你的 Entry 是可变的并且存储 position。这使您的更新操作更有问题。您必须在每次更新时重新排序和重新设置位置。而且您正在锁定所有其他更新甚至读取操作。我会避免在多线程代码中使用可变对象。

我会改用 SortedSet 并让实现处理排序。要找出元素的位置，您只需执行 set.headSet(element).size() + 1。所以根本不需要存储位置。

我最初想建议使用像 ConcurrentHashSet 这样的并发集合实现，这将允许 "full concurrency of retrievals and adjustable expected concurrency for updates"。基本上，检索可以是非阻塞的，只有更新是。

但是，这不会有多大帮助，因为您的 "retrieval" 逻辑（围绕目标条目创建排行榜）并不那么简单并且涉及多次读取。所以我认为最好不要使用并发集合，而是在集合上实际同步并使更新和检索尽可能紧凑。如果您放弃在 Entry 中使用 position 的想法，那么更新就是微不足道的 add。然后你只需要尽可能快地读取条目周围的条目（在同步块内）。这对于树集来说应该相当快。

如果是线程安全的，任何增加并发的机会

If thread-safe, any chances to make more concurrent

java

multithreading

java-threads