將單個鏈接列表轉換爲地圖

圖如何重新編碼使用地圖對於每個終端線的資格考試問題，在假設問題的大小由輸入線的數量占主導地位，而不是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; 
    } 
}

我在理論上遇到了麻煩。我們可以使用散列表或樹形圖。我正在考慮如何構建一張可以保存每臺電腦用戶列表的地圖？我可以重用Usage對象，該對象將保存用戶的名稱和計數。我不應該修改該對象

來源

2015-09-26 Peter3

我解決了這個離線，並沒有看到一些看起來是非常有幫助的答案。對不起，尼克和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; 
    } 


}

來源

2015-09-27 14:53:20 Peter3

當檢查列表中是否存在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實用方法。

來源

2015-09-26 22:48:56 Aivean

用簡單的話：你用一個LinkedList（單或雙），當你有一個項目列表，你通常打算穿越它們，和Map實現，當你有「字典式」的條目，其中鍵對應於一個值，並且您計劃使用該鍵訪問該值。

爲了轉換您SinglyLinkedList到HashMap或TreeMap，你需要找出你的項目的財產將被用來作爲你的密鑰（它必須是具有唯一值的元素）。

假設你正在使用的名稱屬性從您的使用類，你可以做到這一點（一個簡單的例子）：

//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。

來源

2015-09-26 23:10:44

將單個鏈接列表轉換爲地圖

回答

相關問題