InfoQ

InfoQ

News

My Bookmarks

Login or Register to enable bookmarks for unlimited time.

The content has been bookmarked!

There was an error bookmarking this content! Please retry.

Java Collections, Skip Lists, and Google

Posted by Bryan Clauser and Scott Delap on Oct 09, 2007

Sections
Architecture & Design,
Development,
Operations & Infrastructure
Topics
Data Access ,
Java
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.

glad by Jianzhi Wang Posted
  1. Back to top

    glad

    by Jianzhi Wang

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

Educational Content

New-age Transactional Systems - Not Your Grandpa's OLTP

John Hugg discusses high volume transaction processing applications with high and low frequency profiles, and how VoltDB can be used for that purpose.

Cool Code

Kevlin Henney examines code samples to see what can be learned from them starting from the premise that one won’t write great code unless he knows how to read it.

Collaboration: At the Extremities of Extreme

Jason Ayers share the observations he made watching a team of developers collaborating in real time on the same code base, pushing XP, pair programming and continuous integration to their extremes.

Yesod Web Framework

Michael Snoyman presents Yesod, a web framework written in Haskell and containing a web server, templating, ORM, libraries (templating, gravatar, etc.).

Transactions without Transactions

Richard Kreuter and Kyle Banker on how to avoid classical RDBMS transactional systems by using compensation mechanisms, transactional messaging or transactional procedures.

Attila Szegedi on JVM and GC Performance Tuning at Twitter

Attila Szegedi talks about performance tuning Java and Scala programs at Twitter: how to approach GC problems, the importance of asynchronous I/O, when to use MySQL/Cassandra/Redis, and much more.

10 tips on how to prevent business value risk

One category of risk that project teams need to ensure they address is business value failure – delivering a product that fails to provide value for the business investor.

Interview: Software Systems Architecture: Working With Stakeholders Using Viewpoints and Perspectives

InfoQ spoke to the authors of Software Systems Architecture on a couple of new topics, the System Context viewpoint and Agile, which have been added to the second edition.