java - 游戏排行榜中的插队排名如何实现？

Question

排名	玩家ID
1	001
2	002
3	003
4	004
5	005

如玩家004打败排名为2的002玩家，排行榜将变成

排名	玩家ID
1	001
2	004
3	002
4	003
5	005

数据结构为Map<排名，玩家ID>
thks!!

Answer 1

Do not use map or list, whether it is ArrayList or LinkedList, because ArrayList is equivalent to an array, and ranking changes require updating a large number of elements. Although LinkedList is more convenient for insertion and deletion, binary search cannot be used and it is necessary to find the changed elements. The location needs to be traversed. A better implementation is to use a balanced binary tree, or directly use sortset

in redis

Answer 2

Why use map? In this way, all the data after the inserted ranking must be adjusted every time. Isn’t it possible to use a list? Use list.add(int, object)

Answer 3

To rank, there must be something similar to a score. If it doesn’t change frequently, just put it in the list and sort by score each time. If the ranking changes frequently or there are many players, maintain a maximum heap.

Answer 4

The player ranked m will be defeated by rank n, and the ranking will change
The general meaning is that all the rankings from n to m-1 are increased by 1, and then the original ranking of m is replaced by n.
If it is in the database, it can be easily processed by using sql twice. If it is stored in other text, it is easy to handle by writing a loop and increasing it by 1

Answer 5

I have done this function
I used to use ConcurrentSkipListMap<排名, uid>. Of course, if you don’t have concurrency requirements, you can also use TreeMap
Each player has a ranking value, because the ranking change only involves two players, only the ranking values ​​of the two players need to be updated:

javaint user1OldRank = user1.rank;
int user2OldRank = user2.rank;
user1.rank = user2OldRank;
user2.rank = user1OldRank;

map.put(user1.rank, user1.uid);
map.put(user2.rank, user2.uid);

The advantage of using this is that it is very fast to search for a certain period of consecutive rankings (for example, to find a certain player and the players in front of him): map.subMap(from, to)

Answer 6

The ranking is fixed, just change the key values ​​​​of the two players...