java - 按值排序的数据结构

Question

我正在尝试为大量玩家存储分数。因此，我需要一张根据值排序的 map ，但由于玩家数量众多，每次检索它时对其进行排序的效率很低。我还希望能够在 map 中找到玩家排名。它与 Redis 中的分数数据类型非常相似。像这样的东西:

    ScoreMap<String, Integer> scores = new ScoreMap<String, Integer>();

    scores.put("Bill", 2);
    scores.put("Tom", 6);
    scores.put("Jim", 3);
    scores.put("Jake", 3);


    System.out.println("Rank = " + scores.getRank("Bill"));

    System.out.println();
    System.out.println("All:");
    for (Entry<String, Integer> entry : scores.entrySet()) {
        System.out.println(entry.getKey() + " => " + entry.getValue());
    }

    System.out.println();
    System.out.println("Rank Range:");
    for (Entry<String, Integer> entry : scores.entryRankRange(0, 2)) {
        System.out.println(entry.getKey() + " => " + entry.getValue());
    }

    System.out.println();
    System.out.println("Score Range:");
    for (Entry<String, Integer> entry : scores.entryScoreRange(2, 3)) {
        System.out.println(entry.getKey() + " => " + entry.getValue());
    }

这将返回

    Rank = 3

    All:
    Tom => 6
    Jake => 3
    Jim => 3
    Bill => 2

    Rank Range:
    Tom => 6
    Jake => 3
    Jim => 3

    Score Range:
    Jake => 3
    Jim => 3
    Bill => 2

我知道这有点具体，我可能必须制作一个自定义数据结构。但如果能指出正确的方向，我们将不胜感激。 :)

Answer 1

最简单的方法是使用 Set (即 TreeSet )并将玩家信息(包括得分)封装到一个特定的类中:

public class CompetitivePlayer implements Comparable<CompetitivePlayer>{

    private String name;
    private int score;    

    public CompetitivePlayer(String name, int score) {
        this.name = name;
        this.score = score;
    }

    public String getName() {
        return name;
    }

    public int getScore() {
        return score;
    }

    public void incrementScore() {
        score++;
    }

    @Override
    public int compareTo(CompetitivePlayer o) {
        return score - o.score;
    }
}

TreeSet 假设存储在其中的整体实现 Comparable 用于确定其元素的自然顺序的接口(interface)。

编辑:

如果需要经常修改玩家的分数，那么Map<String, Integer>基于的解决方案更适合，因为 there's no get in Java's Set 。 This thread讨论Map基于的方法非常详细。

一种简单的解决方案(如上述线程中所建议的)是单行代码，使用 Guava图书馆:

Map<String, Integer> sortedScores = ImmutableSortedMap.copyOf(scores,
    Ordering.natural().onResultOf(Functions.forMap(scores)));