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



-

	package com.tvidushi.hashmap;
	public class MyHashMap {
	/* The initial size of the bucket array */
	private int BUCKET_ARRAY_SIZE = 256;
	private Node bucketArray[] = new Node[BUCKET_ARRAY_SIZE];
	public MyHashMap(){
	}
	public MyHashMap(int initialSize){
	this.BUCKET_ARRAY_SIZE = initialSize;
	}
	//put operation
	public void put1(String key,String value){
	//calculate hashcode
	int hashcode = Math.abs(key.hashCode()%BUCKET_ARRAY_SIZE);
	//create node entry
	Node node = new Node(key,value);
	//if duplicate
	if(bucketArray[hashcode] == null){
	// no collison senario
	bucketArray[hashcode] = node;
	}else{
	// collison detected
	Node currentNode = bucketArray[hashcode];
	while(currentNode.next !=null){
	//validate if key exist
	if(currentNode.getKey() ==key)
	currentNode.setValue(value);
	currentNode = currentNode.next;
	}
	currentNode.next = node;
	}
	}
	public void put(String key,String value){
	//1.create hashcode
	//2.create new node
	//3.verify if hash position is empty ,inser
	//4.collison occured iterate & add
	int hashcode = Math.abs(key.hashCode())%BUCKET_ARRAY_SIZE;
	Node node = new Node(key,value);
	if(bucketArray[hashcode] == null){
	bucketArray[hashcode] = node;
	}else{
	Node currentNode = bucketArray[hashcode];
	while(currentNode.next != null){
	currentNode = currentNode.next;
	if(currentNode.key == key){
	currentNode.setValue(value);
	}
	currentNode = currentNode.next;
	}
	currentNode = node;
	}
	}
	public String get(String key){
	int hashcode = Math.abs(key.hashCode())%BUCKET_ARRAY_SIZE;
	Node currentnode = bucketArray[hashcode];
	if(currentnode.next == null){
	if(currentnode.getKey()==key)return currentnode.getValue();
	}else{
	while (currentnode.next != null){
	if(currentnode.getKey() == key)
	return currentnode.getValue();
	currentnode = currentnode.next;
	}
	}
	return null;
	}
	//remove operation
	public void remove(String key){
	}
	class Node {
	String key;
	String value;
	Node next;
	Node(String key,String value){
	this.key = key;
	this.value = value;
	}
	Node(){}
	public String getKey() {
	return key;
	}
	public void setKey(String key) {
	this.key = key;
	}
	public String getValue() {
	return value;
	}
	public void setValue(String value) {
	this.value = value;
	}
	public Node getNext() {
	return next;
	}
	public void setNext(Node next) {
	this.next = next;
	}
	}
	}

view raw MyHashMap.java hosted with ❤ by GitHub

-
The test case :
-

	**
	*
	*/
	package com.tvidushi.hashmap;
	import org.junit.After;
	import org.junit.Before;
	import org.junit.Test;
	/**
	* @author takshila.vidushi
	*
	*/
	public class MyHashMapTest {
	private MyHashMap myMap;
	private final int NUM_ELEMENTS = 200000;
	/**
	* @throws java.lang.Exception
	*/
	@Before
	public void setUp() throws Exception {
	myMap = new MyHashMap();
	}
	/**
	* @throws java.lang.Exception
	*/
	@After
	public void tearDown() throws Exception {
	}
	/**
	* Test method for {@link com.vidushi.takshila.examples.VidushiHashMap#put(java.lang.String, java.lang.String)}.
	*/
	@Test
	public void testPut() {
	myMap.put("vidushi", "vidushi01");
	}
	/**
	* Test method for {@link com.vidushi.takshila.examples.VidushiHashMap#get(java.lang.String)}.
	*/
	@Test
	public void testGet() {
	String k = "vidushi";
	String v = "vidushi01";
	myMap.put("vidushi", "vidushi01");
	System.out.println(myMap.get("vidushi"));
	}
	}

view raw MyHashMapTest.java hosted with ❤ by GitHub

-

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