값이 해시 된 이진 검색 맵

다음 코드는 문자열 입력 빈도 (addPV 메서드)를 추적하고 가장 높은 개수의 k 문자열을 순서대로 (firstK 메서드) 출력 할 수있는 간단한 버전의 클래스를 제공합니다.값이 해시 된 이진 검색 맵

아래의 간단한 코드에서 이진수 트리 (트리 집합)를 사용하여 개수를 추적하고 순서를 유지합니다. 보조 데이터 구조 (해시 맵)는 트리 집합의 요소에 빠르게 액세스하는 데 사용됩니다. 캐릭터 라인 명과 카운트를 포함한 복합 엔트리 클래스가 사용됩니다. 카운트에 의해 자연 순서가 결정되어 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; 
    } 
}

출처

2016-08-08 Hargen.Hans