Time complexity analysis of HashMap

The search time complexity of HashMap container O(1) is only its ideal state, and this ideal state needs to be guaranteed by the java designer.

Under the premise that the length of the linked list is as short as possible by the designer, due to the use of the array structure, the key search is completed in O(1) time.

HashMap can be divided into two parts, hash, and map. the map just implements the storage of key-value pairs. And its entire O(1) search complexity is largely guaranteed by hash.

The use of hash by HashMap reflects some design philosophies, such as: converting ordinary object objects into int values ​​through the key.hashCode(), so that they can be regarded as array subscripts, and the search performance of array O(1) can be used.

OK, let’s take a look at the time complexity of adding elements in HashMap.

The process of put operation:

The first step: key.hashcode(), time complexity O(1).

Step 2: After finding the bucket, determine whether there is an element in the bucket, if not, insert a new entey node into the array directly. The time complexity is O(1).

Step 3: If there are elements in the bucket and the number of elements is less than 6, the equals method is called to compare whether there is a key with the same name. If it does not exist, a new entry is inserted at the end of the linked list. Time complexity O(1)+O(n)=O(n).

Step 4: If there are elements in the bucket and the number of elements is greater than 6, the equals method is called to compare whether there is a key with the same name. If it does not exist, a new entry is inserted at the end of the linked list. Time complexity O(1)+O(logn)=O(logn). The time complexity of a red-black tree query is logn.

Through the above analysis, we can conclude that the time complexity of new elements in HashMap is not fixed, and the possible values ​​are O(1), O(logn), and O(n).

Second, the hash collision problem

When HashMap puts an element, it will first calculate the hashcode of the key, and will not call the equals method at this time. why? Because the time complexity of the equals method is O(n). However, HashMap has a hash collision problem. In the worst case, all keys are allocated to the same bucket. At this time, the time complexity of map put and get is O(n).

Therefore, a problem that HashMap designers must consider is to reduce hash collisions.

Which method does HashMap use to resolve hash collisions?

A: HashMap uses the chain address method to resolve hash conflicts. To put it bluntly, it is to connect the conflicting keys and put them in the bucket. When the number of elements in the bucket does not exceed 6, it is strung together in the form of a singly linked list, and when the number of elements in the bucket exceeds 6, it is strung together in the form of a red-black tree.

Through the above analysis, we can conclude that the time complexity of HashMap’s hash operation is O(1), and the time complexity of HashMap’s equals operation is O(n).

Leave a Comment

Your email address will not be published.

Scroll to Top