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

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

不使用map或list，不论是ArrayList还是LinkedList，因为ArrayList相当于数组，排名变化需要更新大量的元素，而LinkedList虽然插入删除比较方便，但是因为不能使用二分查找，要查找到变更后的位置需要遍历。比较好的实现方式是使用平衡二叉树，或者直接使用redis中的sortset

Answer 2

为什么要用map？这样每次都要把插入名次之后的所有数据做调整，用list不行么?使用list.add(int,object)

Answer 3

要排名肯定有一个类似分数的东西，如果不频繁变动，放list里每次按分数排序就可以了。如果名次变动比较频繁或者玩家比较多，维护一个最大堆。

Answer 4

排名m的打败排名为n，排行榜变化
大概意思就是排名n至m-1的全部各增加1，然后原来那m的排名换成n。
如果在数据库，用sql分两次很好处理。如果是其他文本储存的写个循环增加1也很好处理

Answer 5

这种功能我做过
以前我用的是ConcurrentSkipListMap<排名, uid>,当然如果你没有并发需求的话也可以用TreeMap
每个玩家有一个排名值,因为排名变化只涉及到两个玩家,只用更新两个玩家的排名值就可以了:

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);

用这个的好处是查找某一段连续的排名(比如说查找某个玩家以及他前面几名)很快:map.subMap(from, to)

Answer 6

排名固定的嘛,直接把两位玩家的key值换一下..