Преобразование одноуровневого списка на карту

Question

Мне присвоено задание изменить для обновления существующего.

Фигура, как перекодировать проблему квалификационного экзамена с помощью карты для каждого терминал линии, на предположении, что размер проблемы доминируют числа входных линий, а не 500 терминальных линий

Программа принимает текстовый файл с номером, именем. Номер - номер ПК, и имя - это пользователь, который вошел в систему. Программа возвращает пользователя для каждого компьютера, который входил в систему больше всего. Вот существующий код

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

У меня возникают проблемы с теоретической стороны. Мы можем использовать hashmap или treemap. Я пытаюсь понять, как создать карту, которая будет содержать список пользователей для каждого компьютера? Я могу повторно использовать объект Usage, который будет содержать имя и счетчик пользователя. Я не должен изменять этот объект, хотя

Answer 1

Я решил это в автономном режиме и не получил возможность увидеть некоторые из ответов, которые выглядели как очень полезными. Извините, что Ник и 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.

Answer 3

С простыми словами: Вы использовать LinkedList (однократно или двукратно), когда у вас есть список пунктов, и вы обычно планируете пройти их, и Map реализации, когда у вас есть «Словарь-как» запись, где ключ соответствует значению, и вы планируете получить доступ к значению с помощью ключа.

Для того, чтобы превратить ваш SinglyLinkedList в HashMap или TreeMap, вам нужно узнать, какое свойство вашего пункта будет использоваться в качестве ключа (он должен быть элемент с уникальными значениями).

Предполагая, что вы используете свойство имя из вашего класса Usage, вы можете сделать это (простой пример):

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