CODEWITHSUNDEEP
javahashmapruntimetime-complexity
user68498
user68498

Reputation: 35

How to determine the worst case complexity of methods in HashMap?

public void addOccurence(String word) { 
    if (hm.containsKey(word)){
          hm.put(word, hm.get(word)+1);
    }
    else {hm.put(word, 1); }
}

I know that in average put(k,v) and get(v) take o(1) and their worst cases are o(n). What about containsKey(v)? And how to determine the running time of things like: 

hm.put(word, hm.get(word)+1)

Is it o(n^2) in worst case and o(1) in average?

Upvotes: 2

Views: 2786

Answers (4)

Trying
Trying

Reputation: 14278

Worst case time complexity of hm.put(word, hm.get(word)+1) is O(N).

How: suppose you due to excessive collision you hashMap turned into a linked list. So get() will have to search the whole linked list hence O(N). Similarly hm.put() will need to traverse the linked list to insert the value. So O(N)+O(N) = O(2N) ~ = O(N).

Even though for an insert you will not traverse the whole linked list then also the get() method's time complexity is O(N). So total is O(N). So in both cases, the worst-case time complexity is O(N).

This is different in Java-8 as it converts the link list to a tree if the bucket becomes larger than TREEIFY_THRESHOLD.

But asymptotic lower bound of the same is O(1).

How: Because if your keys are well distributed then the get() will have o(1) time complexity and same for insert also. So resulting in O(1) in asymptotic time complexity.

Upvotes: 1

user3009629
user3009629

Reputation: 1

The worst case runtime is not O(n^2) because the you do NOT have nested loops with O(n) RT for each loop. The runtime would be O(n) because the you are adding the RT from the hm.put(word, hm.get(word)+1) method to the RT from the hm.containsKey(word) method. And O(n) + O(n) = O(2n) ==> O(n)

The best case would of course be if the string was not in the hashmap and the else(...) statement was executed, or O(1).

public void addOccurence(String word) { 
    if (hm.containsKey(word)){ //Worst Case O(n)
        hm.put(word, hm.get(word)+1); //Worst case O(n)
    }
    else {hm.put(word, 1); }  //O(1) Runtime
}

As a side note, the containsKey(k) method is basically a get(k) method that returns a boolean based on whether or not the key is there. On the other hand, the get(k) method would actually return the value of the key, assuming the key exists in the hashmap. The runtimes for both would be the same because they essentially searching through the hashmap in the same way.

Upvotes: 0

Mikhail
Mikhail

Reputation: 4223

O(N) is not the worst case. HashMap is only claimed to have constant work time. In fact its not true. Constant work time is maintained by usual rehashing of a Map when a special threshold exceeds. Have a look at internal HashMap method:

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

If size is greater than threshold complete rehashing happens, its complexity is equal to creating new HashMap. So the worst case is

O(new HashMap(oldMap)) + O(N)

O(N) might happen if you have overridden hashCode() function badly, so that it has pure distribution. With default implementations this cant happen. The only danger is in rehashing.

Upvotes: 1

user207421
user207421

Reputation: 310840

It is at worst O(N). You are doing either two or three operations, each of which is at worst O(N), so you have 3N which is still O(N). You aren't doing anything of a quadratic nature.

Upvotes: 1

Related Questions