Java Algorithms Trees

• A tree will have a root node on its top and it has child and child have child. 
• Node with out child are called leaf.
• A Binary Tree contains nodes with two children always.Each node has left node and right node. 
• Binary search tree is a binary tree having specific ordering. Here always left node contains lesser and right node contains higher values. This ordering will make finding a node very fast. 
  
• Insertion: There are two types of insertion are there Balanced and Unbalanced 
  
• Balanced Insertion
• Inserts on next free child based on left right order and time complexity will be lesser here.
• Unbalanced Insertion
•  insert go deep of list and time complexity is higher. 
•  Traversing 
  
• In-order Traverse
  
•  Visit left node first then root node and then right node
•  Pre-order
• Visit root node first then left node and right node.
• Post-Order 
• Visit left node first then right node and last root node. 
•  Code approach 
• For Insert 
• Compare value with root value.
•  If value lesser or equal to root value then go to left child node. Put value in child node if child node is null.
• If child node not null then pass the value to insert method of child. 
• If value is greater than root node value then do the same with right node. 
• For Contains 
• Check node value equals to value. 
• If equals then return true. 
• Else if value lesser than root value then go to left. If left node is null return false else call contains method of left node.
• Else if value greater than root node value then go to right node and do the same there.

public class Node { int data; Node left; Node right; public Node(int data) { this.data = data; } public void insert(int value) { if (value <= data) { // inserting if left node is free if (left == null) { left = new Node(value); } else { // forward to next node if left node aleady occupied. left.insert(value); } } else { if (right == null) { right = new Node(value); } else { right.insert(value); } } } public boolean contains(int value) { if (data == value) { return true; } else if (value < data) { if (left == null) { return false; } else { left.contains(value); } } else { if (right == null) { return false; } else { right.contains(value); } } return false; } public void inOrderPrinting() { if (left != null) { left.inOrderPrinting(); } System.out.println(data); if (right != null) { right.inOrderPrinting(); } } }

Reference Link https://www.youtube.com/watch?v=oSWTXtMglKE

Continue Reading

Java Algorithms Bubble Sort

• Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. 
•  Getting each element one by one and comparing it with adjacent elements and swapping the positions.

public void bubbleSort() { int temp, firstValue, secondValue; int[] arr = { 1, 90, 25, 22, 4, 50 }; printArray(arr); for (int i = 0; i < arr.length; i++) { // #arr.length - 2 -- avoids next index of last index -- secondValue for (int j = 0; j < arr.length - 2; j++) { firstValue = arr[j]; secondValue = arr[j + 1]; if ((firstValue > secondValue)) { temp = firstValue; arr[j] = secondValue; arr[j + 1] = temp; } } } System.out.println("-----SORTING DONE-----"); printArray(arr); }

 
Reference Link https://www.youtube.com/watch?v=T8ErAYobcbc matrix

Continue Reading

Java Algorithms Linear Search

A linear search traverse down a list, one item at a time, without jumping.

public String linearSearchForValue(int value) { String indexesWithValue = ""; for (int i = 0; i < size; i++) { if (theArray[i] == value) { indexesWithValue += i + " ,"; } } return indexesWithValue; }

Continue Reading

Travesrse Matrix Diagonally in Java

A matrix will be in M x N format.So what we need to do is, get value of indexes from 0,0 to M,N. Itreate the two dimensional array in diagonally as follow

50 36 22 31 88 87 27 73 95

After diagonal traverse the output will be.

50 31 36 27 88 22 73 87 95

Consider the above output

50 31 36 27 88 22

• These elements start from left to right top
• Need to iterate for 0 to M-1 using for loop and display corresponding elements diagonally using a while loop.
• To find next element use for formula: M-1,N+1 in while loop

73 87 95

• These elements start from bottom to right top
• Need to Iterate form 1 to N-1 in for loop and display corresponding elements diagonally using a while loop.
• So to find next element use for formula, M-1,N+1 in while loop

      TraveseMatrixDiagonally.java  

public class TraveseMatrixDiagonally { private static final int M = 4; private static final int N = 4; public static void main(String[] args) { TraveseMatrixDiagonally app = new TraveseMatrixDiagonally(); int[][] matrix = app.createMatrix(); app.printMatrix(matrix); app.traverseDiagonally(matrix); } private void traverseDiagonally(int[][] matrix) { for (int i = 0; i <= M - 1; i++) { int X = i; // temp M int Y = 0; // temp N while (X >= 0 && Y <= N - 1) { System.out.print(matrix[X][Y] + " "); X = X - 1; Y = Y + 1; } System.out.println(" "); } for (int i = 1; i <= N - 1; i++) { int X = M - 1; int Y = i; while (X >= 0 && Y <= N - 1) { System.out.print(matrix[X][Y] + " "); X = X - 1; Y = Y + 1; } System.out.println(" "); } } private int[][] createMatrix() { int matrix[][] = new int[M][N]; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { matrix[i][j] = (int) ((Math.random() * (99 + 1 - 10)) + 10); } } return matrix; } private void printMatrix(int[][] matrix) { for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { System.out.print(matrix[i][j]); System.out.print(" "); } System.out.println(" "); } } } /* ****** SAMPLE INPUT ******** 61 44 88 74 44 32 86 56 92 ******* INPUT ******** ****** SAMPLE OUTPUT ******** 61 74 44 86 44 88 56 32 92 ******* OUTPUT ******** */

Reference Link https://www.youtube.com/watch?v=T8ErAYobcbc

Continue Reading

Traverse the matrix as spiral in Java

A matrix will be in M x N format.So what we need to do is, get value of indexes from 0,0 to m,n. Itreate the two dimensional array in spiral mode as follow

• we need to traverse matrix and remove the row/column which already traversed.
• We are not going to delete the elements instead we will limit it by defining boundaries. 
• Boundaries can be t, b, l, r we need to specify the direction variable dir. It decides the direction of traverse as below.
dir=0; ->right, dir=1 -> down, dir=2 -> left, dir=3 ->up

      TraverseMatrixSpiral.java  

package com.sk.iwq.matrix; public class TraverseMatrixSpiral { private static final int M = 3; private static final int N = 3; public static void main(String[] args) { TraverseMatrixSpiral app = new TraverseMatrixSpiral(); int matrix[][] = app.createMatrix(); app.printMatrix(matrix); System.out.println(app.traverseSpriral(matrix).toString()); } private StringBuilder traverseSpriral(int[][] matrix) { StringBuilder sb = new StringBuilder(); int dir = 0; int t = 0; int b = M - 1; int l = 0; int r = N - 1; while (t <= b && l <= r) { if (dir == 0) { for (int i = l; i <= r; i++) { sb.append(matrix[t][i] + ", "); } t++; } if (dir == 1) { for (int i = t; i <= b; i++) { sb.append(matrix[i][r] + ", "); } r--; } if (dir == 2) { for (int i = r; i >= l; i--) { sb.append(matrix[b][i] + ", "); } b--; } if (dir == 3) { for (int i = b; i <= t; i++) { sb.append(matrix[i][l] + ", "); } l++; } dir = (dir + 1) % 4; } return sb; } private int[][] createMatrix() { int matrix[][] = new int[M][N]; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { matrix[i][j] = (int) (Math.random() * 100 + 1); } } return matrix; } private void printMatrix(int[][] matrix) { for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { System.out.print(matrix[i][j]); System.out.print(" "); } System.out.println(" "); } } } /* ****** SAMPLE INPUT ******** 50 36 22 31 88 87 27 73 95 ******* INPUT ******** ****** SAMPLE OUTPUT ******** 50, 36, 22, 87, 95, 73, 27, 31, 88 ******* OUTPUT ******** */

Continue Reading

Traverse the matrix in Java

Traverse the matrix in Java

• A matrix will be in M x N format.
• So what we need to do is, get value of indexes from 0,0 to m,n. 
•  Itreate the two dimensional array as follow

take 0(i) and traverse j till j < N
take 1(i) and traverse j till j < N
           .
           .
till M(i) and traverse j till j < N

      PrimeNumberCheck.java  

public class TraverseMatrix { private static final int M = 3; private static final int N = 3; public static void main(String[] args) { TraverseMatrix app = new TraverseMatrix(); int matrix[][] = app.createMatrix(); app.printMatrix(matrix); app.normalTraverse(matrix); } private void normalTraverse(int[][] matrix) { for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { System.out.print(matrix[i][j]); System.out.print(", "); } } } private int[][] createMatrix() { int matrix[][] = new int[M][N]; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { matrix[i][j] = (int) (Math.random() * 100 + 1); } } return matrix; } private void printMatrix(int[][] matrix) { for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { System.out.print(matrix[i][j]); System.out.print(" "); } System.out.println(" "); } } }

Continue Reading

Check number is prime or not

To check the given number is prime or not.
Prime Numbers:

• A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.
•  It means the remainder of divison of N with numbers from 2 to N/2 should be grater than zero.

Lets take 6  6%2=0, 6%3=0...from 2 to 3(2 to 6/2)
here remainder is zero. So 6 is not prime number.
Lets take 5 now
5%2=1
here remainder is greater than zero. So 5 is prime number.

      PrimeNumberCheck.java  

public class PrimeNumberCheck { public static void main(String[] args) { PrimeNumberCheck app = new PrimeNumberCheck(); System.out.println("Eneter number:"); Scanner scanner = new Scanner(System.in); int number = scanner.nextInt(); System.out.println(app.isPrime(number)); } private boolean isPrime(int number) { boolean isPrime = true; for (int i = 2; i <= number / 2; i++) { if (number % i == 0) { return false; } } return isPrime; } } /* ****** INPUT ******** 5 ******* INPUT ******** ****** OUTPUT ******** true ******* OUTPUT ******** */

Continue Reading

Order of Execution in java Inheritance

Order of Execution

1. Parent Static Block 
2. Child Static Block 
3. Parent Normal Block 
4. Parent Constructor 
5. Child Normal Block 
6. Child Constructor
7. Child method invoked

Animal.java 

public class Animal { static { System.out.println("Animal Static Block "); } public Animal() { System.out.println("Animal Consuctor"); } { System.out.println("Animal Normal Block"); } public void aboutMe() { System.out.println("I am a Animal"); } }

Cow.java

public class Cow extends Animal { static { System.out.println("Cow Static Block "); } public Cow() { System.out.println("Cow Consuctor"); } { System.out.println("Cow Normal Block"); } public void aboutMe() { System.out.println("I am a Cow"); } }

App.java

public class App { public static void main(String[] args) { Cow cow = new Cow(); cow.aboutMe(); } }

Continue Reading

Java Spring Interview Questions

1. Load application Context on Spring?
1. ClassPathXmlApplicationContext ctx = new ClassPathXmlApplicationContext("applicationContext.xml");
2. Autowired
1. @Autowired
2. private ApplicationContext appContext;
2. Spring bean scopes: session and globalSession
1. GlobalSession is something which is connected to Portlet applications. When your application works in Portlet container it is built of some amount of portlets. Each portlet has its own session, but if your want to store variables global for all portlets in your application than you should store them in globalSession. This scope doesn't have any special effect different from session scope in Servlet based applications.
3. What is the difference between a portlet and a servlet?
1. Portlets are part of JSR-168 standard that regulates portal containers and components. This is different standard from standards for web containers (and servlets). Though there are definitely strong parallels between these two standards they differ in containers, APIs, life cycle, configuration, deployment, etc.
2. The main difference between portlet vs. servlet could be that while servlet always responds to single type of action - request, portlet (due to nature of its life cycle and stronger container bindings) has to respond to two types of actions: render and request. There are of course more to it but I found this as the core difference between the two when I studied portal development.
4. Difference between spring @Controller and @RestController annotation? 

@Controller

• @Controller is used to mark classes as Spring MVC Controller. 
• If we need to return values as JSON or XML then need to add @ResponseBody annotation above the method
@RestController 
• Its methods will automatically converte the response to JSON or XML. No need to add @ResponseBody annotation.

@Controller @ResponseBody public class MyController { } @RestController public class MyRestController { }

Continue Reading

Write a code to create deadlock in java

public class DeadLockEx { private String str1 = "SPRING"; private String str2 = "HIBERNATE"; public static void main(String[] args) { DeadLockEx app = new DeadLockEx(); app.t1.start(); app.t2.start(); } Thread t1 = new Thread("Thead 1") { public void run() { while (true) { synchronized (str1) { synchronized (str2) { System.out.println(str1 + str2); } } } } }; Thread t2 = new Thread("Thead 2") { public void run() { while (true) { synchronized (str2) { synchronized (str1) { System.out.println(str2 + str1); } } } } }; }

Continue Reading

Java Oops Interview Questions

1. Implementing two interfaces in a class with same method. Which interface method is overridden? 

interface A{ int f(); } interface B{ int f(); } class Test implements A, B{ public static void main(String... args) throws Exception{ } @Override public int f() { // from which interface A or B return 0; } }

• If a type implements two interfaces, and each interface define a method that has identical signature, then in effect there is only one method, and they are not distinguishable. 
• If, say, the two methods have conflicting return types, then it will be a compilation error. This is the general rule of inheritance 
• This is the general rule of inheritance, method overriding, hiding, and declarations, and applies also to possible conflicts not only between 2 inherited interface methods, but also an interface and a super class method, or even just conflicts due to type erasure of generics.
• Reference
https://stackoverflow.com/questions/2801878/implementing-two-interfaces-in-a-class-with-same-method-which-interface-method

Continue Reading

Two Sum on arrays

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
Example:
Given nums = [ 3, 4, 5, 2, 10, 8, 9 ]
target = 19
Because nums[4] + nums[6] = 10 + 9 = 19, return [4, 6]
Approach:
step1. take 3 and then add 3 with all other elements
step2. take 4 and then add 4 with all other elements.Continue same till 9

 
      TwoSum.java  

public class TwoSum { public static void main(String[] args) { int[] arr = { 3, 4, 5, 2, 10, 8, 9 }; int target = 19; TwoSum app = new TwoSum(); int[] rslt = app.twosum(arr, target); System.out.print(rslt[0] + ", " + rslt[1]); } private int[] twosum(int[] arr, int target) { int[] rslt = new int[2]; // take 3 and then add 3 with all other // take 4 and then add 4 with all other elemnts.Continue same till 9 for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length; j++) { if (j != i) { // don't add the same indexes int sum = arr[i] + arr[j]; if (sum == target) { rslt[0] = i; rslt[1] = j; break; } } } } return rslt; } } /* ****** INPUT ******** { 3, 4, 5, 2, 10, 8, 9 } 19 ******* INPUT ******** ****** OUTPUT ******** 4, 6 ******* OUTPUT ******** */

Continue Reading

Java JDBC Datasouce

• Data Source Objects is a factory of connections to physical data sources.
• To use datasource, We need to configure the data source in the naming service of JBoss or Tomacat. Webapplication can use JNDI lookup to get the datasource and using that data source we can create the connections.
• 
• The interface Datasource is packaged inside javx.sql package. Datasource Interface is imlemented by the driver vendor like mySql, Oracle etc.
• There are three types of implementations for Datasouce interface.
  1. Basic Pooling Implementation:- Produces a standard connection object. The connection produced is idential to the connection produced by the DriverManager class.A basic DataSource implementation produces standard Connection objects that are not pooled or used in a distributed transaction.
  2. Connection Pooling Implementation:- A DataSource implementation that supports connection pooling produces Connection objects that participate in connection pooling, that is, connections that can be recycled.
  3. Distributed Transaction Implementation:- A DataSource implementation that supports distributed transactions produces Connection objects that can be used in a distributed transaction, that is, a transaction that accesses two or more DBMS servers.
  
• Advantages of DataSource Objects
  1. Programmers no longer have to hard code the driver name or JDBC URL in their applications, which makes them more portable.
  2. When the DataSource interface is implemented to work with a ConnectionPoolDataSource implementation, all of the connections produced by instances of that DataSource class will automatically be pooled connections.
  3. when the DataSource implementation is implemented to work with an XADataSource class, all of the connections it produces will automatically be connections that can be used in a distributed transaction.
  
  
  

      Tomcat DataSource JNDI

•  To declare a JNDI DataSource for the MySQL database, create a Resource XML element with the following content:
• Add this element inside the root element context tag in the context.xml file of tomcatThere are two places where the context.xml file can reside (create one if not exist):
  1. Inside /META-INF directory of a web application
  2. Inside $CATALINA_BASE/conf directory:
  
• Add the following declaration into the web.xml file:
• We can look up the configured JNDI DataSource using Java code as follows:
  
  Context initContext = new InitialContext(); Context envContext = (Context) initContext.lookup("java:comp/env"); DataSource ds = (DataSource) envContext.lookup("jdbc/UsersDB"); Connection conn = ds.getConnection();

      Interface

• Interface is a blueprint of a class and it contains only public abstract methods and staic final variables(contants)
• Sub classes able implemeting interface by implementing all nethods.
• Interfaces can be use when we need to achieve muliple inheritance because it supports multiple inheritance.

Continue Reading

Switching Case of String

All the uppercase letters should be converted to lowercase and all the lowercase letters should be converted to uppercase

 
      StringCaseSwith.java  

import java.util.Scanner; /** * all the uppercase letters should be converted to lowercase and all the * lowercase letters should be converted to uppercase */ public class StringCaseSwith { public static void main(String[] args) { String c = ""; String rslt = ""; Scanner scanner = new Scanner(System.in); String str = scanner.next(); for (int i = 0; i < str.length(); i++) { c += str.charAt(i); if (c.equals(c.toUpperCase())) { rslt += c.toLowerCase(); } if (c.equals(c.toLowerCase())) { rslt += c.toUpperCase(); } c = ""; } System.out.println(rslt); } } /* ****** INPUT ******** Rob ******* INPUT ******** ****** OUTPUT ******** rOB ******* OUTPUT ******** */

Continue Reading

Find missing number between 1 to N with low time complexity

• Need to find missing number between 1 to N with low time complexity O(n).
• Step1: Get sum of natural numbers from 1 to N as N x(N+1)/2
• Step2: Get sum of array elements
• Step3: Missing number = natural numbers sum - array sum

      FindMissingNumber.java

public class FindMissingNumber { private static final int END_NUMBER = 10; private int getMissingNumber(int[] arr) { int missingNum = 0; int arrSum = 0; for (int i = 0; i < arr.length; i++) { arrSum += arr[i]; } int naturalSum = END_NUMBER * (END_NUMBER + 1) / 2; missingNum = naturalSum - arrSum; return missingNum; } public static void main(String[] args) { int[] arr = { 1, 2, 3, 0, 5, 6, 7, 8, 9, 10}; FindMissingNumber app = new FindMissingNumber(); int missingNum = app.getMissingNumber(arr); System.out.println("Missing Number = " + missingNum); } } ****** OUTPUT ******** Missing Number = 4 ******* OUTPUT ********

Continue Reading

When to use Abstract class and When to use Interface in Java

• Abstraction is one among the oops concepts and it means hiding the implementation details.In java abstraction can be achieved by two methods.
  1. Abstract Class
  2. Interface

      Abstract Class

• Abstract class contains both unimplemented and implemented methods. Abstratct class must have the keyword abstract and it may not contains any abstract method.
• If it acontains any abstract method then all subclasses must have to implement it.
• Abstarct classes can be initiated by exending it.
• We can use abstract class when some functionalities are common across all subclasses and some of the functionlaties differs.
• Consider we have Bank as abstarct class and it has implemented methods deposit() and withdraw(). Here deposit() and withdraw() are common across all banks. calcualte() is varies based on bank differs. So here we can use abstarct class.

      Bank.java

public abstract class Bank { public void deposit(double ammount) { System.out.println("Ammount has deposited, " + ammount); } public void withdraw(double ammount) { System.out.println("Ammount has withdrawn, " + ammount); } public abstract double calculateInterest(); }

      HDFC.java

public class HDFC extends Bank { private static final double MONTHLY_DEDUCTION = 12; private static final double YEARLY_DEDUCTION = 40; private double ammount = 1000; @Override public double calculateInterest() { double interest = ammount + MONTHLY_DEDUCTION + YEARLY_DEDUCTION; return interest; } }

      ICICI.java

public class ICICI extends Bank { private static final double MONTHLY_DEDUCTION = 12; private static final double QUARTARLY_DEDUCTION = 15; private double ammount = 1000; @Override public double calculateInterest() { double interest = ammount + MONTHLY_DEDUCTION + (QUARTARLY_DEDUCTION * 4); return interest; } }

      Interface

• Interface is a blueprint of a class and it contains only public abstract methods and staic final variables(contants)
• Sub classes able implemeting interface by implementing all nethods.
• Interfaces can be use when we need to achieve muliple inheritance because it supports multiple inheritance.

Java 8

• After being introduced Default Method, the Interfaces and abstract Classes seems similar, however, they still different concept in Java 8.
•  Abstract Class can define constructor. They are more structured and can have a state associated with them. 
• While in contrast, default method can be implemented only in the terms of invoking other Interface methods, with no reference to a particular implementation's state. Hence, both use for different purposes and choosing between two really depends on the scenario context.

Continue Reading

Set Implementation in Java

• Set conatins only unique elements.
• HashSet achieves uniqueness of its elements by using hashmap
• Whenever we create an object of hashset inernally it will create an object of hashmap.
• If we add an element into a set it will store as key for map. But same time we need a value for key. That value can be Object instance.So whenever we add an element to set it will create Hash map entry with key as added element and value as DUMMY Object.
• There are two possible output we will get we put an entry into a hashmap
  1. null: If the Key is unique and succussfully added to tha map. 2. Old Value of the Key: If the key is duplicate

      SkHashSet.java

package com.sk.custom_hashset; import java.util.HashMap; import java.util.Set; public class SkHashSet { private HashMap MAP = new HashMap(); private static final Object DUMMY = new Object(); public boolean add(E element) { return MAP.put(element, DUMMY) == null; } public int size() { return MAP.size(); } public Set getAll() { return MAP.keySet(); } }

Download Source

Continue Reading

Java Hashmap Implementation

• Hashmap stores key value pairs
• HashMap uses hash to insert and get elements. hash = key.hashCode()%BUCKET_ARRAY_SIZE]
• Its an array of Entry LinkedList and each LinkedList identifies using hash. LinkedList will be stored in hash index of BUCKET_ARRAY
• Entries become LinkedList by keeping next entry in current entry.

Steps To create Hashmap
 Entry Class
     It  Make an Entry class to store the HashMap Entries.
Variable: key, value and next
All enties having the same hash[key.hashCode()%BUCKET_ARRAY_SIZE] linked together using next property having the type Entry. next will holds next entry.Always append new entry in last of linked List.
 Put
Finding the bucket(Linked List) using hash[key.hashCode()%BUCKET_ARRAY_SIZE]
if entry is null in bucket then create new Entry and add to array with key.hashCode()%BUCKET_ARRAY_SIZE as key
if bucket already contains entry and key already existing then get entry and override value
if bucket already exists and key not contains then attach new entry at the end of the linkedList[looping till next become null]
 Get
Finding the bucket(LinkedList) using hash[key.hashCode()%BUCKET_ARRAY_SIZE]
Loop entry till entry become and null and return value if key exists while looping

      Entry.java

package com.sk.custom_hashmap; public class Entry { private final K key; private V value; private Entry next; public Entry(K k, V v) { key = k; value = v; } public V getValue() { return value; } public void setValue(V value) { this.value = value; } public Entry getNext() { return next; } public void setNext(Entry next) { this.next = next; } public K getKey() { return key; } }

SkHashMap.java

package com.sk.custom_hashmap; import java.util.HashSet; import java.util.Set; public class SkHashMap { private int BUKET_ARRAY_SIZE = 16;// initial capacity private double LOAD_FACTOR = 0.75; // no.of entries/BUKET_ARRAY_SIZE private Entry[] BUKET_ARRAY = new Entry[BUKET_ARRAY_SIZE]; @SuppressWarnings(value = { "unchecked" }) public void put(K key, V value) { int hash = key.hashCode() % BUKET_ARRAY_SIZE; // finding bucket Entry entry = BUKET_ARRAY[hash]; if (null == entry) { /** * creating a new Entry and add to array if the hash is not present * in bucket array. */ BUKET_ARRAY[hash] = new Entry(key, value); } else { /** * Overrides value if key already exists */ if (entry.getKey().equals(key)) { entry.setValue(value); } else { /** * need to append new Entry in the end.. So traverse across * Entrys till Entry.next ==null */ while (entry.getNext() != null) { entry = entry.getNext(); } entry.setNext(new Entry(key, value)); } } } @SuppressWarnings(value = { "unchecked", "unused" }) public V get(K key) { V value = null; int hash = key.hashCode() % BUKET_ARRAY_SIZE; Entry entry = BUKET_ARRAY[hash]; while (null != entry) { if (entry.getKey().equals(key)) { return entry.getValue(); } entry = entry.getNext(); } return null; } @SuppressWarnings(value = { "unchecked" }) public Set> getEntrySet() { Set> set = new HashSet>(); for (Entry enty : BUKET_ARRAY) { Entry entrry = enty; while (entrry != null) { set.add(entrry); entrry = entrry.getNext(); } } return set; } }

Load Factor

• Load Factor is a measure, which decides when exactly to increase the hashmap capacity(no.of buckets) to maintain get and put operation complexity of O(1).
• Default load factor of Hashmap is 0.75 (i.e 75% of current map size).
• Default capacity of Hashmap is 2^4 = 16 buckets.
• Let say we have well implemented hashcode() method, which make sure that key-value pair will be well distributed across 16 buckets equally.
• So, If there are 16 items in hashmap, then good hashcode method will distribute 1 item in each bucket. Searching for any item in this case will take only 1 look up.Now, If there are 32 items in hashmap, then good hashcode method will distribute 2 item in each bucket. Searching for any item in this case will take maximum 2 look up.Now, If there are 128 items in hashmap, then good hashcode method will distribute 8 item in each bucket. Searching for any item in this case will take maximum 8 look up.
• If the amount of item keeps on increasing and the number of buckets are fixed(16) then at one time, performance of hashmap will start degrading due to large number of items in each bucket.
• Now, say if there are 5,00,000 items in hashmap, then, good hashcode method will distribute 31,250 items in each bucket. Searching for any item in this case, will require maximum 31,250 look up.
If we increase the total number of buckets, when total items in each bucket starts increasing, then we will be able to keep constant number of items in each bucket and maintain the time complexity of O(1) for get and put operation. The decision of "When to increase the number of buckets" is decided by Load Factor.

Default, initial capacity of the HashMap is 16 and Load factor is 0.75

Load factor = Number of entries in a bucket / capacity(no. of buckets)

It is advisable to have a load factor of around 0.75 for keeping the put and get complexity around O(1).

Load Factor and Initial Capacity(Number of buckets) can be configured while creation of Hashmap like shown below,
HashMap m = new HashMap(int initialCapacity, float loadFactor);

Rehashing

• Rehashing is the process of re-calculating the hashcode of already stored entries (Key-Value pairs), to move them to another bigger size hashmap when Load factor threshold is reached.
• When the number of items in map, crosses the Load factor limit at that time hashmap doubles its capacity and hashcode is re-calculated of already stored elements for even distribution of key-value pairs across new buckets.

HashMap Collision Occur 

• There are several class in JDK which are based upon the hash table data structure
• HashMap,
• LinkedHashMap,
• Hashtable,
• WeakHashMap,
• IdentityHashMap,
• ConcurrentHashMap, 
• TreeMap, and
• EnumMap.
• Underlying working of all these Map is pretty much same as discussed in How does HashMap internally works in Java, except some minor differences in their specific behaviors. Since hash table data structure is subject to collision all these implementations are required to handle the collision.
• A collision will occur when two different keys have the same hashCode, which can happen because two unequal objects in Java can have the same hashCode.
• HashMap handles collision by using linked list to store map entries ended up in same array location or bucket location
• From Java 8 onwards, HashMap, ConcurrentHashMap, and LinkedHashMap will use the balanced binary tree in place of linked list to handle frequently hash collisions. The idea is to switch to the balanced tree once the number of items in a hash bucket grows beyond a certain threshold. This will improve the worst case get() method performance from O(n) to O(log n).
• Legacy class Hashtable which exists in JDK from Java 1 will not use the balanced binary tree to handle frequent hash collision to keep its iteration order intact. This was decided to avoid breaking many legacy Java application which depends upon iteration order of Hashtable.
• Apart from Hashtable, WeakHashMap and IdentityHashMap will also continue to use the linked list for handling collision even in the case of frequent collisions.
• TreeMap
• Treemap class is like HashMap which stores key- value pairs . The major difference is that Treemap  sorts the key in ascending order.
• It sorts the TreeMap object keys using Red-Black tree algorithm.
• We should read the pseudo code of Red Black algorithm in order to understand the internal implementation 
• As the name of the algorithm suggests ,color of every node in the tree is either red or black.
• Root node must be Black in color.
• Red node can not have a red color neighbor node.
• All paths from root node to the null should consist the same number of black nodes 
• Rotations maintains the inorder ordering of the keys(x,y,z).
• A rotation can be maintained in O(1) time.

• Why  java's  treemap does not allow an initial size ?
• HashMap reallocates its internals as the new one gets inserted while TreeMap does not reallocate nodes on adding new ones. Thus , the size of the TreeMap  dynamically increases if needed , without shuffling the internals. So it is meaningless to set the initial size of the TreeMap .
• ConcurrentHashMap 
• public ConcurrentHashMap (int initialCapacity, float loadFactor, int concurrencyLevel)
• So the above line  creates a new, empty map with the specified initial capacity, load factor and concurrency level.
• initialCapacity - the initial capacity. The implementation performs internal sizing to accommodate this many elements.
• concurrencyLevel - the estimated number of concurrently updating threads. The implementation performs internal sizing to try to accommodate this many threads
• In the ConcurrentHashMap Api , you will find the following constants.
• static final int DEFAULT_INITIAL_CAPACITY = 16;
• static final int DEFAULT_CONCURRENCY_LEVEL = 16;
•  Instead of a map wide lock, ConcurrentHashMap maintains  a list of 16 locks by default ( number of locks equal to the initial capacity , which is by default  16) each of which is used to lock on a single bucket of the Map.

Download Source

Continue Reading

Lifecycle and States of a Thread

A thread in Java at any point of time exists in any one of the following states.

1. New
2. Runnable
3. Blocked
4. Waiting
5. Timed Waiting
6. Terminated

Continue Reading