Двоичный поиск Карта, которая имеет значения хешей

Question

В следующем коде представлена ​​простая версия класса, которая отслеживает, как часто вводилась строка (метод addPV), и может выводить строки k с наивысшим счетчиком по порядку (метод firstK).

В упрощенном коде ниже Дерево двоичного дерева (treeet) используется для отслеживания отсчетов и сохранения порядка. Для быстрого доступа к элементам в treeet используется вторичная структура данных (hashmap). Используется класс композитных записей, содержащий имя и количество строк, где count определяет естественный порядок и имя hashCode.

Наиболее элегантным способом было бы использовать BST (например, treemap), чья запись имела бы счет как ключ и имя строки в качестве значения. Внутренний хэш-файл можно использовать для эффективного доступа к элементам в BST в постоянное время. Существует ли стандартная структура данных в общих библиотеках для общих объектов?

import java.util.*; 

public class MostVisitedPages { 
    private HashMap<String,CountEntry> hm = new HashMap<>(); 
    private TreeSet<CountEntry> ts = new TreeSet<>(); 

    private static class CountEntry implements Comparable<CountEntry>{ 
     String page; 
     int count; 

     CountEntry (String page, int count){ 
      this.page = page; 
      this.count = count; 
     } 

     @Override 
     public int compareTo(CountEntry entry){ 
      int res = Integer.compare(count,entry.count); 
      return res != 0 ? res: page.compareTo(entry.page); 
     } 

     @Override 
     public boolean equals(Object obj){ 
      if(this == obj) return true; 
      else if (obj==null || !(obj instanceof CountEntry)) return false; 
      else {return page.equals(((CountEntry)obj).page);} 
     } 

     @Override 
     public int hashCode(){ 
      return page.hashCode(); 
     } 
    } 

    public void addPV(String p){ 
     if(hm.containsKey(p)){ 
      CountEntry ce = hm.get(p); 
      ts.remove(ce); 
      ce.count += 1; 
      ts.add(ce); 
     } else { 
      CountEntry ce = new CountEntry(p,1); 
      ts.add(ce); 
      hm.put(p, ce); 
     } 
    } 

    public List<String> firstK(int k){ 
     List<String> ret = new ArrayList<>(k); 

     Iterator<CountEntry> it = ts.descendingIterator(); 
     for(int i = 0; i<k && i<hm.size(); i++){ 
      ret.add(it.next().page); 
     } 

     return ret; 
    } 
} 

Answer 1

Да, есть TreeMap класс in JDK.

Он должен соответствовать вашим потребностям.