HashMap,Queue

TYPES OF HASHMAP	NULL KEYS	NULL VALUES	DUPLICATE KEYS	SORTED	SYNCHRONIZED	READALL/WRITE LOCK	INSERTION ORDER	WEAK REFERENCES STORED	[== OPERATOR ]
HASHMAP	YES
HASHTABLE					YES
LINKEDHASHMAP							YES	YES
WEAKHASHMAP
IDENTITYHASHMAP									IdentityHashMap as name suggests uses the equality operator(==) for comparing the keys. So when you put any Key Value pair in it the Key Object is compared using == operator.
TREEMAP				YES
ENUM MAP
COLLECTIONS.SYNCHRONIZEDMAP
CONCURRENT.CONCURRENT HASHMAP						YES
CONCURRENT.CONCURRENTSKIPLISTMAP

MAP IMPLEMENATION : ASSOCIATIVE ARRAY
HASHING	HASHING IS A TECHNIQUE TO CONVERT/TRANSFORM STRING OF CHARACTERS (TEXT) INTO SHORT LENGTH FIXED VALUE THAT REPRESENTS THAT REPRESENTS THE ORGINAL STRING.A SHORT VALUE HELPS IN INDEXING FASTER SEARCHES
HASHCODE()	HOW HASHMAP WORKS INTERNALLY ?
put(K k,V v){                                                                  hash(k) ;                                                                      index = hash &(n-1);                                                                    }		IN  JAVA 8 ,IF LINKEDLIST CROSSES A THRESHOLD OF 8 , THE LINKED LIST IS CHANGED TO BALANCED TREE
get(K k){                                                               hash(k);                                                                           index= hash & (n-1);                                                   }	we first compare index & then hash code , if hashcode doesn’t match we compare the next node
EQUALS AND HASHCODE CONTRACT:EQUALS OBJECTS MUST HAVE EQUAL HASHCODE| IF WE DO NOT DO SO , OUR OBJECT WILL BEHAVE INCORRECTLY WHEN STORED IN HASHBASED COLLECTIONS

Implementing HashMaps



-

-
The test case :
-

-

Sr.No	List Of Methods/Def/Examples/Sample Programs
1.	Put() Def/Examples
2.	Get() Def/Examples
3.	Entryset() Def/Examples
4.	Keyset() Def/Examples
5.	Values() Def/Examples
6.	Other Methods: Size(), Containskey(), ContainsValue(), Remove(), IsEmpty(), Clear().
7.	Clone() Def/Examples
8.	PutAll() Def/Examples

ConcurrentHashMap

• You should use ConcurrentHashMap when you need very high concurrency in your project.
• It is thread safe without synchronizing the whole map.
• Reads can happen very fast while write is done with a lock.
• There is no locking at the object level.
• The locking is at a much finer granularity at a hashmap bucket level.
• ConcurrentHashMap doesn’t throw a ConcurrentModificationException if one thread tries to modify it while another is iterating over it.
• ConcurrentHashMap uses multitude of locks.

SynchronizedHashMap

• Synchronization at Object level.
• Every read/write operation needs to acquire lock.
• Locking the entire collection is a performance overhead.
• This essentially gives access to only one thread to the entire map & blocks all the other threads.
• It may cause contention.
• SynchronizedHashMap returns Iterator, which fails-fast on concurrent modification.
• 
  
• 
  
• HashMap: this implementation uses a hash table as the underlying data structure. It implements all of the Mapoperations and 
• allows null values and one null key. This class is roughly equivalent to 
• 
  
• 
  
• Hashtable - a legacy data structure before Java Collections Framework, but it is not synchronized and permits nulls. HashMap does not guarantee the order of its key-value elements. Therefore, consider to use a HashMap when order does not matter and nulls are acceptable.  
• LinkedHashMap: this implementation uses a hash table and a linked list as the underlying data structures, thus the order of a LinkedHashMap is predictable, with insertion-order as the default order. This implementation also allows nulls like HashMap. So consider using a LinkedHashMap when you want a Map with its key-value pairs are sorted by their insertion order.  
• TreeMap: this implementation uses a red-black tree as the underlying data structure. A TreeMap is sorted according to the natural ordering of its keys, or by a Comparator provided at creation time. This implementation does not allow nulls. So consider using a TreeMap when you want a Map sorts its key-value pairs by the natural order of the keys (e.g. alphabetic order or numeric order), or by a custom order you specify.

Queues

https://www.youtube.com/watch?v=KxzhEQ-zpDc&list=PLDV1Zeh2NRsAWrxWRTHJrsgBrbwqGzt-z

https://www.youtube.com/watch?v=KxzhEQ-zpDc&list=PLDV1Zeh2NRsAWrxWRTHJrsgBrbwqGzt-z

Priority Queues

https://www.youtube.com/watch?v=wptevk0bshY&list=PLDV1Zeh2NRsCLFSHm1nYb9daYf60lCcag

Problems:

Breadth First Traversal of Graphs