我應該選擇哪種數據結構？

Question

我想列出遊戲的最高分數。超過30萬名玩家將按他們的最高分排列。玩家可以通過輸入他們的名字和新的最高分來更新他們的高分。一次只顯示10個分數，並且用戶可以鍵入他們想從哪個位置開始。因此，如果他們鍵入「100100」，那麼整個列表應刷新，並通過第100,109個分數向他們顯示100,100分。那麼在這種情況下我應該使用哪種數據結構？我想用hashTable與用戶的名字作爲關鍵，它將需要不斷的時間來更新他們的分數。但是如果用戶以前的得分是100,100，那麼在他更新他的得分之後，他的得分成爲整個列表中的最高得分？然後，如果使用散列表，則需要線性時間，因爲我需要比較列表中的每個分數以確保是最高分數。因此，有沒有更好的數據結構可以選擇使用hashtable？

Answer 1

您應該選擇針對最常見操作進行了優化的數據結構。通過對有序列表的描述，最常見的操作可能是查看列表（並在其中跳躍）。

如果你使用一個用戶名作爲鍵的哈希表，那麼顯示按分數排序的列表將非常昂貴，而當查看器在列表中跳過時，計算不同視圖會非常昂貴。

相反，使用按分數排序的簡單列表將使所有「查看」操作非常便宜並且非常容易實現。當用戶更新他們的分數時，只需按名稱對用戶進行線性（O(n)）搜索並刪除他們的舊條目。然後，由於該列表已排序，因此您可以在O(log n)時間內搜索該列表，以查找將新條目重新插入列表中的位置。

Answer 2

使用帶有分數鍵和帶名稱鍵的散列的基於映射（有序樹）的容器。讓這些值成爲存儲在列表或數組等中的實體的鏈接，即按照您喜歡的方式存儲數據爲您需要快速執行的不同訪問創建獨立參數。