Showing posts with label collections. Show all posts
Showing posts with label collections. Show all posts

Friday, 15 June 2012

Hacking apache collections

Once you get the jar added to your project, you can start cruising the javadoc and seeing what you can make of the Apache collections classes (and interfaces, mind you).

This will take you a few steps beyond the humble plateau of plain-vanilla Maps and Lists, by introducing variations of Sets and different types of Maps, designed for special scenarios. But before you ascend to the Java data structure stratosphere, you might want to recap your knowledge on the basic interfaces in the Collections framework, such as the Map interface, and the List interface. An interesting point of comparison, is that while the Map interface has no superinterfaces, the List interface is superinterface'd by the Collection interface and the Iterable interface by extension, since Collections are by necessity Iterable.

Perhaps, you are interested in the numerous implementations of Bags (sets that allow repeat elements e.g. two pairs of socks in a gym bag), and wander over to TreeBag or HashBag (now deprecated). Also fascinating are the various implementations of the BidiMap interface such as TreeBidiMap, that allows lookup from keys to values and values to keys- with equal efficiency. It is more storage efficient than using two separate TreeMaps, although the DualTreeBidiMap does use this approach.

Remember always the distinction between interfaces and classes, do not try to create an object of type Bag by instantiating Bag, but rather create an instance of TreeBag (but not HashBag) i.e. instantiate the implementing classes (but not deprecated ones!)

Tuesday, 28 April 2009

The Stronghold of Mark Reinhold - Java Collection Classes

Yoda may be a master Jedi, but Mark Reinhold is the primary implementor behind many of the Java collection classes. He has also been involved in the area of NIO high-performance APIs.

A recent interesting class of Mark's I stumbled upon recently (using jdb and typing 'classes' to pull a list of the currently known classes) is the PreHashedMap.java collection class in "package sun.util". This is build on top of java.util.AbstractMap (a skeletal implementation of the Map interface) and has been in orbit since JDK 1.5.

PreHashedMap use memoization to store precomputed hashes. Hashes are computed as the hashCode of an Object, right shifted by a fixed offset and binary AND'ed with a mask. The mask and offset are configured at startup in the constructor of the PreHashedMap.