Time complexity

Average Time Complexity of HashMap = O(1)

• Average Case:
  • Insertion (average): O(1)
  • Lookup (average): O(1)
  • Deletion (average): O(1)
• Worst Case:
  • Insertion (worst): O(n), where n is the size of the hash map. This occurs when there are many hash collisions, leading to linear probing or other collision resolution strategies that may involve traversing the entire hash map.
  • Lookup and Deletion (worst): O(n), for the same reason as insertion.

Refercences

• What is a Hash Map? Time Complexity and Two Sum Example
• Time Complexity of HashMap get is O(1). Why?
• Reference from my own artical on medium: Time complexity