data-structures - 我应该选择哪种数据结构？

Question

我正在考虑列出游戏的最高得分。超过 300,000 名玩家将按最高分排名。玩家可以通过输入他们的名字和新的最高分来更新他们的高分。一次只显示 10 个分数，用户可以输入他们想要从哪个位置开始。因此，如果他们输入“100100”，那么整个列表应该刷新，并显示第 100,100 分到第 100,109 分。那么在这种情况下我应该使用什么数据结构呢？我正在考虑使用hashTable和用户名作为键，更新他们的分数需要恒定的时间。但是如果一个用户之前的分数是第 100,100 位，并且在他更新他的分数之后，他的分数成为了整个列表中的最高分呢？然后，如果通过使用哈希表将需要线性时间因为我需要比较列表中的每个分数以确保是最高的。因此，除了使用hashTable之外，还有没有更好的数据结构可供选择？

Answer 1

使用带有分数键的基于地图（有序树）的容器和带有名称键的散列。让这些值成为存储在列表或数组等中的实体的链接。即按照您的喜好存储数据，以便为您需要快速执行的不同访问做出索引。

Answer 2

您应该选择为最常见的操作优化的数据结构。根据您对有序列表的描述，最常见的操作可能是查看列表（并在其中跳转）。

如果您使用以用户名作为键的哈希表，那么显示按分数排序的列表将非常昂贵，并且当查看者在列表中四处跳动时计算不同的视图非常昂贵。

相反，使用按分数排序的简单列表将使所有“查看”操作非常便宜且易于实现。当用户更新他们的分数时，只需O(n)按名称对用户进行线性 ( ) 搜索并删除他们的旧条目。然后，由于列表已排序，您可以及时搜索它O(log n)以找到在列表中重新插入新条目的位置。