NFJS 3.1-Java Collections Power Techniques

This is the last day at the symposium and so far I found it very productive overall. During the breakfast session, me and Ryan mistakenly thought of Glenn as Randy Webb ... :) What is HE doing here??
Glenn Vanderburg is a Java consultant from the dallas area and has been presenting at NFJS for the 4 years now. This presentation was mostly about different tips and tricks that can be used while using the Collections API. The idea is that everyone knows about collections and uses them to some extent. Every project written in Java has some pretty crappy collections code, reinventing the wheel, etc. Collections came with 1.2 Java was one of the big things. Most of us never learned the API deeply and it has been updated and released since then in almost every big release. A lot of improvements have been slipped in 1.3 and 1.4 that people didn’t even learn or know about.

Java is not a formal design by contract language. You can not express in the commitment what the symmantics of these methods will be. Josh Block who wrote the Collections library, made a tremendous job in creating the doc and mentioning the commitments. But the problem is that none of us read the javadoc and wait on Eclipse to display the list of methods. It is a good idea to step back and learn some stuff about these as they are definitely a corner stone in Java development.

Collection's basic class hierarchy shows that a design around a series of core interfaces. A set of abstract classes to do custom implementation and followed by a set of concrete implementations. In the following, I will summarize the important points (tips) as mentioned by Glenn in his presentation and I think can be a good source for a tips and tricks session for the upcoming JTEs.

For vs. While: Advantages of the use for loop with the iterator. 1) constrains the scope of the iteration variable inside the loop 2) keeps the loop control at one place. A mantainance developer can put some code in between the iterator declaration and while loop and it slows down the code understanding/flow.

Encapsulation Problem: Whenever there is an instance variable that is a collection and has getters and setters, we usually end up with an encapsulation problem as some one else now owns the children and they can change these without your notice. Solutions that enable you to provide the children without exposing them to other people.

1. Provide a copy because most of the times the class you return it to will not modify it, but there is an overhead of copying.
2. Return an unmodifiable list, does not copy children but provides a wrapper that delegates the modifiable methods. So creating one new object and wrapping the old list with it, but it is inconvenient to return an unmodifiable list and there is no way the compiler will know, hence they will get a unmodifiable exception.
3. There is another option that is copyOnwriteArrayList method, that does not incur the copy overhead and if the caller calls a modification on that list, it creates a copy of the original list and then starts applying the modifications to that list. Convinience to the caller by providing them a full fledged list where they can also modify it.
4. Recommended: Jason Hunters JDOM library. If there is an element and you call getChild element, it returns the child element list but it does not give you a canned implementation of the list from the java interface. The API is designed for convenience and notifies the containing object everytime things are added and therefore encapsulation is not really violated. ‘Live List’ is proxy for the parent. (Read the Java doc for JDOM)

Deep vs. Shallow Copy: Deep vs. Shallow Copy in Java is a very difficuilt problem. There is no reliable way to implement a deep copy. Prefer collections to arrays, they are more flexible. The recipient of a collection can change its size etc. As an interface design issue, you may use arrays internally but if you can get away with it that is better although on the other hand arrays do have performance advantages.

Empty Collections vs. NULL: What do you do if there are no values to be returned, NEVER return an NULL, rather return an empty array. Java allows to create an array of size 0. In that case, the caller does not have to make a special case and they can only iterate over a size 0. A little array object is not a big deal in terms of size neither. There are some canned empty collections, that can be used and you can use only one of these throughout and don’t have to create your own. A use case is described: there are 15 variables that are all lists and originally they are empty and during the course of the program only a few of these variables will ever have any value. So in the constructor start up with one empty list and all 15 variables are intiallized to this empty list. In the add node method, create a new list and replace these lists that are changing. So a creation of 15 lists in the beginning can be easily avoided.

Initializing Collections Constants (Copy Constructor): Arrays.asList takes a list of things and makes use of the copy constructor. 'Arrays' is a class that has no instance methods. It is just a holder for public static utility methods. So can change Array to List which basically creates a thin little wrapper around the array and the only thing that you can not do is to expand or contract the size of the list because it is using the array underneath to store, the rest of the list functionality is there. When people need to make copy of a list, they create a new object iterate and then insert all the elements. The alternative can be cloning. If you look in the javadoc in collection. You can use the copy constructor. All the built in collections comply with this.

Collections have toString method that can be used as a log message to know what is in it. Arrays.deepToString works the way, if any of the objects inside the arrays is another array it recursively calls the ToString on those.

Set Functions: We have a set of objects and want to remove the candidates explicitly but lists and sets have a removeAll method and the candidate object will do all the work for you. Although it is not that efficient and it is the trivial implementation but it is definitely more expressive. retainall method means to keep everything that are in the passed collection and throw away the rest. So Unions, intersections and differences can be computed easily.

Comparators/Sorting/Manipulations: Comparators are often not thought of as a part of collection objects and they are often written if one is working with the collections API to sort collections. The typical comparator has no instance and is inherently thread safe. Don’t need the comparators for the descending case. You can use an inversecomparator which is a decorator to the comparator and passes in a Comparator and reverse the order. Java 1.5 has the method Collections.reverseOrder(comparator) and returns a new comparator that reverses the order.

Many people may already know, never use vectors or hashtables. They are very slow. They came with Java 1.0 and every method is synchronized. Their modern equivalents Arraylists and hashmaps respectively should be used.

There are some builtin algorithms in the collections classes. Sorting, the most important algorithm, and Java’s implementation is the quicksort which is pretty quick except for the worst case when the list is already sorted. What if we are adding stuff constantly to the list and want it sorted. The best way is to use binary search. There is a binary search already built in the collections implementation and its been there since the original collections framework. You can use, (-index)-1 for the index for the insertion point. Binary search tells you where to insert the element, if it is not there and there is negative number space for that. The reason we have another -1 is to differentiate with the case where it returns 0, which means the item was found and is at position 0.

What kind of list should be used? If you are mostly searching for stuff that is there, arraylist is best. But if there is a lot of insertion, LinkedList is better. As always, keep the concrete implementation out and keep the interface types everywhere because in that case it is easy to replace those. Why isn’t binary search a method in the Collection itself? There is no good answer to this. People expect to see List.Sort as they expect to see List.binarysearch therefore these things are not widely known although they are there for a while. Use TreeSet when you need a Set and sometimes you have to iterate over it in a sorted order. A TreeSet is an ordinary set with this extra auxiliary characteristic that it can be sorted easily. Use things they are meant for !!!

Other list manipulations are there.. Shuffle. The builtin Random method is not that great. But the Random library can be used to overcome this and is used in the default cryptographic libraries.

Adapters: An adapter wraps another object but changes the interface as compared to the decorator where the interface remains unchanged. Arrays.asList is the perfect example. Wraps an array and returns a List interface. A usecase for this: We want to display a set of values from a JDBC rowset returned from a query, and there is an API that is expecting a list that represent values in the columns. Use AbstractList( ) and have to override two methods size and the get method as well as Java’s 0-based indexing and JDBC’s 1-based indexing. A point of caution, Rowsets are not thread safe !! There are cases when adapting is not great of an idea because the contrasts don’t match up and there is not way to catch exceptions.

Implementing LRU (Last Recently Used Cache): A least recently used cache contains the most recently used values. A linkedHashmaps allows you to iterate in a specified order. So it can be used to build LRU caches and again JavaDoc is a great source for that. There is a removeEldestEntry method that can be extended and the slides can be referenced for that.

It is interesting to know how programmers spend their times in their brains? People will be astonished to find out that a lot of time is actually spent in thinking of the names for the things that are imaginary, or reinventing the wheel.. The JDK comes with the source code to the core libraries i.e., src.jar , which is the secret weapon of a Java developer. It is highly recommended to go have a look at it. If nothing else, just to get tips and tricks for development or to know if there is a bug or you are implementing things wrong. The Javadoc not only explains what the methods do but also how they do it so that they can be overridden intelligently.