What is the time complexity of putting and getting an element from suc

1.	What is the time complexity of putting and getting an element from such structure? Which Map implementation provide better performance?
Answer» The time complexity of HASHMAP to getting the elements is usually from O(N) to O(Log(n)), when there is no collision OCCURS and the worst case is O(n) to O(1), because when collision occurs and HashMap needs to travel till the end of the linked list. Now in the case of putting the elements in HashMap, is always O(1). Below classes is the implementation of Map interface. LinkedHashMap, HashMap Hashtable, WeakHashMap, IdentityHashMap, ConcurrentHashMap, TreeMap, and EnumMap. However, as PER the MEMORY performance basis, the WeakHashMap gives better performance. But it doesn’t provide the thread safety if one needs to achieve the thread safety, to achieve the thread safety one needs to use the ConcurrentHashMap because it provides thread safety without using synchronization.

What is the time complexity of putting and getting an element from such structure? Which Map implementation provide better performance?

Answer»

The time complexity of HASHMAP to getting the elements is usually from O(N) to O(Log(n)), when there is no collision OCCURS and the worst case is O(n) to O(1), because when collision occurs and HashMap needs to travel till the end of the linked list. Now in the case of putting the elements in HashMap, is always O(1). Below classes is the implementation of Map interface.

LinkedHashMap,
HashMap
Hashtable,
WeakHashMap,
IdentityHashMap,
ConcurrentHashMap,
TreeMap, and
EnumMap.

However, as PER the MEMORY performance basis, the WeakHashMap gives better performance. But it doesn’t provide the thread safety if one needs to achieve the thread safety, to achieve the thread safety one needs to use the ConcurrentHashMap because it provides thread safety without using synchronization.

Discussion

No Comment Found

Related InterviewSolutions

How is WeakHashMap differs from other HashMap?
How the ConcurrentHashMap works, how it provides the thread safety?
What is CopyOnWriteArrayList? How it is different from ArrayList in Java?
When to use the Queue and Stack? What is the possible use case?
When to use the Iterator and Enumeration? What is the possible use case?
How can you use Comparable and Comparator interfaces to sort collections?
What is the situation in which fail-fast and fail-safe iterators works? What are the issues to use the fail-safe along with the example?
What is the purpose of the initial capacity and load factor parameters of a HashMap? What are their default values? How is the threshold plays the role to decide the size?
What is the time complexity of putting and getting an element from such structure? Which Map implementation provide better performance?
What is collision problem? How HashMap performs collision detection and collision prevention when the index position found for the same key, what are the algorithms performed to avoid this situation?