Time Complexity of Hashmap Methods

Time Complexity of HashMap methods

The source is often helpful: http://kickjava.com/src/java/util/HashMap.java.htm

• remove: O(1)
• size: O(1)
• values: O(n) (on traversal through iterator)

HashMap get/put complexity

It depends on many things. It's usually O(1), with a decent hash which itself is constant time... but you could have a hash which takes a long time to compute, and if there are multiple items in the hash map which return the same hash code, get will have to iterate over them calling equals on each of them to find a match.

In the worst case, a HashMap has an O(n) lookup due to walking through all entries in the same hash bucket (e.g. if they all have the same hash code). Fortunately, that worst case scenario doesn't come up very often in real life, in my experience. So no, O(1) certainly isn't guaranteed - but it's usually what you should assume when considering which algorithms and data structures to use.

In JDK 8, HashMap has been tweaked so that if keys can be compared for ordering, then any densely-populated bucket is implemented as a tree, so that even if there are lots of entries with the same hash code, the complexity is O(log n). That can cause issues if you have a key type where equality and ordering are different, of course.

And yes, if you don't have enough memory for the hash map, you'll be in trouble... but that's going to be true whatever data structure you use.

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

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.

What is the time complexity of HashMap.containsKey() in java?

From the API doc ofHashMap:

This implementation provides constant-time performance for the basic
operations (get and put), assuming the hash function disperses the
elements properly among the buckets.

Since containsKey() is just a get() that throws away the retrieved value, it's O(1) (assuming the hash function works properly, again).

Hashmaps and Time Complexity

My understanding is ES6 Map object can implement a Hashmap in Javascript. Is that correct?

No, it's not correct the way it is phrased. When you say implement you remind me of interfaces and languages like java. In Java, there is the interface map and then there are different implementations like hashmap, treemap, etc.

In the case of javascript, you could use map (or you could even use an array), to implement a hashmap (or hashtable) algorithm.

Do note that in some browsers like v8, map is already built using hashtables so it is already a hashmap. Unfortunately, the ECMAScript 2015 specification (see https://262.ecma-international.org/6.0/#sec-map-objects ) does not specify or dictate the exact implementation. Instead, it is quite open ended allowing each browser or javascript engine to have a compatible implementation.

Map object must be implemented using either hash tables or other
mechanisms that, on average, provide access times that are sublinear
on the number of elements in the collection. The data structures used
in this Map objects specification is only intended to describe the
required observable semantics of Map objects. It is not intended to be
a viable implementation model.

If a hashtable is used, then it is a hashmap (not the same exactly as java), but the underlying implementation depends on the actual browser.

Note/FYI: Maps in google's V8 engine are built on top of hash tables.

indexOf method in arrays has an O(n) time complexity.

Yes. You cannot do better than O(n) in a random unsorted array.

Does has method in Maps have O(1) time complexity?

Usually yes. Considering that the map uses hashtables (or somethling like hashtables).
Additionally, there has to be:

• descent hash function that is constant time and doesn't take long to compute
• not too many collisions because we would then have to iterate through multiple items that had the same hash code.

O(1) isn't always guaranteed, and the worst case scenario of O(N) is quite unlikely.

Have a look @ the theory behind hashmaps and hashtables :

• https://en.wikipedia.org/wiki/Hash_table
• https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm

How JS can find an element in a Map object in one step?

Map uses a hashtable (or a similar mechanism) as specified in the spec.
Therefore, when an object is requested a hash is calculated.
Then the specific location in an internal table is located.
This is the basic theory about hash tables and why they are usualy O(1).
Do note, that if there are many collisions performance can move towards O(N).

See: https://stackoverflow.com/a/9214594/1688441 from Hash table runtime complexity (insert, search and delete)

Hash tables are O(1) average and amortized case complexity, however it suffers from O(n) > worst case time complexity. [And I think this is where your confusion is]

That excellent answer lists the situations of worst cases.

How it works differently than indexOf

Hashtables use a hash and do a lookup inside a table/array.
Instead, indexOf searches step by step within an array/collection/string. See: https://262.ecma-international.org/5.1/#sec-15.4.4.14

If not having an O(1) then Es6 Map is not a real Hashmap

This is not correct. A hashmap can have a worst-case performance of O(N).
There is an excellent wikipedia article about hashmap/hashtable with an excellent table: (from: https://en.wikipedia.org/wiki/Hash_table )

1. https://en.wikipedia.org/wiki/Hash_table
2. Hash table runtime complexity (insert, search and delete)

What is the time complexity of java.util.HashMap class' keySet() method?

Getting the keyset is O(1) and cheap. This is because HashMap.keyset() returns the actual KeySet object associated with the HashMap.

The returned Set is not a copy of the keys, but a wrapper for the actual HashMap's state. Indeed, if you update the set you can actually change the HashMap's state; e.g. calling clear() on the set will clear the HashMap!

---

... iterating through the returned Set will take obviously O(n) time.

Actually that is not always true:

• It is true for a HashMap is created using new HashMap<>(). The worst case is to have all N keys land in the same hash chain. However if the map has grown naturally, there will still be N entries and O(N) slots in the hash array. Thus iterating the entry set will involve O(N) operations.

• It is false if the HashMap is created with new HashMap<>(capacity) and a singularly bad (too large) capacity estimate. Then it will take O(Cap) + O(N) operations to iterate the entry set. If we treat Cap as a variable, that is O(max(Cap, N)), which could be worse than O(N).

There is an escape clause though. Since capacity is an int in the current HashMap API, the upper bound for Cap is 2³¹. So for really large values of Cap and N, the complexity is O(N).

On the other hand, N is limited by the amount of memory available and in practice you need a heap in the order of 2³⁸ bytes (256GBytes) for N to exceed the largest possible Cap value. And for a map that size, you would be better off using a hashtable implementation tuned for huge maps. Or not using an excessively large capacity estimate!

Is the Access Time Complexity of a Map Created by Map.ofEntries() the Same as HashMap which is o(1)?

Mutability or immutability are not directly related to the complexity of the access operation in a Map. For instance, a HashMap will always be O(1) for the get() operation, whereas a TreeMap will be O(log n). It's the implementing class of the Map interface that determines the complexity of the operations.

Besides it's always been possible to create unmodifiable maps, because we can make any Map of any concrete type immutable after we put items on it, like this:

Map<Integer, String> immutableMap = Collections.unmodifiableMap(mutableMap);

To be clear, HashMap.ofEntries() won't work because the ofEntries() method is static and defined in the Map interface, not in any of its implementing classes.

And you should not worry about being unable to declare the type of a map as HashMap or some other concrete class, anyway the best practice is to declare the map as being of a Map interface.

Also, if you were using a version older than Java 9 and don't mind using an external library, you can use ImmutableMap from Guava:

Map<Integer, String> immutableMap = ImmutableMap.of(key1, val1, key2, val2);

Perhaps reading this article will clarify things a bit more.

What is the complexity of HashMap#replace?

tl:dr

HashMap#replace runs in O(1) amortized;

and under the premise that the map is properly balanced, which Java takes care of during your put and remove calls, also non-amortized.

Non-amortized

The fact whether it also holds for non-amortized analysis hinges on the question regarding the implemented self-balancing mechanism.

Basically, due to replace only changing the value which does not influence hashing and the general structure of the HashMap, replacing a value will not trigger any re-hashing or re-organization of the internal structure.

Hence we only pay for the cost of locating the key, which depends on the bucket size.

The bucket size, if the map is properly self-balanced, can be considered a constant. Leading to O(1) for replace also non-amortized.

However, the implementation triggers self-balancing and re-hashing based on heuristic factors only. A deep analysis of that is a bit more complex.

So the reality is probably somewhere in between due to the heuristics.

---

Implementation

To be sure, let us take a look at the current implementation (Java 16):

@Override
public V replace(K key, V value) {
    Node<K,V> e;
    if ((e = getNode(key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

The method afterNodeAccess is a dummy for subclasses and is empty in HashMap.
Everything except getNode runs in O(1) trivially.

getNode

getNode is the canonical implementation of locating an entry in a HashMap, which we know runs in O(1) for a proper self-balancing map, like Javas implementation. Let's take a look at the code:

/**
 * Implements Map.get and related methods.
 *
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

This method basically computes the hash hash = hash(key), then looks up the hash in the table first = tab[(n - 1) & (hash = hash(key))] and starts iterating through the data structure stored in the bucket.

Regarding the data structure for the bucket, we have a little branching going on at if (first instanceof TreeNode).

Bucket

The buckets are either simple implicitly linked lists or red-black-tree.

Linked List

For the linked list, we have a straightforward iteration

do {
     if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
} while ((e = e.next) != null);

which obviously runs in O(m) with m being the size of the linked list.

Red-Black-Tree

For the red-black-tree, we have

return ((TreeNode<K,V>)first).getTreeNode(hash, key);

Lookup in a red-black-tree is O(log m), with m being the size of the tree.

Bucket size

Javas implementation makes sure to re-balance the buckets by rehashing if it detects that it gets out of hands (you pay for that on each modifying method like put or remove).

So in both cases we can consider the size of the buckets as constant or, due to the heuristics involved with self-balancing, close to a constant.

Conclusion

Having the buckets at constant size, effectively, makes getNode run in O(1), leading to replace running in O(1) as well.

Without any self-balancing mechanism, in worst case it would degrade to O(n) if a linked list is used and O(log n) for a red-black-tree (for the case that all keys yield a hash collision).

Feel free to dig deeper into the code but it gets a bit more complex down there.

What is the time complexity of HashMap.containsValue() in java?

To answer the question in the title - as mentioned by others, containsValue is O(n), because without the key it doesn't know where it is and the algorithm has to go over all the values stored in the map.

To answer the question in the body of your question - on how to solve it - just consider whether you really need a general map which can count how many instances have you seen of each number. I mean, the only time you'd care if there's more than one appearance of a number is when it's x/2, right? That smells like a corner case to me. Just add a test that checks for that corner case - something like embedding if (numberList[i] == requiredSum/2) half++ during your set-construction loop, and then if (requiredSum % 2 == 0 && half == 2) return true after it (see other variation below).

Then you can just iterate over the set and for each item check whether requiredSum-item also appears in the set.

To summarize (with early exits when possible):

Set<Integer> seen = new HashSet<Integer>();
boolean halfSeen = false;
for (int num : numberList) {
    if (num == requiredSum/2 && requiredSum % 2 == 0) {
        if (halfSeen) return true;
        halfSeen = true;
    } else {
        seen.add(num);
    }
}
for (int num : seen) {
    if (seen.contains(requiredSum - num)) return true;
}
return false;

---

Related Topics