java - 反转 HashMap 中的键值对

Question

我的数据结构如下:

Map<String,ArrayList<String>> graph = new HashMap<String,ArrayList<String>>();

这本质上是一个 HashMap ，它将字符串值作为键并将字符串数组列表存储在键的值中。现在我正在尝试反转键值模式，使值成为键，键成为值。我这样做的方式如下:

private Map<String,ArrayList<String>> reverseAdjList(Map<String,ArrayList<String>> adjList){
    Map<String,ArrayList<String>> tGraph = new HashMap<String,ArrayList<String>>();
    for (Map.Entry<String, ArrayList<String>> entry : adjList.entrySet()) {
        String key = entry.getKey();
        ArrayList<String> values = new ArrayList<>();
        values.add(key);
        ArrayList<String> value = entry.getValue();    
        for(String v:value){
            if(tGraph.containsKey(v)){
                values.addAll(tGraph.get(v));
            }
            tGraph.put(v, values);
        }
    }
    return tGraph;
}

所以这对我来说适用于反转小数据集的 HashMap 键值模式但是当我在更大的数据集上尝试它时我遇到了

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Arrays.java:3210)
at java.util.Arrays.copyOf(Arrays.java:3181)
at java.util.ArrayList.grow(ArrayList.java:261)
at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:235)
at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:227)
at java.util.ArrayList.addAll(ArrayList.java:579)
at GraphProcessor.reverseAdjList(GraphProcessor.java:67)
at GraphProcessor.SCC(GraphProcessor.java:135)
at GraphProcessor.<init>(GraphProcessor.java:50)
at GraphProcessor.main(GraphProcessor.java:250)

我知道这是一种非常幼稚和错误的方法，什么是更好和正确的方法呢？

Answer 1

您的代码中存在错误:

for (Map.Entry<String, ArrayList<String>> entry : adjList.entrySet()) {
    String key = entry.getKey();
    ArrayList<String> values = new ArrayList<>(); // Wrong place for this variable.
    values.add(key);
    ArrayList<String> value = entry.getValue();    
    for(String v:value){
        if(tGraph.containsKey(v)){
            values.addAll(tGraph.get(v));
        }
        tGraph.put(v, values);
    }
}

局部变量 values 应该在嵌套的 for 循环中，否则 values 会为以后所有的新键 v 如果你的数据集很大，会消耗大量内存，应该是:

private Map<String, ArrayList<String>> reverseAdjList(Map<String, List<String>> adjList) {
    Map<String, ArrayList<String>> tGraph = new HashMap<>();
    for (Map.Entry<String, List<String>> entry : adjList.entrySet())  {
        String key = entry.getKey();
        List<String> value = entry.getValue();
        for (String v : value) {
            ArrayList<String> values = new ArrayList<>();
            values.add(key);
            if (tGraph.containsKey(v)) {
                values.addAll(tGraph.get(v));
            }
            tGraph.put(v, values);
        }
    }
    return tGraph;
}

但实际上您不需要为每个内部 for 步骤创建一个新的 List 实例，请使用 JDK 1.8 尝试以下代码:

private  Map<String, List<String>> reverseMap(Map<String, List<String>> adjList) {
    Map<String, List<String>> tGraph = new HashMap<>();
    for (Map.Entry<String, List<String>> entry : adjList.entrySet()) {
        for (String value : entry.getValue()) {
            tGraph.computeIfAbsent(value, v -> new ArrayList<>()).add(entry.getKey()); // Updated according comment from @shmosel
        }
    }
    return tGraph;
}

如果你使用的是旧版本的jdk，你可以试试:

    private Map<String, List<String>> reverseMap(Map<String, List<String>> adjList) {
    Map<String, List<String>> tGraph = new HashMap<>();
    for (Map.Entry<String, List<String>> entry : adjList.entrySet()) {
        for (String value : entry.getValue()) {
            List<String> newValues = tGraph.get(value);
            if (newValues == null) {
                newValues = new ArrayList<>();
                tGraph.put(value, newValues);
            }
            newValues.add(entry.getKey());
        }
    }
    return tGraph;
}

希望这会有所帮助:-)