Changing a key value pair in a HashMap
I have a data structure like this:
Map<String,ArrayList<String>> graph = new HashMap<String,ArrayList<String>>();
It is essentially a hash map that puts string values as keys and stores a list of arrays of strings in value for the keys. Now I am trying to change the key value template to make the value a key and enter the value. The way I do it is as follows:
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;
}
So this works for me when changing the hashmap key value pattern for small datasets, however, when I try to use this larger dataset, I run
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)
I know this is a very naive and wrong approach to do this, what is the best and correct way to do this?
source to share
There is an error in your code:
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);
}
}
The local variable values
must be in a nested loop for
, otherwise it values
accumulates for the whole new new key v
and will cost a lot of memory, if your dataset is large it should be:
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;
}
But you don't really need to create a new List instance for every internal step for
, try the following code with 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;
}
If you are using an older version of jdk you can try:
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;
}
Hope this can be helpful :-)
source to share