Java Collections

1) How do I use an Iterator to go through a Collection?

Collection collection = ...;
Iterator iterator = collection.iterator ();
while (iterator.hasNext()) {
Object element = iterator.next ();
// Do something with element
}
}

2) How do I use a ListIterator to go through a List backwards?
List list = ...;
ListIterator iterator = list.listIterator(list.size());
while (iterator.hasPrevious()) {
Object element = iterator.previous();
// Process element
}

3) How do I use Enumeration to iterate through a collection?
Enumeration enum = ...;
while (enum.hasMoreElements()) {
Object element = iterator.nextElement();
// process element
}

4) How do I make an array larger?
You cannot directly make an array larger. You must make a new (larger) array and copy the original elements into it, usually with System.arraycopy(). If you find yourself frequently doing this, the Vector class does this automatically for you, as long as your arrays are not of primitive data types.

5) How do you store a primitive data type within a Vector or other collections class?
You need to wrap the primitive data type into one of the wrapper classes found in the java.lang package, like Integer, Float, or Double, as in:

Integer in = new Integer (5);

6) How do I use an array with the Collections Framework?
The Arrays.asList () method provides a fixed-length List view of an array, where changes to the List are stored in the original array. The Arrays class also provides additional support methods for sorting and searching an array.

7) Which is faster, synchronizing a HashMap or using a Hashtable for thread-safe access?
Because a synchronized HashMap requires an extra method call, a Hashtable is faster for synchronized access.

8) Which is the preferred collection class to use for storing database result sets?
When retrieving database results, the best collection implementation to use is the LinkedList. The benefits include:
Retains the original retrieval order
Has quick insertion at the head/tail
Doesn't have an internal size limitation like a Vector where when the size is exceeded a new internal structure is created (or you have to find out size beforehand to size properly)
Permits user-controlled synchronization unlike the pre-Collections Vector which is always synchronized
Basically:

ResultSet result = stmt.executeQuery("...");
List list = new LinkedList();
while(result.next()) {
list.add(result.getString("col"));
}

If there are multiple columns in the result set, you'll have to combine them into their own data structure for each row. Arrays work well for that as you know the size, though a custom class might be best so you can convert the contents to the proper type when extracting from databse, instead of later.

Why doesn't the Iterator interface extend the Enumeration interface?
If the Iterator interface extended the Enumeration interface, the Iterator interface would end up with five methods where two methods just called other methods in the interface. The designers of the framework wanted to get rid of the cumbersome Enumeration method names so had the Iterator interface stand on its own with new shorter method names.

9) How do I print a Collection?
The Collection Framework implementation classes override the toString() method to print out all the elements of the collection. If you create your own custom implementation, as long as your class is a subclass of AbstractMap or AbstractCollection you'll inherit this behavior. (Keep in mind that AbstractList and AbstractSet subclass AbstractCollection.)

10) How do I synchronize a collection?
With the Collections Framework, the new implementations are all unsynchronized by default. If you need synchronized access, you must synchronize things yourself. The Collections class offers a wrapper method for each of the six core collection interfaces that add synchronization to an arbitrary collections implementation. To ensure thread-safety, direct access to the original backing collection must be avoided.
For example, the following will synchronize an arbitrary List and lose the original reference so you can't access it directly:

List list = ...;
list = Collections.synchronizedList(list);

11) How do I get the length of an array?
To avoid getting an ArrayIndexOutOfBoundsException, you can check for the array length from either the length instance variable or using reflection and calling java.lang.reflect.Array.getLength(), passing the array as an argument to the method.
int length = args.length;
// or
int length2 = Array.getLength(args);

12) How do I sort an array?
The Arrays class in java.util provides a series of sort () methods for sorting arrays. If the array is an array of primitives or an array of a class that implements Comparable then you can just call the method directly:

Arrays.sort(theArray);

If, however, it is an array of objects that don't implement the Comparable interface then you need to provide a custom Comparator to help you sort the elements in the array.

Arrays.sort (theArray, theComparator);

13) What's the fastest way to traverse all the elements of a Vector?
If speed is of the essence, do not use a Vector. Instead, use an ArrayList. All accesses to a Vector are synchronized, whether you need it or not. If you know you aren’t accessing the structure from multiple threads, the ArrayList will be much faster.

With that said, what about if you need to stay with a Vector? There are at least four ways to traverse through all the elements of a Vector:

Using a for loop and accessing each element with elementAt(index) or get(index)
Using an Emumeration
Using an Iterator
Using an Enumeration/Iterator, but relying on an exception to catch ending
Of the four, there are neglible differences in performance. While looping through to a specific index is a little faster, you lose the flexibility of changing to another data structure at a later time. With the Enumeration / Iterator approach, there is the added cost to create the Enumeration/Iterator to walk through. With the exception approach, you are relying on NoSuchElementException to be thrown to catch the ending of the walk through. While creating the exception takes time, this approach avoids the repeated test of hasMoreElement(). As the structure gets larger, avoiding the test condition can save lots of time.

14) How does a Hashtable internally maintain the key-value pairs?
The Hashtable class uses an internal (private) class named Entry to hold the key-value pairs. All entries of the Hashtable are stored in an array of Entry objects with the hash value of the key serving as the index. If two or more different keys have the same hash value these entries are stored as a linked list under the same index.

15) How do I look through each element of a HashMap?
To go through all the elements of a HashMap, or any class that implements the Map interface, call the entrySet() or keySet() methods than loop through what is returned. The entrySet() returns a group of Map.Entry elements, whereas the keySet() method just returns a Set of key elements. If you then want what the key refers to, you'd have to look them up.
Once you have a Set to work with, you would then use an Iterator to go through all its elements. The following demonstrates:


Map map = some hash map
Set set = map.keySet();
Iterator it = set.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}

16) How do I create a read-only collection?
The Collections class has six methods to help out here:
unmodifiableCollection (Collection c)
unmodifiableList (List list)
unmodifiableMap (Map m)
UnmodifiableSet (Set s)
unmodifiableSortedMap (SortedMap m)
unmodifiableSortedSet (SortedSet s)
If you then get an Iterator from one of these unmodifiable collections, when you call remove() it will throw an UnsupportedOperationException

17) How can I process through the keys of a Hashtable in sorted order?
In order to get all the keys for a Hashtable, you use the keys() method to get an Enumeration or the keySet() method to get a Set. If you are using Java 2, and can use the collections framework, what you should do is get the key set of the Hashtable and create a TreeSet from it. You can then get an iterator() from the created TreeSet that will have the keys in order. If you can't use the collections framework, you'll have the sort the Enumeration you get back from keys() yourself.

18) Which collections in Java are synchronized and which aren't?
The original collection classes in Java are all synchronized: Vector and Hashtable, along with their subclasses Stack and Properties. Those classes introduced with the Java 2 Collections Framework are all NOT synchronized by default, the sets, lists, and maps. If you need to synchronize those, see How do I synchronize a collection?.

19) What are the differences between ArrayList and LinkedList?
An ArrayList is a List implementation backed by a Java array, similar to the Vector class. As the number of elements in the collection increases, the internal array grows to fit them. If there are lots of growth periods, performance degrades as the old array needs to be copied into the new array. However, random access is very quick as it uses an array index to access.
With a LinkedList, the List implementation is backed by a doubly linked list data structure, allowing easy inserts/deletions anywhere in the structure, but really slow random accesses as the access must start at an end to get to the specific position.

20) What is the difference between a singly linked list and doubly linked list?
A singly linked list is one that has only a pointer/reference to the next element in the list. A doubley linked list has both a previous and next pointer/reference.

21) What is a polymorphic algorithm?
In general, an algorithm is called polymorphic if it can achieve the same functionality using different data structures. For example, if the same sorting or searching algorithm could be used with different types of containers, such as vectors, lists, maps, etc., then that algorithm would be called polymorphic. As a case in point, the generic algorithms of the STL library in C++ are polymorphic because they can be used for different container classes.
In the context of Java collections, the polymorphic algorithms are all supplied by the various static methods of the java.util.Collections class. Consider, for example, the method sort( List list ). This method is capable of sorting any collection that has implemented the List interface, and that includes containers of types ArrayList, LinkedList, Vector, etc.
22) How do you sort the elements of a vector?
Since the Vector class implements the List interface, you can call the Collections.sort() method to sort the elements in place. You can also manually insert elements into a Vector to keep the vector sorted. Of course, if keeping sorted access is such a big deal, you should consider using a different, more appropriate data structure like a TreeSet.
For 1.1 Java users, you'll need to sort the elements yourself. There is no built-in support for this. A better option might be to sort the elements as you insert each element.

23) How do you control growth of vectors when their internal arrays are full?
The vector constructor can include either an initial capacity or a capacity and growth increment. When not specified, the initial size of the vector is 10 and growth will double when necessary. Otherwise, initialize size and growth will grow when needed as specified by the arguments to the constructor.
If the argument to the constructor is a collection, the initial size of the internal structure is 10% larger than the collection. Since there is no second argument to control growth, the capacity will double when necessary.

24) Why can't I add a collection to itself?
This will cause a stack overflow exception to be generated on calls to methods like toString() and hashCode(), which recursively call the method on the elements of the collection.

25) What is a weak reference and what are they used for?
Normally the Java garbage collector plays safe. It will only free up the memory used by an object when that object can no longer be accessed by the program. Once an object become impossible to reach it is eligible for collection, and eventually its memory will be reclaimed.
This eliminates one of the most common programming errors in some other languages (like C++), where code accidentally tries to access an object that has been freed. Unfortunately it can lead to another problem, where you leave open a potential access route to an object that you don't need any more. Memory fills up, and the program slows down or reports an "Out of Memory" error.

To avoid this, you can be very careful to close off access paths to an object once you have finished using it. Java 2 introduces another alternative, the weak reference. Weak references provide access to an object without preventing it from being freed. When you use a weak reference you have to accept that the object referred to may have disappeared, which results in the reference being automatically set to null. On the other hand, the weak reference will not hold the object in memory once it is inaccessible via normal references (or via "soft" references - see below). Weak references are not appropriate in all circumstances, but sometimes they can make code easier to write and understand.

The most common use of weak references is indirect - they are used internally by the WeakHashMap class. Like HashMap, WeakHashMap associates key objects with values. However, once the key object becomes inaccessible via stronger references it becomes eligible for garbage collection. When it is freed, the map entry magically disappears. The assumption here is that if you are not using the key anywhere other than in the map you will have no need to look it up, so it should be freed.

Other specialist references are soft references (which inhibit collection until memory runs short), and phantom references (used for cleanup when objects are freed).

For more detailed (and precise) information, see the java.lang.ref API docs, and also the article Reference Objects and Garbage Collection at the Sun website.

26) How does ArrayList increase its capacity?
Unlike Vector where you can specify a capacity increment, ArrayList doesn't support this. Instead, ArrayList will increase capacity by about a half when it runs out of space. The refernece implementation uses the forumla:
newCapacity = (oldCapacity * 3)/2 + 1
though, this isn't part of the class definition so others can implement it differently.

27) What are the differences between HashMap and Hashtable?
Both provide key-value access to data. The Hashtable is one of the original collection classes in Java. HashMap is part of the new Collections Framework, added with Java 2, v1.2.
The key difference between the two is that access to the Hashtable is synchronized on the table while access to the HashMap isn't. You can add it, but it isn't there by default.

Another difference is that iterator in the HashMap is fail-safe while the enumerator for the Hashtable isn't. If you change the map while iterating, you'll know.

And, a third difference is that HashMap permits null values in it, while Hashtable doesn't.

For new code, I would tend to always use HashMap.

28) What are the differences between Vector and ArrayList? Which is best to use?
Vector and ArrayList are very similar. Both of them represent a 'growable array', where you access to the elements in it through an index.

ArrayList it's part of the Java Collection Framework, and has been added with version 1.2, while Vector it's an object that is present since the first version of the JDK. Vector, anyway, has been retrofitted to implement the List interface.

The main difference is that Vector it's a synchronized object, while ArrayList it's not.

While the iterator that are returned by both classes are fail-fast (they cleanly thrown a ConcurrentModificationException when the orignal object has been modified), the Enumeration returned by Vector are not.

Unless you have strong reason to use a Vector, the suggestion is to use the ArrayList.
I/O

No comments: