Konvertieren von einfach verknüpften Liste zu einer Karte

Question

Ich habe eine Aufgabe zu ändern, um ein vorhandenes zu aktualisieren.

herauszufinden, wie die Eignungsprüfung Problem neu zu kodieren eine Karte für jedes Endgerät Zeile, auf der Annahme, dass die Größe des Problems durch die Anzahl der Eingangsleitungen dominiert wird, nicht die 500 Anschlussleitungen

Das Programm nimmt eine Textdatei mit der Nummer und dem Namen auf. Die Nummer ist die PC-Nummer und der Name ist der Benutzer, der sich anmeldete. Das Programm gibt den Benutzer für jeden Computer zurück, der sich am häufigsten angemeldet hat. Hier ist der bestehende Code

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; 
    } 
} 

Ich habe Probleme auf der theoretischen Seite. Wir können eine Hashmap oder eine Treemap verwenden. Ich versuche darüber nachzudenken, wie ich eine Karte erstellen würde, die die Liste der Benutzer für jeden PC enthält? Ich kann das Usage-Objekt wiederverwenden, das den Namen und die Anzahl der Benutzer enthält. Ich soll dieses Objekt aber nicht ändern

Answer 1

Ich löste das offline und hatte keine Chance, einige der Antworten zu sehen, die beide sehr hilfreich zu sein schienen. Entschuldige bitte Nick und Aivean und danke für die Antworten. Hier ist der Code, den ich geschrieben habe, um das zum Laufen zu bringen.

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

Wenn Sie überprüfen, ob Usage in der Liste vorhanden ist, führen Sie jedesmal eine lineare Suche durch (O(N)). Wenn Sie Ihre Liste durch die Map<String,Usage> ersetzen, können Sie in sublinearer Zeit nach name suchen. TreeMap hat O(log N) Zeit für die Suche und Aktualisierung, HashMap hat amortisiert O(1) (konstante) Zeit. Die beste Datenstruktur in diesem Fall ist 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 kann auch in der Zeit, die proportional zu seiner Größe wiederholt werden, so dass Sie die gleiche Prozedur in ihm maximales Element finden verwenden können. Ich habe Ihnen zwei Möglichkeiten gegeben, entweder einen manuellen Ansatz oder die Verwendung der Collections.max Hilfsmethode.

Answer 3

Mit einfachen Worten: Sie ein verwenden LinkedList (einfach oder doppelt), wenn Sie eine Liste der Elemente, und Sie in der Regel planen, sie zu durchqueren, und eine Map Implementierung, wenn Sie „Wörterbuch-like“ Einträge haben, in denen ein Schlüssel entspricht einem Wert und Sie möchten mit dem Schlüssel auf den Wert zugreifen.

Um eine Ihrer SinglyLinkedList zu HashMap zu konvertieren oder TreeMap, werden Sie die Eigenschaft Ihrer Artikel finden müssen, wie Sie Ihren Schlüssel verwendet werden (es muss ein Element mit eindeutigen Werten sein).

Angenommen, Sie den Namen Eigenschaft von Ihrer Nutzungsklasse verwenden, können Sie dieses (ein einfaches Beispiel) tun:

//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"); 

dass Beachten Sie auch:

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

gültig sind, aufgrund diamond inference.