InfoQ

News

Java Collections, Skip Lists, and Google

Posted by Bryan Clauser and Scott Delap on Oct 09, 2007 10:12 PM

Community
Java
Topics
Data Access
Tags
Java SE
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.

1 comment

Reply

glad by Wang Jianzhi Posted Oct 10, 2007 9:01 AM
  1. Back to top

    glad

    Oct 10, 2007 9:01 AM by Wang Jianzhi

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

Exclusive Content

VMware Infrastructure 3 Book Excerpt and Author Interview

VMware Infrastructure 3: Advanced Technical Design Guide and Advanced Operations Guide provides a wealth of practical insights into setting up virtualization in todays corporate environments.

Architectures of extraordinarily large, self-sustaining systems

Can a system that is so large it cannot be comprehended be "designed" in a conventional sense? The foundations of computing are about to change. In this talk, Richard P. Gabriel explores why and how.

Using Ruby Fibers for Async I/O: NeverBlock and Revactor

Ruby 1.9's Fibers and non-blocking I/O are getting more attention - we talked to Mohammad A. Ali of the NeverBlock project and Tony Arcieri of the Revactor project.

Agile and Beyond - The Power of Aspirational Teams

Tim Mackinnon talks about the aspirations behind the Agile principles and practices, the desire to become efficient, to write quality code which does not end up being thrown away.

Concurrency: Past and Present

Brian Goetz discusses the difficulties of creating multithreaded programs correctly, incorrect synchronization, race conditions, deadlock, STM, concurrency, alternatives to threads, Erlang, Scala.

ActionScript 3 for Java Programmers

Often the hardest part of changing technologies is language syntax differences. This new article provides Java developers with a transition guide to Actionscript which forms the foundation of Flex.

Neal Ford On Programming Languages and Platforms

Neal Ford talks about having multiple languages running on one of the two major platforms: Java and .NET. He also presents the advantages offered by Ruby compared to static languages like Java or C#.

Future Directions for Agile

David Anderson talks about the history of Agile, the current status of it and his vision for the future. The role of Agile consists in finding ways to implement its principles.