将单向链表转换为地图

Question

我接到一项任务，要更改以升级现有的。

弄清楚如何使用地图为每个终端线重新编码资格考试问题，在假设问题的大小主要取决于输入行的数量，而不是 500 终端线

程序接收一个文本文件，其中包含编号、名称。数字是 PC 号，名称是登录的用户。该程序 returns 每台电脑登录次数最多的用户。这是现有的代码

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 对象，它将保存用户的姓名和计数。不过我不应该改变那个对象

Answer 1

检查列表中是否存在 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 2

用简单的话说：当你有一个项目列表时，你使用一个LinkedList（单或双），你通常计划遍历它们，以及当您有 "Dictionary-like" 个条目时的 Map 实现，其中一个键对应一个值并且您计划使用该键访问该值。

为了将您的 SinglyLinkedList 转换为 HashMap 或 TreeMap，您需要找出项目的属性将用作您的密钥（它必须是具有唯一值的元素）。

假设您使用的是您的用法 class 中的名称属性，您可以这样做（一个简单的例子）：

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

Answer 3

我离线解决了这个问题，但没有机会看到一些看起来很有帮助的答案。对尼克和艾文感到抱歉，感谢您的回复。这是我最终编写的代码以使其正常工作。

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


}

将单向链表转换为地图

Converting singly linked list to a map

java

hashmap

treemap