Internal implementation of Set/HashSet (How Set Ensures Uniqueness)

Set Implementation Internally in Java

Each and every element in the set is unique .  So that there is no duplicate element in set .

 what happens internally when you pass duplicate elements in the  add() method of the Set object , It will return false and do not add to the HashSet , as the element is already present .So far so good .

But the main problem arises that how it returns false . So here is the answer

When you open the HashSet implementation of the add() method in Java Apis that is rt.jar , you will find the following code in it

public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable

{
    private transient HashMap<E,Object> map;
    
    // Dummy value to associate with an Object in the backing Map
    
    private static final Object PRESENT = new Object();
    
    
    
    public HashSet() {
        map = new HashMap<>();
    }
    
    // SOME CODE ,i.e Other methods in Hash Set
    
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    
    
    
    // SOME CODE ,i.e Other methods in Hash Set
}

So , we are achieving uniqueness in Set,internally in java  through HashMap . Whenever you create an object of HashSet it will create an object of HashMap as you can see in the italic lines in the above code .

The main point to notice in above code is that put (key,value) will return

1.  null , if key is unique and added to the map
2.  Old Value of the key , if key is duplicate

So , in HashSet add() method ,  we check the return value of map.put(key,value) method with null value
i.e.

   public boolean add(E e) {
            return map.put(e, PRESENT)==null;
       }

So , if map.put(key,value) returns null ,then
map.put(e, PRESENT)==null      will return true and element is added to the HashSet .



So , if map.put(key,value) returns old value of the key ,then
map.put(e, PRESENT)==null      will return false and element is  not added to the HashSet .

Primitive Data Types

The Java programming language is statically-typed, which means that all variables must first be declared before they can be used. 


A primitive type is predefined by the language and is named by a reserved keyword. Primitive values do not share state with other primitive values. The eight primitive data types supported by the Java programming language are:

• byte: The byte data type is an 8-bit signed two's complement integer. It has a minimum value of -128 and a maximum value of 127 (inclusive). The byte data type can be useful for saving memory in large arrays, where the memory savings actually matters. They can also be used in place of int where their limits help to clarify your code; the fact that a variable's range is limited can serve as a form of documentation.
• short: The short data type is a 16-bit signed two's complement integer. It has a minimum value of -32,768 and a maximum value of 32,767 (inclusive). As with byte, the same guidelines apply: you can use a short to save memory in large arrays, in situations where the memory savings actually matters.
• int: By default, the int data type is a 32-bit signed two's complement integer, which has a minimum value of -2³¹ and a maximum value of 2³¹-1. In Java SE 8 and later, you can use theint data type to represent an unsigned 32-bit integer, which has a minimum value of 0 and a maximum value of 2³²-1. Use the Integer class to use int data type as an unsigned integer. See the section The Number Classes for more information. Static methods like compareUnsigned, divideUnsigned etc have been added to the Integer class to support the arithmetic operations for unsigned integers.
• long: The long data type is a 64-bit two's complement integer. The signed long has a minimum value of -2⁶³ and a maximum value of 2⁶³-1. In Java SE 8 and later, you can use the longdata type to represent an unsigned 64-bit long, which has a minimum value of 0 and a maximum value of 2⁶⁴-1. Use this data type when you need a range of values wider than those provided by int. The Long class also contains methods like compareUnsigned, divideUnsigned etc to support arithmetic operations for unsigned long.
• float: The float data type is a single-precision 32-bit IEEE 754 floating point. Its range of values is beyond the scope of this discussion, but is specified in the Floating-Point Types, Formats, and Values section of the Java Language Specification. As with the recommendations for byte and short, use a float (instead of double) if you need to save memory in large arrays of floating point numbers. This data type should never be used for precise values, such as currency. For that, you will need to use the java.math.BigDecimal class instead.Numbers and Strings covers BigDecimal and other useful classes provided by the Java platform.
• double: The double data type is a double-precision 64-bit IEEE 754 floating point. Its range of values is beyond the scope of this discussion, but is specified in the Floating-Point Types, Formats, and Values section of the Java Language Specification. For decimal values, this data type is generally the default choice. As mentioned above, this data type should never be used for precise values, such as currency.
• boolean: The boolean data type has only two possible values: true and false. Use this data type for simple flags that track true/false conditions. This data type represents one bit of information, but its "size" isn't something that's precisely defined.
• char: The char data type is a single 16-bit Unicode character. It has a minimum value of '\u0000' (or 0) and a maximum value of '\uffff' (or 65,535 inclusive).
  
  
  The following chart summarizes the default values for the above data types.

  Data Type	Default Value (for fields)
  byte	0
  short	0
  int	0
  long	0L
  float	0.0f
  double	0.0d
  char	'\u0000'
  String (or any object)	null
  boolean	false

• 
  

Common Observations:

       final int i =100;
        byte b = i;
        System.out.println(b);  // valid prints 100


        /*
        final int x =1000;
        byte y = x;   //compile error
        System.out.println(y);  */


        /*
         int x =100;
        byte y = (byte) x;   //valid
        System.out.println(y); */


        /*int x =100;
        byte y =  x;   //compile error. Nee to cast x --  byte y =  (byte) x
        System.out.println(y); */

        char c = 9;   //valid
        char d = 'A';  //valid
        char e = 0x12; //valid

        int j = 0345;  //valid
   
        System.out.println(1+2f+3d); // print 6.0

        /*final long test = 1;
        byte b1 = test; //compile error
        System.out.println(b1);*/
 

OverLoading vs Overriding

Method overloading and method overriding in Java is two important concept in Java which allows Java programmer to declare method with same name but different behaviour. Method overloading and method overriding is based on polymorphism in Java. 

In case of method overloading, method with same name co-exists in same class but they must have different method signature, while in case of method overriding, method with same name is declared in derived class or sub class.Method overloading is resolved using static binding in Java at compile time while method overriding is resolved using dynamic binding in Java at runtime. In short When you overload a method in Java its method signature got changed while in case of overriding method signature remains same but a method can only be overridden in sub class

OverLoad:

If you have two methods with same name in one Java class with different method signature than its called overloaded method in Java. Generally overloaded method in Java has different set of arguments to perform something based on different number of input. You can also overload constructor in Java, which we will see in following example of method overloading in Java. Binding of overloading method occurs during compile time and overloaded calls resolved using static binding. To overload a Java method just changes its signature. Just remember in order to change signature you either need to change number of argument, type of argument or order of argument in Java if they are of different types. Since return type is not part of method signature simply changing return type will result in duplicate method and you will get compile time error in Java.

 Remember you can overload static method in Java, you can also overload private and final method in Java but you can not override them.

You can overload the main() method, but only public static void main(String[] args) will be used when your class is launched by the JVM.

Override:

In order to override a Java method, you need to create a child class which extends parent. Overridden method in Java also shares same name as original method in Java but can only be overridden in sub class. Original method has to be defined inside interface or base class, which can be abstract as well. When you override a method in Java its signature remains exactly same including return type. JVM resolves correct overridden method based upon object at run-time by using dynamic binding in Java.

Rule of Method Override

1. Method signature must be same including return type, number of method parameters, type of parameters and order of parameters
2. Overriding method can not throw higher Exception than original or overridden method. means if original method throws IOException than overriding method can not throw super class of IOException e.g. Exception but it can throw any sub class of IOException or simply does not throw any Exception. This rule only applies to checked Exception in Java, overridden method is free to throw any unchecked Exception.
3. Overriding method can not reduce accessibility of overridden method , means if original or overridden method is public than overriding method can not make it protected.

Summary

1. First and most important difference between method overloading and overriding is that, In case of method overloading in Java, Signature of method changes while in case of method overriding it remain same.
2.  Second major difference between method overloading vs overriding in Java is that You can overload method in one class but overriding can only be done on subclass.
3. You can not override static, final and private method in Java but you can overload static, final or private method in Java.
4. Overloaded method in Java is bonded by static binding and overridden methods are subject to dynamic binding.

Application Server vs Web Server

1. Application Server supports distributed transaction and EJB. While Web Server only supports Servlets and JSP.

2. Application Server can contain web server in them. most of App server e.g. JBoss or WAS has Servlet and JSP container.

3. Though its not limited to Application Server but they used to provide services like Connection pooling, Transaction management, messaging, clustering, load balancing and persistence. Now Apache tomcat also provides connection pooling.

4. In terms of logical difference between web server and application server. web server is supposed to provide http protocol level service while application server provides support to web service and expose business level service e.g. EJB.

5. Application server are more heavy than web server in terms of resource utilization.

Thread vs Process in Java

1) Both process and Thread are independent path of execution but one process can have multiple Threads.

2) Every process has its own memory space, executable code and a unique process identifier (PID) while every thread has its own stack in Java but it uses process main memory and share it with other threads.

3) Threads are also refereed as task or light weight process (LWP) in operating system

4) Threads from same process can communicate with each other by using Programming language construct like wait and notify in Java and much simpler than inter process communication.

5) Another difference between Process and Thread in Java is that it's How Thread and process are created. It's easy to create Thread as compared to Process which requires duplication of parent process.

6) All Threads which is part of same process share system resource like file descriptors , Heap Memory and other resource but each Thread has its own Exception handler and own stack in Java.

There were some of the fundamental difference between Process and Thread in Java. Whenever you talk about Process vs Thread, just keep in mind that one process can spawn multiple Thread and share same memory in Java. Each thread has its own stack.

Some linux command map Java thread with light weight process or lwp, e.g. if you use prstat command in Solaris, you can get how many light weight process or Thread a particular Java program is using.

Volatile in Java

In general each thread has its own copy of variable, such that one thread is not concerned with the value of same variable in the other thread. But sometime this may not be the case. Consider a scenario in which the count variable is holding the number of times a method is called for a given class irrespective of any thread calling, in this case irrespective of thread access the count has to be increased. In this case the count variable is declared as volatile. The copy of volatile variable is stored in the main memory, so every time a thread access the variable even for reading purpose the local copy is updated each time from the main memory. The volatile variable also have performance issues.

Volatile keyword in Java is used as an indicator to Java compiler and  Thread that do not cache value of this variable and always read it from main memory. So if you want to share any variable in which read and write operation is atomic by implementation e.g. read and write in int or boolean variable you can declare them as volatile variable.


Java introduces some change in Java Memory Model (JMM),  Which  guarantees visibility of changes made by one thread to another also as "happens-before" which solves the problem of memory writes that happen in one thread can "leak through" and be seen by another thread. Java volatile keyword cannot be used with method or class and it can only be used with variable. Java volatile keyword also guarantees visibility and ordering , after Java 5 write to any volatile variable happens before any read into volatile variable. By the way use of volatile keyword also prevents compiler or JVM from reordering of code or moving away them from synchronization barrier.

Example of volatile keyword in Java:

To Understand example of volatile keyword in java let’s go back to Singleton pattern in Java and see double checked locking in Singleton with Volatile and without volatile keyword in java.

/**
 * Java program to demonstrate where to use Volatile keyword in Java.
 * In this example Singleton Instance is declared as volatile variable to ensure
 * every thread see updated value for _instance.
 *
 * @author Javin Paul
 */
public class Singleton{
private static volatile Singleton _instance; //volatile variable

public static Singleton getInstance(){

   if(_instance == null){
            synchronized(Singleton.class){
              if(_instance == null)
              _instance = new Singleton();
            }

   }
   return _instance;

}

If you look at the code carefully you will be able to figure out:

1) We are only creating instance one time

2) We are creating instance lazily at the time of first request comes.

If we do not make _instance variable volatile then Thread which is creating instance of Singleton is not able to communicate other thread, that instance has been created until it comes out of the Singleton block, so if Thread A is creating Singleton instance and just after creation lost the CPU, all other thread will not be able to see value of _instance as not null and they will believe its still null.

Why because reader threads are not doing any locking and until writer thread comes out of synchronized block, memory will not be synchronized and value of _instance will not be updated in main memory. With Volatile keyword in Java this is handled by Java himself and such updates will be visible by all reader threads.

 

When to use Volatile variable in Java

1) You can use Volatile variable if you want to read and write long and double variable atomically. long and double both are 64 bit data type and by default writing of long and double is not atomic and platform dependence. Many  platform perform write in long and double variable 2 step, writing 32 bit in each step, due to this its possible for a Thread to see 32 bit from two different write. You can avoid this issue by making long and double variable volatile in Java.

2) Volatile variable can be used as an alternative way of achieving synchronization in Java in some cases, like Visibility. with volatile variable its guaranteed that all reader thread will see updated value of volatile variable once write operation  completed, without volatile keyword different reader thread may see different values.

3) volatile variable can be used to inform compiler that a particular field is subject to be accessed by multiple threads, which will prevent compiler from doing any reordering or any kind of optimization which is not desirable in multi-threaded environment. Without volatile variable compiler can re-order code, free to cache value of volatile variable instead of always reading from main memory. like following example without volatile variable may result in infinite loop

private boolean isActive = thread;
public void printMessage(){
  while(isActive){
     System.out.println("Thread is Active");
  }
} 

without volatile modifier its not guaranteed that one Thread see the updated value of isActive from other thread. compiler is also free to cache value of isActive instead of reading it from main memory in every iteration. By making isActive a volatile variable you avoid these issue.

4) Another place where volatile variable can be used is to fixing double checked locking in Singleton pattern.

 

 

Important points on Volatile keyword in Java

1. volatile keyword in Java is only application to variable and using volatile keyword with class and method is illegal.

2. volatile keyword in Java guarantees that value of volatile variable will always be read from main memory and not from Thread's local cache.

3. In Java reads and writes are atomic for all variables declared using Java volatile keyword (including long and double variables).

4. Using Volatile keyword in Java on variables reduces the risk of memory consistency errors, because any write to a volatile variable in Java establishes a happens-before relationship with subsequent reads of that same variable.

5. From Java 5 changes to a volatile variable are always visible to other threads. What’s more it also means that when a thread reads a volatile variable in java, it sees not just the latest change to the volatile variable but also the side effects of the code that led up the change.

6. Reads and writes are atomic for reference variables are for most primitive variables (all types except long and double) even without use of volatile keyword in Java.

7. An access to a volatile variable in Java never has chance to block, since we are only doing a simple read or write, so unlike a synchronized block we will never hold on to any lock or wait for any lock.

8. Java volatile variable that is an object reference may be null.

9. Java volatile keyword doesn't means atomic, its common misconception that after declaring volatile ++ will be atomic, to make the operation atomic you still need to ensure exclusive access using synchronized method or block in Java.

10. If a variable is not shared between multiple threads no need to use volatile keyword with that variable.

 

 

Difference between synchronized and volatile keyword in Java

 

Difference between volatile and synchronized is another popular core Java question asked in multi-threading and concurrency interviews. Remember volatile is not a replacement of synchronized keyword but can be used as an alternative in certain cases. Here are few differences between volatile and synchronized keyword in Java.

1. Volatile keyword in java is a field modifier, while synchronized modifies code blocks and methods.

2. Synchronized obtains and releases lock on monitor’s java volatile keyword doesn't require that.

3. Threads in Java can be blocked for waiting any monitor in case of synchronized, that is not the case with volatile keyword in Java.

4. Synchronized method affects performance more than volatile keyword in Java.

5. Since volatile keyword in Java only synchronizes the value of one variable between Thread memory  and "main" memory  while synchronized synchronizes the value of all variable between thread memory and "main" memory and locks and releases a monitor to boot. Due to this reason synchronized keyword in Java is likely to have more overhead than volatile.

6. You can not synchronize on null object but your volatile variable in java could be null.

7. From Java 5 Writing into a volatile field has the same memory effect as a monitor release, and reading from a volatile field has the same memory effect as a monitor acquire

 

Interview Question on Singleton Design Pattern

What is Singleton class? Have you used Singleton before?
Singleton is a class which has only one instance in whole application and provides a getInstance() method to access the singleton instance. There are many classes in JDK which is implemented using Singleton pattern like java.lang.Runtime which provides getRuntime() method to get access of it and used to get free memory and total memory in Java

What is double checked locking in Singleton?One of the most hyped question on Singleton pattern and really demands complete understanding to get it right because of Java Memory model caveat prior to Java 5. If a guy comes up with a solution of using volatile keyword with Singleton instance and explains it then it really shows it has in depth knowledge of Java memory model and he is constantly updating his Java knowledge.

Answer: Double checked locking is a technique to prevent creating another instance of Singleton when call to getInstance() method is made in multi-threading environment. In Double checked locking pattern as shown in below example, singleton instance is checked two times before initialization.

public static Singleton getInstance(){
      if(_INSTANCE == null){
          synchronized(Singleton.class){
          //double checked locking - because second check of Singleton instance with lock
                if(_INSTANCE == null){
                    _INSTANCE = new Singleton();
                }
            }
          }
      return _INSTANCE;
}

Double checked locking should only be used when you have requirement for lazy initialization otherwise use Enum to implement singleton or simple static final variable.

How do you prevent for creating another instance of Singleton using clone() method?This type of questions generally comes some time by asking how to break singleton or when Singleton is not Singleton in Java.
Answer: Preferred way is not to implement Clonnable interface as why should one wants to create clone() of Singleton and if you do just throw Exception from clone() method as  “Can not create clone of Singleton class”. 

How many ways you can write Singleton Class in Java?
Answer:  I know at least four ways to implement Singleton pattern in Java
1) Singleton by synchronizing getInstance() method
2) Singleton with public static final field initialized during class loading.
3) Singleton generated by static nested class, also referred as Singleton holder pattern.
4) From Java 5 on-wards using Enums

What is lazy and early loading of Singleton and how will you implement it?This is another great Singleton interview question in terms of understanding of concept of loading and cost associated with class loading in Java. Many of which I have interviewed not really familiar with this but its good to know concept.

Answer: As there are many ways to implement Singleton like using double checked locking or Singleton class with static final instance initialized during class loading. Former is called lazy loading because Singleton instance is created only when client calls getInstance() method while later is called early loading because Singleton instance is created when class is loaded into memory.


Is it better to make whole getInstance() method synchronized or just critical section is enough? Which one you will prefer?This is really nice question and I mostly asked to just quickly check whether candidate is aware of performance trade off of unnecessary locking or not. Since locking only make sense when we need to create instance and rest of the time its just read only access so locking of critical section is always better option. read more about synchronization on How Synchronization works in Java
Answer: This is again related to double checked locking pattern, well synchronization is costly and when you apply this on whole method than call to getInstance() will be synchronized and contented. Since synchronization is only needed during initialization on singleton instance, to prevent creating another instance of Singleton,  It’s better to only synchronize critical section and not whole method. Singleton pattern is also closely related to factory design pattern where getInstance() serves as static factory method.

Java Banking Interview Questions

What is the difference between creating String as new() and literal?

When we create string with new() Operator, it’s created in heap and not added into string pool while String created using literal are created in String pool itself which exists in PermGen area of heap.

String str = new String("Test");
 
does not  put the object str in String pool , we need to call String.intern() method which is used to put  them into String pool explicitly. its only when you create String object as String literal e.g. String s = "Test" Java automatically put that into String pool. By the way there is a catch here, Since we are passing arguments as "Test", which is a String literal, it will also create another object as "Test" on string pool. This is the one point, which has gone unnoticed, until knowledgeable readers of Javarevisited blog suggested it

What is the difference when String is gets created using literal or new() operator ?
When we create string with new() operator,  its created in heap only and not added into string pool, while String created using literal are created in String pool itself which exists in PermGen area of heap. You can put such string object into pool by calling intern() method. If you happen to create same String object multiple times, intern() can save some memory for you.

What will be the problem if you don't override hashcode() method ?
If you don't override equals method, than contract between equals and hashcode will not work, according to which, two object which are equal by equals() must have same hashcode. In this case other object may return different hashcode and will be stored on that location, which breaks invariant of HashMap class, because they are not supposed to allow duplicate keys. When you add object using put() method, it iterate through all Map.Entry object present in that bucket location, and update value of previous mapping, if Map already contains that key. This will not work if hashcode is not overridden

When do you override hashcode and equals() ?
Whenever necessary especially if you want to do equality check  based upon business logic rather than object equality e.g. two employee object are equal if they have same emp_id, despite the fact that they are two different object, created by different part of code. Also overriding both these methods are must if you want to use them as key in HashMap. Now as part of equals-hashcode contract in Java, when you override equals, you must overide hashcode as well, otherwise your object will not break invariant of classes e.g. Set, Map which relies on equals() method for functioning properly.

How does substring () inside String works?

Another good Java interview question, I think answer is not sufficient but here it is “Substring creates new object out of source string by taking a portion of original string”.  This question was mainly asked to see if developer is familiar with risk of memory leak, which substring can create. Until Java 1.7, substring holds reference of original character array, which means even a substring of 5 character long, can prevent 1GB character array from garbage collection, by holding a strong reference. This issue is fixed in Java 1.7, where original character array is not referenced any more, but that change also made creation of substring bit costly in terms of time. Earlier it was on the range of O(1), which could be O(n) in worst case on Java 7.

Final In Java

Final is a keyword or reserved word in java and can be applied to member variables, methods, class and local variables in Java. Once you make a reference final you are not allowed to change that reference and compiler will verify this and raise compilation error if you try to re-initialized final variables in java.

 

Final and Immutable Class in Java

 

Final keyword helps to write immutable class. Immutable classes are the one which can not be modified once it gets created and String is primary example of immutable and final class . Immutable classes offer several benefits one of them is that they are effectively read-only and can be safely shared in between multiple threads without any synchronization overhead. You can not make a class immutable without making it final and hence final keyword is required to make a class immutable in java.

Important points on final in Java

1. Final keyword can be applied to member variable, local variable, method or class in Java.

2. Final member variable must be initialized at the time of declaration or inside constructor, failure to do so will result in compilation error.

3. You can not reassign value to final variable in Java.

4. Local final variable must be initializing during declaration.

5. Only final variable is accessible inside anonymous class in Java

 

6. Final method can not be overridden in Java.

7. Final class can not be inheritable in Java.

8. Final is different than finally keyword which is used on Exception handling in Java.

 

9. Final should not be confused with finalize() method which is declared in object class and called before an object is garbage collected by JVM.

 

10. All variable declared inside java interface are implicitly final.

11. Final and abstract are two opposite keyword and a final class can not be abstract in java.

 

12. Final methods are bonded during compile time also called static binding.

13. Final variables which is not initialized during declaration are called blank final variable and must be initialized on all constructor either explicitly or by calling this(). Failure to do so compiler will complain as "final variable (name) might not be initialized".

14. Making a class, method or variable final in Java helps to improve performance because JVM gets an opportunity to make assumption and optimization.

15. As per Java code convention final variables are treated as constant and written in all Caps e.g.

private final int COUNT=10;

16. Making a collection reference variable final means only reference can not be changed but you can add, remove or change object inside collection. For example:

private final List Loans = new ArrayList();

list.add(“home loan”);  //valid

list.add("personal loan"); //valid

loans = new Vector();  //not valid

 

Difference Between Stack and Heap in Java

In general both stack and heap are part of memory, a program is allocated and used for different purposes. Java program runs inside JVM which is launched as a process by "java" command. Java also uses both stack and heap memory for different needs

 

1) Main difference between heap and stack is that stack memory is used to store local variables and function call, while heap memory is used to store objects in Java. No matter, where object is created in code e.g. as member variable, local variable or class variable,  they are always created inside heap space in Java.

2) Each Thread in Java has there own stack which can be specified using -Xss JVM parameter, similarly you can also specify heap size of Java program using JVM option -Xms and -Xmx where -Xms is starting size of heap and -Xmx is maximum size of java heap.

 

3) If there is no memory left in stack for storing function call or local variable, JVM will throw java.lang.StackOverFlowError, while if there is no more heap space for creating object, JVM will throw java.lang.OutOfMemoryError: Java Heap Space.

 

4) If you are using Recursion, on which method calls itself, You can quickly fill up stack memory. Another difference between stack and heap is that size of stack memory is lot lesser than size of  heap memory in Java.

5) Variables stored in stacks are only visible to the owner Thread, while objects created in heap are visible to all thread. In other words stack memory is kind of private memory of Java Threads, while heap memory is shared among all threads.