単独リンクリストをマップに変換する

Question

既存のものをアップグレードするための変更を割り当てられました。

問題の大きさは、入力ラインの数によって支配されていることを を前提に、各端末回線用のマップを使用して資格試験の問題を再符号化する方法図アウトではなく、500本の 端末回線

プログラムは番号、名前を持つテキストファイルを取り込みます。番号はPC番号で、名前はログオンしたユーザーです。プログラムは、最も多くログオンした各PCのユーザーを返します。ここに既存のコードがあります

public class LineUsageData { 
    SinglyLinkedList<Usage> singly = new SinglyLinkedList<Usage>(); 


    //function to add a user to the linked list or to increment count by 1 
    public void addObservation(Usage usage){ 
     for(int i = 0; i < singly.size(); ++i){ 
      if(usage.getName().equals(singly.get(i).getName())){ 
       singly.get(i).incrementCount(1); 
       return; 
      } 
     } 

     singly.add(usage); 
    } 
    //returns the user with the most connections to the PC 
    public String getMaxUsage(){ 
     int tempHigh = 0; 
     int high = 0; 
     String userAndCount = ""; 
     for(int i = 0; i < singly.size(); ++i){//goes through list and keeps highest 
      tempHigh = singly.get(i).getCount(); 
      if(tempHigh > high){ 
       high = tempHigh; 
       userAndCount = singly.get(i).getName() + " " + singly.get(i).getCount(); 
      } 
     } 

     return userAndCount; 
    } 
} 

私は理論的な面で問題があります。ハッシュマップまたはツリーマップを使用できます。私はどのように私は各PCのユーザーのリストを保持するマップを形成するだろうと思うしようとしている？私は、ユーザの名前とカウントを保持するUsageオブジェクトを再利用することができます。

Answer 1

私はこれをオフラインで解決し、両方とも非常に役立つと思われる回答を見る機会を得られませんでした。そのNickとAiveanについては申し訳ありません。ここにコードを書いて、これを動作させるようにしました。

public class LineUsageData { 

    Map<Integer, Usage> map = new HashMap<Integer, Usage>(); 
    int hash = 0; 
    public void addObservation(Usage usage){ 
     hash = usage.getName().hashCode(); 
     System.out.println(hash); 
     while((map.get(hash)) != null){ 
      if(map.get(hash).getName().equals(usage.name)){ 
       map.get(hash).count++; 
       return; 
      }else{ 
       hash++; 
      } 

     } 
     map.put(hash, usage); 
    } 






    public String getMaxUsage(){ 
     String str = ""; 
     int tempHigh = 0; 
     int high = 0; 

    //for loop 
     for(Integer key : map.keySet()){ 
      tempHigh = map.get(key).getCount(); 
      if(tempHigh > high){ 
       high = tempHigh; 
       str = map.get(key).getName() + " " + map.get(key).getCount(); 
      } 
     } 

     return str; 
    } 


} 

Answer 2

Usageがリストに存在するかどうかをチェックすると、毎回リニア検索が実行されます（O(N)）。リストをMap<String,Usage>に置き換えると、サブラインの時間でnameを検索することができます。 TreeMapはO(log N)の検索と更新の時間を有し、HashMapは償却されたO(1)（一定）時間です。

したがって、この場合の最も有効なデータ構造はHashMapです。あなたはそれで最大の要素を見つけるために、同じ手順を使用できるように

import java.util.*; 

public class LineUsageData { 
    Map<String, Usage> map = new HashMap<String, Usage>(); 

    //function to add a user to the map or to increment count by 1 
    public void addObservation(Usage usage) { 
     Usage existentUsage = map.get(usage.getName()); 
     if (existentUsage == null) { 
      map.put(usage.getName(), usage); 
     } else { 
      existentUsage.incrementCount(1); 
     } 
    } 

    //returns the user with the most connections to the PC 
    public String getMaxUsage() { 
     Usage maxUsage = null; 
     for (Usage usage : map.values()) { 
      if (maxUsage == null || usage.getCount() > maxUsage.getCount()) { 
       maxUsage = usage; 
      } 
     } 

     return maxUsage == null ? null : maxUsage.getName() + " " + maxUsage.getCount(); 
    } 

    // alternative version that uses Collections.max 
    public String getMaxUsageAlt() { 
     Usage maxUsage = map.isEmpty() ? null : 
       Collections.max(map.values(), new Comparator<Usage>() { 
        @Override 
        public int compare(Usage o1, Usage o2) { 
         return o1.getCount() - o2.getCount(); 
        } 
       }); 

     return maxUsage == null ? null : maxUsage.getName() + " " + maxUsage.getCount(); 
    } 

} 

Mapも、それの大きさに比例する時間で繰り返すことができます。私はあなたに手動アプローチか、Collections.maxユーティリティメソッドの2つのオプションを与えました。簡単な言葉で

Answer 3

：あなたが使用しLinkedList（単独で、または二重に）あなたは、項目のリストを持って、あなたは通常、 それらを横断する計画としたときに、「辞書のような」エントリを持っているMap実装キーは値に対応し、キーを使用して値にアクセスする予定です。

SinglyLinkedListをHashMapまたはTreeMapに変換するには、アイテムのどのプロパティがキーとして使用されるかを調べる必要があります（固有の値を持つ要素でなければなりません）。

あなたの使用法クラスからnameプロパティを使用していると仮定すると、あなたはこの （簡単な例）を行うことができます。

//You could also use TreeMap, depending on your needs. 
Map<String, Usage> usageMap = new HashMap<String, Usage>(); 

//Iterate through your SinglyLinkedList. 
for(Usage usage : singly) { 
    //Add all items to the Map 
    usageMap.put(usage.getName(), usage); 
} 

//Access a value using its name as the key of the Map. 
Usage accessedUsage = usageMap.get("AUsageName"); 

はまた、次の点に注意してください

Map<string, Usage> usageMap = new HashMap<>(); 

が原因に有効であり、 diamond inference。