値をハッシュするバイナリ検索マップ

Question

次のコードは、文字列が入力された頻度（addPVメソッド）を追跡し、最も高いカウントを持つk文字列をfirstKメソッドで出力できる単純なバージョンのクラスを提供します。

以下の簡略化されたコードでは、バイナリSeach Tree（ツリーセット）を使用してカウントを追跡し、順序を維持します。セカンダリデータ構造（ハッシュマップ）は、ツリーセット内の要素に迅速にアクセスするために使用されます。文字列の名前とカウントを含む複合エントリクラスが使用されます。この場合、カウントによって自然順序が決定され、名前は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があります。

あなたのニーズに合っているはずです。