Important Questions on click of this link
Immutable classes in Java
Immutable class Nice Explanation on click of this link
Rules to define immutable classes
The following rules define a simple strategy for creating immutable objects.
Don't provide "setter" methods - methods that modify fields or objects referred to by fields. 1.
Make all fields final and private. 2.
Don't allow subclasses to override methods. The simplest way to do this is to declare the class as final. A 3. more sophisticated approach is to make the constructor private and construct instances in factory methods. If the instance fields include references to mutable objects, don't allow those objects to be changed: 4. Don't provide methods that modify the mutable objects. 5.
Don't share references to the mutable objects. Never store references to external, mutable objects passed to 6.
the constructor; if necessary, create copies, and store references to the copies. Similarly, create copies of
your internal mutable objects when necessary to avoid returning the originals in your methods.
Immutable Objects
Creating an immutable version of a type using defensive copying
Some basic types and classes in Java are fundamentally mutable. For example, all array types are mutable, and so are classes like java.util.Data . This can be awkward in situations where an immutable type is mandated. One way to deal with this is to create an immutable wrapper for the mutable type. Here is a simple wrapper for an array of integers
public class ImmutableIntArray {
private final int[] array;
public ImmutableIntArray(int[] array) {
this.array = array.clone();
}
public int[] getValue() {
return this.clone();
}
}
This class works by using defensive copying to isolate the mutable state (the int[] ) from any code that might mutate it: The constructor uses clone() to create a distinct copy of the parameter array. If the caller of the constructor subsequent changed the parameter array, it would not affect the state of the ImmutableIntArray . The getValue() method also uses clone() to create the array that is returned. If the caller were to change the result array, it would not affect the state of the ImmutableIntArray .
We could also add methods to ImmutableIntArray to perform read-only operations on the wrapped array; e.g. get its length, get the value at a particular index, and so on.
Note that an immutable wrapper type implemented this way is not type compatible with the original type. You cannot simply substitute the former for the latter.
The recipe for an immutable class
An immutable object is an object whose state cannot be changed. An immutable class is a class whose instances are immutable by design, and implementation. The Java class which is most commonly presented as an example of immutability is java.lang.String.
The following is a stereotypical example:
public final class Person {
private final String name;
private final String ssn; // (SSN == social security number)
public Person(String name, String ssn) {
this.name = name;
this.ssn = ssn;
}
public String getName() {
return name;
}
public String getSSN() {
return ssn;
}
}
A variation on this is to declare the constructor as private and provide a public static factory method instead.
The standard recipe for an immutable class is as follows:
All properties must be set in the constructor(s) or factory method(s).
There should be no setters.
If it is necessary to include setters for interface compatibility reasons, they should either do nothing or throw
an exception.
All properties should be declared as private and final .
For all properties that are references to mutable types:
the property should be initialized with a deep copy of the value passed via the constructor, and
the property's getter should return a deep copy of the property value.
The class should be declared as final to prevent someone creating a mutable subclass of an immutable
class.
A couple of other things to note:
Immutability does not prevent object from being nullable; e.g. null can be assigned to a String variable.
If an immutable classes properties are declared as final , instances are inherently thread-safe. This makes
immutable classes a good building block for implementing multi-threaded applications.
Typical design flaws which prevent a class from
being immutable
Using some setters, without setting all needed properties in the constructor(s)
public final class Person { // example of a bad immutability
private final String name;
private final String surname;
public Person(String name) {
this.name = name;
}
public String getName() { return name;}
public String getSurname() { return surname;}
public void setSurname(String surname) { this.surname = surname); }
}
It’s easy to show that Person class is not immutable:
Person person = new Person("Joe");
person.setSurname("Average"); // NOT OK, change surname field after creation
To fix it, simply delete setSurname() and refactor the constructor as follows:
public Person(String name, String surname) {
this.name = name;
this.surname = surname;
}
Not marking instance variables as private and final
Take a look at the following class:
public final class Person {
public String name;
public Person(String name) {
this.name = name;
}
public String getName() {
return name;
}
}
The following snippet shows that the above class is not immutable:
Person person = new Person("Average Joe");
person.name = "Magic Mike"; // not OK, new name for person after creation
To fix it, simply mark name property as private and final .
Exposing a mutable object of the class in a getter
Take a look at the following class:
import java.util.List;
import java.util.ArrayList;
public final class Names {
private final List<String> names;
public Names(List<String> names) {
this.names = new ArrayList<String>(names);
}
public List<String> getNames() {
return names;
}
public int size() {
return names.size();
}
}
Names class seems immutable at the first sight, but it is not as the following code shows:
List<String> namesList = new ArrayList<String>();
namesList.add("Average Joe");
Names names = new Names(namesList);
System.out.println(names.size()); // 1, only containing "Average Joe"
namesList = names.getNames();
namesList.add("Magic Mike");
System.out.println(names.size()); // 2, NOT OK, now names also contains "Magic Mike"
This happened because a change to the reference List returned by getNames() can modify the actual list of Names .
To fix this, simply avoid returning references that reference class's mutable objects either by making defensive
copies, as follows:
public List<String> getNames() {
return new ArrayList<String>(this.names); // copies elements
}
or by designing getters in way that only other immutable objects and primitives are returned, as follows:
public String getName(int index) {
return names.get(index);
}
public int size() {
return names.size();
}
Injecting constructor with object(s) that can be modified outside the immutable class
This is a variation of the previous flaw. Take a look at the following class:
import java.util.List;
public final class NewNames {
private final List<String> names;
public Names(List<String> names) {
this.names = names;
}
public String getName(int index) {
return names.get(index);
}
public int size() {
return names.size();
}
}
As Names class before, also NewNames class seems immutable at the first sight, but it is not, in fact the following
snippet proves the contrary:
List<String> namesList = new ArrayList<String>();
namesList.add("Average Joe");
NewNames names = new NewNames(namesList);
System.out.println(names.size()); // 1, only containing "Average Joe"
namesList.add("Magic Mike");
System.out.println(names.size()); // 2, NOT OK, now names also contains "Magic Mike"
To fix this, as in the previous flaw, simply make defensive copies of the object without assigning it directly to the
immutable class, i.e. constructor can be changed as follows:
public Names(List<String> names) {
this.names = new ArrayList<String>(names);
}
Letting the methods of the class being overridden
Take a look at the following class:
public class Person {
private final String name;
public Person(String name) {
this.name = name;
}
public String getName() { return name;}
}
Person class seems immutable at the first sight, but suppose a new subclass of Person is defined:
public class MutablePerson extends Person {
private String newName;
public MutablePerson(String name) {
super(name);
}
@Override
public String getName() {
return newName;
}
public void setName(String name) {
newName = name;
}
}
now Person (im)mutability can be exploited through polymorphism by using the new subclass:
Person person = new MutablePerson("Average Joe");
System.out.println(person.getName()); prints Average Joe
person.setName("Magic Mike"); // NOT OK, person has now a new name!
System.out.println(person.getName()); // prints Magic Mike
To fix this, either mark the class as final so it cannot be extended or declare all of its constructor(s) as private .
Comparator And Comparable
// A Java program to demonstrate use of Comparable
import java.io.*;
import java.util.*;
// A class 'Movie' that implements Comparable
class Movie implements Comparable<Movie>
{
private double rating;
private String name;
private int year;
// Used to sort movies by year
public int compareTo(Movie m)
{
return this.year - m.year;
}
// Constructor
public Movie(String nm, double rt, int yr)
{
this.name = nm;
this.rating = rt;
this.year = yr;
}
// Getter methods for accessing private data
public double getRating() { return rating; }
public String getName() { return name; }
public int getYear() { return year; }
}
// Driver class
class Main
{
public static void main(String[] args)
{
ArrayList<Movie> list = new ArrayList<Movie>();
list.add(new Movie("Force Awakens", 8.3, 2015));
list.add(new Movie("Star Wars", 8.7, 1977));
list.add(new Movie("Empire Strikes Back", 8.8, 1980));
list.add(new Movie("Return of the Jedi", 8.4, 1983));
Collections.sort(list);
System.out.println("Movies after sorting : ");
for (Movie movie: list)
{
System.out.println(movie.getName() + " " +
movie.getRating() + " " +
movie.getYear());
}
}
}
Output:
Movies after sorting :
Star Wars 8.7 1977
Empire Strikes Back 8.8 1980
Return of the Jedi 8.4 1983
Force Awakens 8.3 2015
Now, suppose we want sort movies by their rating and names also. When we make a collection element comparable(by having it implement Comparable), we get only one chance to implement the compareTo() method. The solution is using Comparator.
Using Comparator
Unlike Comparable, Comparator is external to the element type we are comparing. It’s a separate class. We create multiple separate classes (that implement Comparator) to compare by different members.
Collections class has a second sort() method and it takes Comparator. The sort() method invokes the compare() to sort objects.
To compare movies by Rating, we need to do 3 things :
Create a class that implements Comparator (and thus the compare() method that does the work previously done by compareTo()).
Make an instance of the Comparator class.
Call the overloaded sort() method, giving it both the list and the instance of the class that implements Comparator.
//A Java program to demonstrate Comparator interface
import java.io.*;
import java.util.*;
// A class 'Movie' that implements Comparable
class Movie implements Comparable<Movie>
{
private double rating;
private String name;
private int year;
// Used to sort movies by year
public int compareTo(Movie m)
{
return this.year - m.year;
}
// Constructor
public Movie(String nm, double rt, int yr)
{
this.name = nm;
this.rating = rt;
this.year = yr;
}
// Getter methods for accessing private data
public double getRating() { return rating; }
public String getName() { return name; }
public int getYear() { return year; }
}
// Class to compare Movies by ratings
class RatingCompare implements Comparator<Movie>
{
public int compare(Movie m1, Movie m2)
{
if (m1.getRating() < m2.getRating()) return -1;
if (m1.getRating() > m2.getRating()) return 1;
else return 0;
}
}
// Class to compare Movies by name
class NameCompare implements Comparator<Movie>
{
public int compare(Movie m1, Movie m2)
{
return m1.getName().compareTo(m2.getName());
}
}
// Driver class
class Main
{
public static void main(String[] args)
{
ArrayList<Movie> list = new ArrayList<Movie>();
list.add(new Movie("Force Awakens", 8.3, 2015));
list.add(new Movie("Star Wars", 8.7, 1977));
list.add(new Movie("Empire Strikes Back", 8.8, 1980));
list.add(new Movie("Return of the Jedi", 8.4, 1983));
// Sort by rating : (1) Create an object of ratingCompare
// (2) Call Collections.sort
// (3) Print Sorted list
System.out.println("Sorted by rating");
RatingCompare ratingCompare = new RatingCompare();
Collections.sort(list, ratingCompare);
for (Movie movie: list)
System.out.println(movie.getRating() + " " +
movie.getName() + " " +
movie.getYear());
// Call overloaded sort method with RatingCompare
// (Same three steps as above)
System.out.println("\nSorted by name");
NameCompare nameCompare = new NameCompare();
Collections.sort(list, nameCompare);
for (Movie movie: list)
System.out.println(movie.getName() + " " +
movie.getRating() + " " +
movie.getYear());
// Uses Comparable to sort by year
System.out.println("\nSorted by year");
Collections.sort(list);
for (Movie movie: list)
System.out.println(movie.getYear() + " " +
movie.getRating() + " " +
movie.getName()+" ");
}
}
Output :
Sorted by rating
8.3 Force Awakens 2015
8.4 Return of the Jedi 1983
8.7 Star Wars 1977
8.8 Empire Strikes Back 1980
Sorted by name
Empire Strikes Back 8.8 1980
Force Awakens 8.3 2015
Return of the Jedi 8.4 1983
Star Wars 8.7 1977
Sorted by year
1977 8.7 Star Wars
1980 8.8 Empire Strikes Back
1983 8.4 Return of the Jedi
2015 8.3 Force Awakens
Comparable is meant for objects with natural ordering which means the object itself must know how it is to be ordered. For example Roll Numbers of students. Whereas, Comparator interface sorting is done through a separate class.
Logically, Comparable interface compares “this” reference with the object specified and Comparator in Java compares two different class objects provided.
If any class implements Comparable interface in Java then collection of that object either List or Array can be sorted automatically by using Collections.sort() or Arrays.sort() method and objects will be sorted based on there natural order defined by CompareTo method.
To summarize, if sorting of objects needs to be based on natural order then use Comparable whereas if you sorting needs to be done on attributes of different objects, then use Comparator in Java.
Producer-Consumer solution using threads in Java
In computing, the producer–consumer problem (also known as the bounded-buffer problem) is a classic example of a multi-process synchronization problem. The problem describes two processes, the producer and the consumer, which share a common, fixed-size buffer used as a queue.
The producer’s job is to generate data, put it into the buffer, and start again.
At the same time, the consumer is consuming the data (i.e. removing it from the buffer), one piece at a time.
Problem
To make sure that the producer won’t try to add data into the buffer if it’s full and that the consumer won’t try to remove data from an empty buffer.
Solution
The producer is to either go to sleep or discard data if the buffer is full. The next time the consumer removes an item from the buffer, it notifies the producer, who starts to fill the buffer again. In the same way, the consumer can go to sleep if it finds the buffer to be empty. The next time the producer puts data into the buffer, it wakes up the sleeping consumer.
An inadequate solution could result in a deadlock where both processes are waiting to be awakened.
Implementation of Producer Consumer Class
A LinkedList list – to store list of jobs in queue.
A Variable Capacity – to check for if the list is full or not
A mechanism to control the insertion and extraction from this list so that we do not insert into list if it is full or remove from it if it is empty.
Note: It is recommended to test the below program on a offline IDE as infinite loops and sleep method may lead to it time out on any online IDE
// Java program to implement solution of producer
// consumer problem.
import java.util.LinkedList;
public class Threadexample
{
public static void main(String[] args)
throws InterruptedException
{
// Object of a class that has both produce()
// and consume() methods
final PC pc = new PC();
// Create producer thread
Thread t1 = new Thread(new Runnable()
{
@Override
public void run()
{
try
{
pc.produce();
}
catch(InterruptedException e)
{
e.printStackTrace();
}
}
});
// Create consumer thread
Thread t2 = new Thread(new Runnable()
{
@Override
public void run()
{
try
{
pc.consume();
}
catch(InterruptedException e)
{
e.printStackTrace();
}
}
});
// Start both threads
t1.start();
t2.start();
// t1 finishes before t2
t1.join();
t2.join();
}
// This class has a list, producer (adds items to list
// and consumber (removes items).
public static class PC
{
// Create a list shared by producer and consumer
// Size of list is 2.
LinkedList<Integer> list = new LinkedList<>();
int capacity = 2;
// Function called by producer thread
public void produce() throws InterruptedException
{
int value = 0;
while (true)
{
synchronized (this)
{
// producer thread waits while list
// is full
while (list.size()==capacity)
wait();
System.out.println("Producer produced-"
+ value);
// to insert the jobs in the list
list.add(value++);
// notifies the consumer thread that
// now it can start consuming
notify();
// makes the working of program easier
// to understand
Thread.sleep(1000);
}
}
}
// Function called by consumer thread
public void consume() throws InterruptedException
{
while (true)
{
synchronized (this)
{
// consumer thread waits while list
// is empty
while (list.size()==0)
wait();
//to retrive the ifrst job in the list
int val = list.removeFirst();
System.out.println("Consumer consumed-"
+ val);
// Wake up producer thread
notify();
// and sleep
Thread.sleep(1000);
}
}
}
}
}
Output:
Producer produced-0
Producer produced-1
Consumer consumed-0
Consumer consumed-1
Producer produced-2
Important Points
In PC class (A class that has both produce and consume methods), a linked list of jobs and a capacity of the list is added to check that producer does not produce if the list is full.
In Producer class, the value is initialized as 0.
Also, we have an infinite outer loop to insert values in the list. Inside this loop, we have a synchronized block so that only a producer or a consumer thread runs at a time.
An inner loop is there before adding the jobs to list that checks if the job list is full, the producer thread gives up the intrinsic lock on PC and goes on the waiting state.
If the list is empty, the control passes to below the loop and it adds a value in the list.
In the Consumer class, we again have an infinite loop to extract a value from the list.
Inside, we also have an inner loop which checks if the list is empty.
If it is empty then we make the consumer thread give up the lock on PC and passes the control to producer thread for producing more jobs.
If the list is not empty, we go round the loop and removes an item from the list.
In both the methods, we use notify at the end of all statements. The reason is simple, once you have something in list, you can have the consumer thread consume it, or if you have consumed something, you can have the producer produce something.
sleep() at the end of both methods just make the output of program run in step wise manner and not display everything all at once so that you can see what actually is happening in the program.
Iterating Map Entries Efficiently
a.) Implementation using Iterator with Map.Entry
Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, Integer> pair = it.next();
sum += pair.getKey() + pair.getValue();
}
b.) Implementation using for with Map.Entry
for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
sum += pair.getKey() + pair.getValue();
}
c.) Implementation using Map.forEach (Java 8+)
map.forEach((k, v) -> sum[0] += k + v);
d.) Implementation using Map.keySet with for
for (Integer key : map.keySet()) {
sum += key + map.get(key);
}
e.) Implementation using Map.keySet with Iterator
Iterator<Integer> it = map.keySet().iterator();
while (it.hasNext()) {
Integer key = it.next();
sum += key + map.get(key);
}
f.) Implementation using for with Iterator and Map.Entry
for (Iterator<Map.Entry<Integer, Integer>> entries =
map.entrySet().iterator(); entries.hasNext(); ) {
Map.Entry<Integer, Integer> entry = entries.next();
sum += entry.getKey() + entry.getValue();
}
g.) Implementation using Stream.forEach (Java 8+)
map.entrySet().stream().forEach(e -> sum += e.getKey() + e.getValue());
h.) Implementation using Stream.forEach with Stream.parallel (Java 8+) 8.
map.entrySet()
.stream()
.parallel()
.forEach(e -> sum += e.getKey() + e.getValue());
LinkedHashMap
Key Points:
Is Hash table and Linked list implementation of the Map interface, with predictable iteration order. inherits HashMap class and implements the Map interface.
contains values based on the key only unique elements. may have one null key and multiple null values. same as HashMap instead maintains insertion order.
Methods:
void clear().
boolean containsKey(Object key).
Object get(Object key).
protected boolean removeEldestEntry(Map.Entry eldest)
Example:
public static void main(String arg[])
{
LinkedHashMap<String, String> lhm = new LinkedHashMap<String, String>();
lhm.put("Ramesh", "Intermediate");
lhm.put("Shiva", "B-Tech");
lhm.put("Santosh", "B-Com");
lhm.put("Asha", "Msc");
lhm.put("Raghu", "M-Tech");
Set set = lhm.entrySet();
Iterator i = set.iterator();
while (i.hasNext()) {
Map.Entry me = (Map.Entry) i.next();
System.out.println(me.getKey() + " : " + me.getValue());
}
System.out.println("The Key Contains : " + lhm.containsKey("Shiva"));
System.out.println("The value to the corresponding to key : " + lhm.get("Asha"));
}
Concepts of WeakHashmap
Key Points:
Implementation of Map.
stores only weak references to its keys.
Weak References : The objects that are referenced only by weak references are garbage collected eagerly; the GC
won’t wait until it needs memory in that case.
Difference between Hashmap and WeakHashMap:
If the Java memory manager no longer has a strong reference to the object specified as a key, then the entry in the
map will be removed in WeakHashMap.
TreeMap and TreeSet
TreeMap and TreeSet are basic Java collections added in Java 1.2. TreeMap is a mutable, ordered, Map implementation. Similarly, TreeSet is a mutable, ordered Set implementation.
TreeMap is implemented as a Red-Black tree, which provides O(log n) access times. TreeSet is implemented using a TreeMap with dummy values. Both collections are not thread-safe.
Queues and Deques
The usage of the PriorityQueue
PriorityQueue is a data structure. Like SortedSet , PriorityQueue sorts also its elements based on their priorities.
The elements, which have a higher priority, comes first. The type of the PriorityQueue should implement
comparable or comparator interface, whose methods decides the priorities of the elements of the data structure.
Deque
A Deque is a "double ended queue" which means that a elements can be added at the front or the tail of the queue.
The queue only can add elements to the tail of a queue.
The Deque inherits the Queue interface which means the regular methods remain, however the Deque interface
offers additional methods to be more flexible with a queue. The additional methods really speak for them self if you
know how a queue works, since those methods are intended to add more flexibility:
Method Brief description
getFirst() Gets the first item of the head of the queue without removing it.
getLast() Gets the first item of the tail of the queue without removing it.
What is a Stack?
In Java, Stacks are a LIFO (Last In, First Out) Data structure for objects. Push and pop method.
BlockingQueue
A BlockingQueue is an interface, which is a queue that blocks when you try to dequeue from it and the queue is
empty, or if you try to enqueue items to it and the queue is already full. A thread trying to dequeue from an empty
queue is blocked until some other thread inserts an item into the queue. A thread trying to enqueue an item in a
full queue is blocked until some other thread makes space in the queue, either by dequeuing one or more items or
clearing the queue completely.
BlockingQueue methods come in four forms, with different ways of handling operations that cannot be satisfied
immediately, but may be satisfied at some point in the future: one throws an exception, the second returns a
special value (either null or false, depending on the operation), the third blocks the current thread indefinitely until
the operation can succeed, and the fourth blocks for only a given maximum time limit before giving up.
OperationThrows ExceptionSpecial Value Blocks Times out
Insert add() offer(e) put(e) offer(e, time, unit)
Remove remove() poll() take() poll(time, unit)
Examine element() peek() N/A N/A
A BlockingQueue can be bounded or unbounded. A bounded BlockingQueue is one which is initialized with initial
LinkedList as a FIFO Queue
The java.util.LinkedList class, while implementing java.util.List is a general-purpose implementation of java.util.Queue interface too operating on a FIFO (First In, First Out) principle.
In the example below, with offer() method, the elements are inserted into the LinkedList . This insertion operation is called enqueue . In the while loop below, the elements are removed from the Queue based on FIFO. This operation is called dequeue.
Queue Interface
A Queue is a collection for holding elements prior to processing. Queues typically, but not necessarily, order elements in a FIFO (first-in-first-out) manner.
Head of the queue is the element that would be removed by a call to remove or poll. In a FIFO queue, all new elements are inserted at the tail of the queue.
Dequeue Interface
A Deque is linear collection that supports element insertion and removal at both ends.
The name deque is short for "double ended queue" and is usually pronounced "deck".
Most Deque implementations place no fixed limits on the number of elements they may contain, but this interface supports capacity-restricted deques as well as those with no fixed size limit.
The Deque interface is a richer abstract data type than both Stack and Queue because it implements both stacks and queues at same time
hashCode() method
When a Java class overrides the equals method, it should override the hashCode method as well. As defined in the method's contract: Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
If two objects are equal according to the equals(Object) method, then calling the hashCode
method on each of the two objects must produce the same integer result.
It is not required that if two objects are unequal according to the equals(Object) method, then
calling the hashCode method on each of the two objects must produce distinct integer results.
However, the programmer should be aware that producing distinct integer results for unequal
objects may improve the performance of hash tables.
Hash codes are used in hash implementations such as HashMap , HashTable , and HashSet . The result of the hashCode function determines the bucket in which an object will be put. These hash implementations are more efficient if the provided hashCode implementation is good. An important property of good hashCode implementation is that the distribution of the hashCode values is uniform. In other words, there is a small probability that numerous instances will be stored in the same bucket.
No comments:
Post a Comment