BT

Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ

Topics

Choose your language

InfoQ Homepage News Java Collections, Skip Lists, and Google

Java Collections, Skip Lists, and Google

This item in japanese

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:

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.

Rate this Article

Adoption
Style

BT