2

I need to return a subset of HashMap from a function. So what is a better approach or the most efficient one:

a. Iterate over the HashMap keys and whichever falls under my conditions, add them to a locally created HashMap and return it

or

b. Clone the HashMap and use retainAll method.

i.e.:

private HashMap<Long, List<Files>> abc(HashMap<Long, List<Files> mainMap, Set<Long> setNeeded){
    HashMap<Long, List<Files>> retVal = new HashMap<Long, List<Files>>(mainMap);
    for(Long timeStamp : mainMap.keySet()){
      if(setNeeded.contains(timeStamp){
        retVal.put(timeStamp, mainMap.get(key));
      }
    }
  return retVal;
}

or

private HashMap<Long, List<Files>> abc(HashMap<Long, List<Files> mainMap, Set<Long> setNeeded){
    HashMap<Long, List<Files>> retVal = new HashMap<Long, List<Files>>(mainMap);
    retVal.retainAll(setNeeded);
    return retVal;
}

or are both optimized and efficient ?

MWiesner
  • 8,868
  • 11
  • 36
  • 70
Dhanesh Khurana
  • 159
  • 1
  • 13
  • 2
    When you know you want to iterate over a HashMap, LinkedHashMap allows you to iterate over the values efficiently – Simon Jul 20 '15 at 07:24

2 Answers2

4

a. will do a single pass on the original map, and copy only the entries you want to the new map

b. will do a first pass on the original map and copy all the entries to the new map, then will do a second pass on the new map and remove all the unneeded entries

Of course, a is faster that b.

It would be even faster if, instead of iterating on the keySet and getting the corresponding value from the map, you iterated on the entrySet, and got the corresponding value from the entry directly.

Also not that the code has a bug: it copies the original map instead of starting from an empty map.

JB Nizet
  • 678,734
  • 91
  • 1,224
  • 1,255
1

It should be the same complexity/optimization in the worst case. retainAll method of Map class also iterates element in the map, then call contain method (can reference OpenJDK source or this post )

But if solution a. is initialized to an empty map. I thought that it should be better than solution b. due to more operations in solution b.

Community
  • 1
  • 1
A-Shi
  • 31
  • 3