BT

Your opinion matters! Please fill in the InfoQ Survey!

Java Collections, Skip Lists, and Google

| by Bryan Clauser Follow 0 Followers , Scott Delap Follow 0 Followers on Oct 09, 2007. Estimated reading time: 2 minutes |
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 Stage
Style

Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Tell us what you think

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

glad by Jianzhi Wang

Glad to find some improvements in j6,thought most of us still operate in j5.

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

1 Discuss

Login to InfoQ to interact with what matters most to you.


Recover your password...

Follow

Follow your favorite topics and editors

Quick overview of most important highlights in the industry and on the site.

Like

More signal, less noise

Build your own feed by choosing topics you want to read about and editors you want to hear from.

Notifications

Stay up-to-date

Set up your notifications and don't miss out on content that matters to you

BT