Карта TopScore или FilteringMap, отсортированная по ключу

Question

Из-за отсутствия лучшего имени я называю структуру данных, которую я ищу, как «TopScoreMap». Вот это требование. Во-первых, размер карты фиксирован. Например, карте необходимо сохранить только top n записей, которые будут выброшены на эту карту. Top n в терминах его ключей. Так как карта должна быть заказана на ее клавишах, я решил реализовать ее на основе java.util.TreeMap. Следующее - это то, что я реализовал. Это прошло несколько тестовых случаев. Мои вопросы:

1. Есть ли существующие структуры данных, которые предоставляют эту функцию?

2. Если нет, существует ли способ избежать итераций при выполнении put? выглядит как O (n^2), худший случай.

class TopScoreMap { 
    TreeMap<Integer, String> map = new TreeMap<Integer, String>(); 
    int max = 0; 

    public TopScoreMap() { 
    this(5); 
    } 

    public TopScoreMap(int maxCapacity) { 
    this.max = maxCapacity; 
    } 

    public void put(int score, String player) { 
    if (map.size() < max) { 
     map.put(score, player); 
    } 
    else { 
     Iterator<Integer> it = map.keySet().iterator(); 
     while (it.hasNext()) { 
     int currentKey = it.next(); 
     if (currentKey < score) { 
      map.remove(currentKey); 
      map.put(score, player); 
      return; 
     } 
     } 
    } 
    } 

} 

Answer 1

вы можете взглянуть на PriorityQueue, таким образом, вам не нужен итератор ... но вы должны отбросить элементы с конца, если он растет за пределом

или, может быть, вы должны использовать SortedMap:

public class T1 { 
    SortedMap<Integer, String> m=new TreeMap<Integer, String>(); 
    void add(Integer i,String n){ 
     m.put(i,n); 
     if(m.size()>3){ 
      m.tailMap(m.lastKey()).clear(); 
     } 
     System.out.println(m); 
    } 
    public static void main(String[] args) { 
     T1 t = new T1(); 
     t.add(1,"a");t.add(2,"b");t.add(3,"c");t.add(4,"d");t.add(0,"e"); 
    } 
} 

Answer 2

Вместо итератора, вы можете просто посмотреть на lastKey подстилающей TreeMap. Если новая запись больше, примите ее.

Что-то вроде:

int lastKey = map.getLastKey(); 
    if (lastKey < score) { 
    map.remove(lastKey); 
    map.put(score, player);  
    } 

Answer 3

С входами из SO, вот что я сделал (не заботясь о синхронизации сейчас)

class ScoreMap { 
    SortedMap<Integer, String> map = new TreeMap<Integer, String>(Collections.reverseOrder()); 
    int max = 5; 

    public ScoreMap(int maxCapacity) { 
     this.max = maxCapacity; 
    } 

    public void put(int score, String player) { 
     map.put(score, player); 
     if (map.size() > max) { 
     map.remove(map.lastKey()); 
     } 
    } 
    //.... 
}