CODEWITHSUNDEEP
javacomparisonhashmaptime-complexity
rgamber
rgamber

Reputation: 5849

Hashmap comparison running time

I am comparing 2 HashMaps, and I am trying to figure out the time complexity of the comparison loop. The code is as follows:

//map1 is a HashMap and contains m elements and keys
//map2 is a HashMap and contains n elements and keys 
List<myObject> myList = new ArrayList<myObject>()  
for (String key: map1.keySet()){ 
    if(!map2.containsKey(key)){
        myList.add(map.get(key));
   }
 }

The first for loop will be O(m). I found on some other forum that the containsKey() takes lg(n) time. Can someone please confirm that? I couldn't find it in the JavaDocs.
If so , then the the total time complexity would be O(mlg{n}).
Also any ideas on how to do this comparison in a better way would be helpful.

Upvotes: 1

Views: 5673

Answers (3)

mergeconflict
mergeconflict

Reputation: 8276

You're right about the time complexity of the outer loop: O(n). The asymptotic complexity of HashMap.containsKey() is O(1) unless you've done something ridiculous in your implementation of myObject.hashCode(). So your method should run in O(n) time. An optimization would be to ensure you're looping over the smaller of the two maps.

Note that TreeMap.containsKey() has O(log n) complexity, not HashMap... Stop looking at those forums :)

Upvotes: 1

DarthVader
DarthVader

Reputation: 55092

Depends on your hashcode algorithm and collisions.

Using a perfect hashcode, theoretically map look up is O(1), constant time, if there are collisions, it might be upto O(n). So in your case, if you have good hash algorithms, it would be O(m).

if you look at wiki, you can get more understanding about the concept. You can also look at Map source code.

Upvotes: 5

dgrant
dgrant

Reputation: 1427

The Java HashMap implementation should constantly be resizing the internal data structure to be larger than the number of elements in the map by a certain amount and the hashing algorithm is good so I would assume collisions are minimal and that you will get much closer to O(1) than O(n).

What HashMap are you using? The one that comes with Java? Your own?

Upvotes: 1

Related Questions