Java Collections, Skip Lists, and Google

While sometimes taken for granted the Java Collections API plays a large role in day to day Java software development. The API and related projects are not standing still however. Alex Miller recently took a look at the API changes for Java 6 including:

• A new double-ended queue interface called Deque (pronounced “deck”) and its concurrent counterpart BlockingDeque, with implementations like ArrayDeque and LinkedBlockingDeque.
• New and improved interfaces for sorted sets and maps called NavigableSet and NavigableMap with several prior implementations like TreeSet and TreeMap retrofitted to support them.
• New combined interfaces for concurrent and sorted interfaces: ConcurrentNavigableSet, ConcurrentNavigableMap . Plus two new concurrent sorted implementations called ConcurrentSkipListSet and ConcurrentSkipListMap.

One of the items that particularly peaked his interest was the SkipList which unlike many common CS data structures is a relatively new invention:

Invented in 1990 by William Pugh, a skip list is a probabilistic data structure, based on parallel linked lists, with efficiency comparable to a binary search tree (order O(log n) average time for most operations).

Google has also been hard at work in the realm of collections releasing a set of classes building on the standard Java Collections Framework. Although this is the alpha release, Google already using its suite in many of its services already in production such as GMail, Reader, and Blogger. Focusing on adding complexity and flexibility to the existing Java Collections Framework, Google adds a number of collections as well as utility classes that can make coding lives easier and code more readable.

Some of the most noteworthy collections are:

• BiMap - A Map that guarantees unique values, and supports an inverse view
• Multiset - A Collection that may contain duplicate values like a List, yet has order-independent equality like a Set. Often used to represent a histogram.
• Multimap - Similar to Map, but may contain duplicate keys. Has subtypes SetMultimap and ListMultimap providing more specific behavior.
• ClassToInstanceMap - A specialized Map whose keys are class literals and whose values are instances of those types.

Google has also included a number of utility classes that also work with these new collections. Some of these include:

• Comparators - Natural order, compound, null-friendly, ad-hoc . . .
• Iterators and Iterables - Element-based equality, cycle, concat, partition, filter with predicate, transform with function . . .
• Lists, Sets and Maps - A plethora of convenient factory methods and much more.
• PrimitiveArrays - "boxing"/"unboxing" of primitive arrays
• Object.equals and hashCode - Provide built-in null-handling.

Public Object has written up a number of examples using the Google Collection Library. The examples consist of the code snippets with Java Collections / Utilities being used and what the code looks like when using Google Collection Library. MulitMap and Objects.equal and hashCode provide a good feel for how the library can be used.

The Google Collection Library adheres to JDK interfaces, and is developed using the 1.5 JDK today, with JDK 1.6 under future consideration. A complete API and FAQ are also available.