fastutil extends the
Collections Framework by providing type-specific maps, sets, lists
and queues with a small memory footprint and fast access and
insertion; provides also big (64-bit) arrays, sets and lists, and
fast, practical I/O classes for binary and text files. It is
free software distributed under the Apache License 2.0.
It requires Java 6 or newer.
The classes implement their standard counterpart interface (e.g.,
Map for maps) and can be plugged into existing code. Moreover,
they provide additional features (such as bidirectional iterators) that are
not available in the standard classes.
Besides objects and primitive types,
fastutil classes provide support
for references, that is, objects that are compared using the equality
operator rather than the
The sources are generated using a C preprocessor, starting from a set of
driver files. You can peek at the javadoc-generated documentation. In particular, the overview
explains the design choices used in
Big data structures
fastutil 6, a new set of classes makes it possible
to handle very large collections: in particular, collections whose size exceeds
231. Big arrays
are arrays-of-arrays handled by a wealth of static methods that act on them
as if they were monodimensional arrays with 64-bit indices, and
big lists provide 64-bit list access.
The size of a hash big set
is limited only by the amount of core memory.
The usual methods from
java.util.Arrays and similar classes have
been extended to big arrays: have a look at the Javadoc documentation of
to get an idea of the generic and type-specific methods available.
The release 5 of
fastutil needs Java 5, and
marks a revolution in the way the
classes are organized. Besides full support for generics, which can help
with object-based classes (but is rather irrelevant in type-specific classes),
fastutil is now strongly based on what is probably the less hyped
and most important feature of Java 5: covariant return-type overriding.
x() returning an object of type
T can now
be overriden by a method returning an object of type
U is a subclass of (or implements)
Covariant return-type overriding has always been supported by the JVM,
but was inaccessible at the syntax level. In Java 5 this irritating limitation
has been lifted, opening a new world of clarity and orthogonality in organizing
collection classes. In particular, interface strengthening makes it
possible to use all features of
fastutil classes without type
casting: for instance,
is strengthened, w.r.t.
Set.iterator(), so that it
IntIterator instead of a
Iterator. Although type casting was previosuly used to simulate this
feature, it made using the hundreds of classes in
difficult and error-prone, as every type cast had to be checked against the documentation.
Another advantage of covariant return-type overriding is that implementations
can declare to return more specific (usually, more powerful) types than those
specified by their interface. For instance,
IntAVLTreeSet.iterator() returns actually
IntSortedSet.iterator() is specified as returning
You can grab
Otherwise, you just have to install the .jar file coming with the distribution.
Note that the jar file is huge, due to the large number of classes: if
you plan to ship your own jar with some
fastutil classes included, you should
look at AutoJar.
History and Motivation
fastutil came up as a necessity during the development
as we needed to manage structures with dozens of millions of items
very efficiently. The same reasons led to the development of the high-performance classes of dsiutils and