Array vs ArrayList vs Vector

April 11, 2006 at 9:10 pm · Filed under Software Engineer in me, Server Side, Java

I was just browsing through some of my old notes about the ‘research’ I did sometime back on various data structures available in java for handling dynamic data sets. Thought may be this could be helpful to somebody else as well. There are situations in code where you need to handle the data that grows during run time. Usually, as much as possible I prefer arrays to handle any homogeneous collection of elements, as they are fast to execute, have implicit type check and easy to handle. But they fail in situations where the size of data is unknown at compile time. The obvious choices available with java are ArrayLists or Vectors. Or I should say ArrayLists or Vectors?

Most of the time, people use both these data structures interchangeably. Even the documentation say that the ‘only’ difference between an ArrayList and a Vector is just that Vectors are synchronized, and there is no much difference. Here is what I found out

Similarities between ArrayLists and Vectors

• Both can grow up during run time.
• Both implement List interface.
• With both, it is easier to remove or add elements at the end or start, but if you try to add or remove elements somewhere at middle of collection, they suffer performance wise. (Use LinkedLists if your programme need to do that a lot, but LinkList requires more memory and computation)

Now the differences

• The major difference, as the documentation says, is just that vectors are synchronized. Now what does that mean, this means that if more than one thread in your code is to use that data, you are in trouble with ArrayList as the data is asynchronous. Though there are ways by which you can make your ArrayLists synchronous, but by default they are not. The obvious downside with vectors is the additional computation to handle threads.
• The other difference is that with vectors, you can specify the incremental value, which is the amount with which the data structure will grow during the runtime. But with ArrayLists you have no option but to accept default that is the list will grow up 50% of original size everytime it needs additional space. It is advisable in both the cases to choose the initial size carefully.

My recommendation will be to use Arrays as much as possible, as they are fast and simple; of course you can not do that in cases where data set is completely dynamic. In these cases, go for ArrayList if your code is ‘threadsafe’ else Vectors or synchronous ArrayLists are suitable.

Java String performance

We all know that misuse of Strings degrade performance. But more often than not, we go back to look at our String code only when we are asked to optimize performance. This is a short blog on the performance aspect of Strings which would be good to keep in mind when coding.

So, the first thing to remember is that Strings are immutable- once you create them, you can’t change them. Oh yes, you might think you’re modifying them, but in reality, a new String is generated. Warning bells should be ringing in your head by now

If you are concatenating Strings over and over, lets say in a loop, then you know that because they are immutable, new Strings keep getting generated. The javac compiler internally uses a StringBuffer to do this- so for example, you have

 String itemList = "";

 itemList=itemList + items[i].description;

in a loop.

What happens is, within the loop, two objects are generated. One is a StringBuffer-

itemList=new StringBuffer().append(itemList).
          append(items[i].description).toString();

The other is the String that gets assigned to itemList via the toString().

A much better way out would be to create a StringBuffer outside the loop, and just append to it within the loop. More efficient.

Also beware of certain String operations like substring, trim or replace that actually work by creating new Strings. Consider using equivalent StringBuffer methods instead.

Another thing we do not think about is comparing Strings.
Comparing a String via equals() can be fairly expensive. It basically involves a character-by-character comparison, though every effort is made to avoid it. For example, if the lengths do not match, the character by character comparison is not done. But there are many cases where lengths are same and strings are long… in these cases, equals() can be time consuming.
Now we know that comparing Strings with == will not solve our problem because == compares the pointer references, and since both Strings are different instances, you will get a false, even if characters match.

Fortunately, there is a way out, if you know about the intern() method. According to the JavaDoc, intern() returns a canonical representation for the string object. A pool of strings, initially empty, is maintained privately by the class String. When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals(Object) method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned.

What this means is that if you have two identical Strings and intern them, only one instance is maintained. So then you can safely use == and have it compare the references and hence return a true.

Now the compiler automatically interns String constants for you. But you could explicitly intern() other Strings that will be compared extensively and repetitively, for example.

As with everything else in life, make sure that if you are interning, do it responsibly. If you intern every String in sight, you are in deep trouble. A pool of Strings will have maintenance costs and you cannot rely on interned Strings getting garbage collected. Hence, if you use it rashly, your performance will actually degrade and you will possibly run into memory issues.
It is worth knowing about intern though- after tuning other areas of your code, you could consider intern especially if you know for a fact that a particular operation will be more efficient by interning the String in question.