Atomicity

What happens when we add one element of state to what was a stateless object? Suppose we want to add a "hit counter" that measures the number of requests processed. The obvious approach is to add a long field to the servlet and increment it on each request.

public class UnsafeCountingFactorizer implements Servlet {

private long count = 0;

public long getCount() {

return count;

}

public void service(ServletRequest req, ServletResponse resp) {

BigInteger i = extractFromRequest(req);

BigInteger[] factors = factor(i);

++count;

encodeIntoResponse(resp, factors);

}

}

Unfortunately, UnsafeCountingFactorizer is not thread-safe, even though it would work just fine in a single-threaded environment. It is susceptible to lost updates. While the increment operation, ++count, may look like a single action because of its compact syntax, it is not atomic. shows what can happen if two threads try to increment a counter simultaneously without synchronization. If the counter is initially 9, with some unlucky timing each thread could read the value, see that it is 9, add one to it, and each set the counter to 10. This is clearly not what is supposed to happen; an increment got lost along the way, and the hit counter is now permanently off by one. This is known is Race Condition.

UnsafeCountingFactorizer has several race conditions that make its results unreliable. A race condition occurs when the correctness of a computation depends on the relative timing or interleaving of multiple threads by the runtime; in other words, when getting the right answer relies on lucky timing.

Race Condition can be avoided by lazy initialization

public class LazyInitRace {

private ExpensiveObject instance = null;

public ExpensiveObject getInstance() {

if (instance ==null){

instance = new ExpensiveObject();

}

return instance;

}

}

LazyInitRace has race conditions that can undermine its correctness. Say that threads A and B execute getInstance at the same time. A sees that instance is null, and instantiates a new ExpensiveObject. B also checks if instance is null. Whether instance is null at this point depends unpredictably on timing, including the vagaries of scheduling and how long A takes to instantiate the ExpensiveObject and set the instance field. If instance is null when B examines it, the two callers to getInstance may receive two different results, even though getInstance is always supposed to return the same instance.

If the increment operation in UnsafeSequence were atomic, the race conditioncould not occur, and each execution of the increment operation would have the desired effect of incrementing the counter by exactly one. To ensure thread safety, check-then-act operations (like lazy initialization) and read-modify-write operations (like increment) must always be atomic. Atomic state can be created by the syncronization or the free atomic package in new Java 1.5

public class CountingFactorizer implements Servlet { 

    private final AtomicLong count = new AtomicLong(0); 

     public long getCount() {

       return count.get(); 

     } 

 public void service(ServletRequest req, ServletResponse resp) {                                

         BigInteger i = extractFromRequest(req);    

         BigInteger[] factors = factor(i);

         count.incrementAndGet();

         encodeIntoResponse(resp, factors);

     }

 } 

The java.util.concurrent.atomic package contains atomic variable classes for effecting atomic state transitions on numbers and object references. By replacing the long counter with an AtomicLong, we ensure that all actions that access the counter state are atomic. Because the state of the servlet is the state of the counter and the counter is thread-safe, our servlet is once again thread-safe.We were able to add a counter to our factoring servlet and maintain thread safety by using an existing thread-safe class to manage the counter state, AtomicLong. When a single element of state is added to a stateless class, the resulting class will be thread-safe if the state is entirely managed by a thread-safe object. But, as we'll see in the next section, going from one state variable to more than one is not necessarily as simple as going from zero to one.

Where practical, use existing thread-safe objects, like AtomicLong, to manage your class's state. It is simpler to reason about the possible states and state transitions for existing thread-safe objects than it is for arbitrary state variables, and this makes it easier to maintain and verify thread safety.

Difference between Encapsulation & Abstraction

This is a common OOPS related question that is being regularly asked in interviews and though it seems to have an easy answer to it, the actual difference can be a bit tricky. So I thought of just pointing out the main differences that i came to understand.

Encapsulation : In simple words , Encapsulation is data hiding. One of the major fundamentals of a good java design is that a class should have 'low coupling, high cohesion'. To have a low coupling, the calling class should be less dependent on the properties of the class or to say if the property changes it shouldn't change the depending functionalities. Encapsulation also prevents direct data manipulation by hiding the property and only which can be accessed by accessor methods. P.J. Plauger has a great analogy and definition of information hiding.”Information hiding is not the same as secrecy. The idea is not to prevent outsiders from knowing what you are doing inside a module. Rather, it is to encourage them not to depend on that knowledge. That leads to a kind of secondary coupling which is more pernicious than obvios dependency because it is less visible. You should encapsulate information to keep it private, not secret. (What you do in the bathroom is no secret, but it is private.)”

Abstraction : Abstraction is the interface which hides the inner functionality.Let’s compare Java and C++. We have a good example of abstraction. In C++, you have to deal with pointers and references a lot. You have to deal a lot of garbage collection. In essence, you have to work on a low level. (C and C++ in turn abstracted a lot of even lower level machine code.) In Java, those things are abstracted away. You just assume they exist. In essence, abstraction means that you are working on a higher level. You don’t care how pointers work in Java, you just assume that they work. You don’t have to concentrate on the lower level stuff, you work on higher level. Abstraction can be seen in java esp in the io package where how the string, or byte is being written in the output stream or read from the stream is not the developers concern

Loopy Problem - IV

Provide declarations for i and j that turn this loop into an infinite loop:

while (i <= j && j <= i && i != j) { 

} 

The <= operator is still antisymmetric on the set of primitive numeric values, but now it applies to operands of boxed numeric types as well. (The boxed numeric types are Byte, Character, Short, Integer, Long, Float, and Double.) The <= operator is not antisymmetric on operands of these types, because Java's equality operators (== and !=) perform reference identity comparison rather than value comparison when applied to object references.

To make this concrete, the following declarations give the expression (i <= j && j <= i && i != j) the value true, turning the loop into an infinite loop:

Integer i = new Integer(0);

Integer j = new Integer(0);

The first two subexpressions (i <= j and j <= i) perform unboxing conversions [JLS 5.1.8] on i and j and compare the resulting int values numerically. Both i and j represent 0, so both of these subexpressions evaluate to TRue. The third subexpression (i != j) performs an identity comparison on the object references i and j. The two variables refer to distinct objects, as each was initialized to a new Integer instance. Therefore, the third subexpression also evaluates to true, and the loop spins forever.

Loopy Problem - III

Provide a declaration for i that turns this loop into an infinite loop:

while (i != i + 0) {

}

The inescapable conclusion is that the type of i must be non-numeric, and therein lies the solution. The only non-numeric type for which the + operator is defined is String. The + operator is overloaded: For the String type, it performs not addition but string concatenation. If one operand in the concatenation is of some type other than String, that operand is converted to a string prior to concatenation

Loopy Problem - II

The following program counts the number of iterations of a loop and prints the count when the loop terminates. What does it print?

public class InTheLoop {

public static final int END = Integer.MAX_VALUE;

public static final int START = END - 100;

public static void main(String[] args) {

int count = 0;

for (int i = START; i <= END; i++)

count++;

System.out.println(count);

}

}

If you don't look at the program very carefully, you might think that it prints 100; after all, END is 100 more than START. If you look a bit more carefully, you will see that the program doesn't use the typical loop idiom. Most loops continue as long as the loop index is less than the end value, but this one continues as long as the index is less than or equal to the end value. So it prints 101, right? Well, no. If you ran the program, you found that it prints nothing at all. Worse, it keeps running until you kill it. It never gets a chance to print count, because it's stuck in an infinite loop.

The problem is that the loop continues as long as the loop index (i) is less than or equal to Integer.MAX_VALUE, but all int variables are always less than or equal to Integer.MAX_VALUE. It is, after all, defined to be the highest int value in existence. When i gets to Integer.MAX_VALUE and is incremented, it silently wraps around to Integer.MIN_VALUE.

If you need a loop that iterates near the boundaries of the int values, you are better off using a long variable as the loop index. Simply changing the type of the loop index from int to long solves the problem, causing the program to print 101 as expected:

for (long i = START; i <= END; i++)

More generally, the lesson here is that ints are not integers. Whenever you use an integral type, be aware of the boundary conditions. What happens if the value underflows or overflows? Often it is best to use a larger type. (The integral types are byte, char, short, int, and long.)

Loopy Problem - I

This program increments a variable repeatedly and then prints its value. What is it?

public class Increment {

public static void main(String[] args) {

int j = 0;

for (int i = 0; i < 100; i++)

j = j++;

System.out.println(j);

}

}

At first glance, the program might appear to print 100. After all, it does increment j 100 times. Perhaps surprisingly, it does not print 100 but 0. All that incrementing gets us nowhere. Why?

When placed after a variable, the ++ operator functions as the postfix increment operator [JLS 15.14.2]: The value of the expression j++ is the original value of j before it was incremented. Therefore, the preceding assignment first saves the value of j, then sets j to its value plus 1, and, finally, resets j back to its original value. In other words, the assignment is equivalent to this sequence of statements:

int tmp = j;

j = j + 1;

j = tmp;

The program repeats this process 100 times, after which the value of j is exactly what it was before the loop, or 0.

Fixing the program is as simple as removing the extraneous assignment from the loop, leaving:

for (int i = 0; i < 100; i++)

j++;

What is ArrayStoreException

An interesting situation occurs when you assign a subclass one-dimensional array variable's reference to a superclass one-dimensional array variable, because a one-dimensional array subtype is a kind of one-dimensional array supertype. If you then try to assign a superclass object reference to one of the subclass one-dimensional array's elements, anArrayStoreException object is thrown. The following code fragment demonstrates

AlarmClock [] ac = new AlarmClock [1];

Clock [] c = ac;

c [0] = new Clock ();

The compiler compiles the code fragment above because each line is legal. At runtime, however, c [0] = new Clock (); results in an ArrayStoreException. That exception occurs because we might try to access an AlarmClock-specific member via a reference to a Clock object. For example, suppose AlarmClock contains a public void soundAlarm() method, Clock lacks that method, and the code fragment above executes without throwing anArrayStoreException object. An attempt to execute ac [0].soundAlarm (); crashes the JVM because we attempt to execute that method in the context of a Clock object (which doesn't incorporate a soundAlarm() method).

ArrayList vs LinkedList

Source

The first thing to do while differentiating the two is to look at what interfaces these two implement. This might hint us at their purpose, as Sun usually bound purposes into interfaces.


// lang java
public class ArrayList
extends AbstractList
implements List, RandomAccess, Cloneable, Serializable

public class LinkedList
extends AbstractSequentialList
implements List, Queue, Cloneable, Serializable
We can ignore Cloneable and Serializable as all of the JCF implement those. It’s also quite obvious that both of them implement the List interface, as they need to provide list functionability (backwards iteration, sub listing, etc).

Now for the differences: ArrayList is implementing RandomAccess while LinkedList implementing Queue. You could already tell something about the usage of the two classes.

ArrayList

Now for some implementation notes. The ArrayList is actually encapsulating an actualy Array, an Object[]. When you instanciate ArrayList, an array is created, and when you add values into it, the array changes its size accordingly. This gives you strengths and weaknesses:

Fast Random Access
You can perform random access without fearing for performence. Calling get(int) will just access the underlying array.

Adding values might be slow When you don’t know the amount of values the array will contain when you create it, a lot of shifting is going to be done in the memory space when the ArrayList manipulates its internal array.
Slow manipulation When you’ll want to add a value randomly inside the array, between two already existing values, the array will have to start moving all the values one spot to the right in order to let that happen.
LinkedList

The LinkedList is implemented using nodes linked to each other. Each node contains a previous node link, next node link, and value, which contains the actual data. When new data is inserted, a node is inserted and the links of the surrounding nodes are updated accordingly. When one is removed, the same happens – The surrounding nodes are changing their links and the deleted node is garbage collected. This, as well, gives strengths and weaknesses:

Fast manipulation As you’d expect, adding and removing new data anywhere in the list is instantanious. Change two links, and you have a new value anywhere you want it.
No random access Even though the get(int) is still there, it now just iterates the list until it reaches the index you specified. It has some optimizations in order to do that, but that’s basically it.
Some Conclusions

ArrayList is very useful when a well defined set of data is needed in a List interface as opposed to an array. It can be dynamically changed, but try not to do so frequently throughout the life of the application. LinkedList is there for you to do just that: Manipulating it is very easy, and as long as its used for iteration purposes only and not for random accessing, it’s the best solution. Further, if you need random accessing from time to time, I suggest toArray for that specific moment.

Another point I didn’t raise here is the Queue issue. LinkedList implements extended abilities to the normal List interface which allows it to add and remove elements from its beginning and end. This makes the LinkedList perfect for Queue and Stack purposes – Although in Java 5 they already added a Stack class.