GNU Trove

Package gnu.trove

GNU Trove: High performance collections for Java.

See:
          Description

Interface Summary
TDoubleDoubleProcedure Interface for procedures that take two parameters of type double and double.
TDoubleFloatProcedure Interface for procedures that take two parameters of type double and float.
TDoubleFunction Interface for functions that accept and return one double primitive.
TDoubleHashingStrategy Interface to support pluggable hashing strategies in maps and sets.
TDoubleIntProcedure Interface for procedures that take two parameters of type double and int.
TDoubleLongProcedure Interface for procedures that take two parameters of type double and long.
TDoubleObjectProcedure Interface for procedures that take two parameters of type double and Object.
TDoubleProcedure Interface for procedures with one double paramater.
TFloatDoubleProcedure Interface for procedures that take two parameters of type float and double.
TFloatFloatProcedure Interface for procedures that take two parameters of type float and float.
TFloatFunction Interface for functions that accept and return one float primitive.
TFloatHashingStrategy Interface to support pluggable hashing strategies in maps and sets.
TFloatIntProcedure Interface for procedures that take two parameters of type float and int.
TFloatLongProcedure Interface for procedures that take two parameters of type float and long.
TFloatObjectProcedure Interface for procedures that take two parameters of type float and Object.
TFloatProcedure Interface for procedures with one float paramater.
TIntDoubleProcedure Interface for procedures that take two parameters of type int and double.
TIntFloatProcedure Interface for procedures that take two parameters of type int and float.
TIntFunction Interface for functions that accept and return one int primitive.
TIntHashingStrategy Interface to support pluggable hashing strategies in maps and sets.
TIntIntProcedure Interface for procedures that take two parameters of type int and int.
TIntLongProcedure Interface for procedures that take two parameters of type int and long.
TIntObjectProcedure Interface for procedures that take two parameters of type int and Object.
TIntProcedure Interface for procedures with one int paramater.
TLinkable Interface for Objects which can be inserted into a TLinkedList.
TLongDoubleProcedure Interface for procedures that take two parameters of type long and double.
TLongFloatProcedure Interface for procedures that take two parameters of type long and float.
TLongFunction Interface for functions that accept and return one long primitive.
TLongHashingStrategy Interface to support pluggable hashing strategies in maps and sets.
TLongIntProcedure Interface for procedures that take two parameters of type long and int.
TLongLongProcedure Interface for procedures that take two parameters of type long and long.
TLongObjectProcedure Interface for procedures that take two parameters of type long and Object.
TLongProcedure Interface for procedures with one long paramater.
TObjectDoubleProcedure Interface for procedures that take two parameters of type Object and double.
TObjectFloatProcedure Interface for procedures that take two parameters of type Object and float.
TObjectFunction Interface for functions that accept and return one Object reference.
TObjectHashingStrategy Interface to support pluggable hashing strategies in maps and sets.
TObjectIntProcedure Interface for procedures that take two parameters of type Object and int.
TObjectLongProcedure Interface for procedures that take two parameters of type Object and long.
TObjectObjectProcedure Interface for procedures that take two Object parameters.
TObjectProcedure Interface for procedures with one Object paramater.
 

Class Summary
HashFunctions Provides various hash functions.
PrimeFinder Used to keep hash table capacities prime numbers.
TDoubleArrayList A resizable, array-backed list of double primitives.
TDoubleDoubleHashMap An open addressed Map implementation for double keys and double values.
TDoubleDoubleIterator Iterator for maps of type double and double.
TDoubleFloatHashMap An open addressed Map implementation for double keys and float values.
TDoubleFloatIterator Iterator for maps of type double and float.
TDoubleHash An open addressed hashing implementation for double primitives.
TDoubleHashSet An open addressed set implementation for double primitives.
TDoubleIntHashMap An open addressed Map implementation for double keys and int values.
TDoubleIntIterator Iterator for maps of type double and int.
TDoubleIterator Iterator for double collections.
TDoubleLongHashMap An open addressed Map implementation for double keys and long values.
TDoubleLongIterator Iterator for maps of type double and long.
TDoubleObjectHashMap An open addressed Map implementation for double keys and Object values.
TDoubleObjectIterator Iterator for maps of type double and Object.
TFloatArrayList A resizable, array-backed list of float primitives.
TFloatDoubleHashMap An open addressed Map implementation for float keys and double values.
TFloatDoubleIterator Iterator for maps of type float and double.
TFloatFloatHashMap An open addressed Map implementation for float keys and float values.
TFloatFloatIterator Iterator for maps of type float and float.
TFloatHash An open addressed hashing implementation for float primitives.
TFloatHashSet An open addressed set implementation for float primitives.
TFloatIntHashMap An open addressed Map implementation for float keys and int values.
TFloatIntIterator Iterator for maps of type float and int.
TFloatIterator Iterator for float collections.
TFloatLongHashMap An open addressed Map implementation for float keys and long values.
TFloatLongIterator Iterator for maps of type float and long.
TFloatObjectHashMap An open addressed Map implementation for float keys and Object values.
TFloatObjectIterator Iterator for maps of type float and Object.
THash Base class for hashtables that use open addressing to resolve collisions.
THashMap An implementation of the Map interface which uses an open addressed hash table to store its contents.
THashSet An implementation of the Set interface that uses an open-addressed hash table to store its contents.
TIntArrayList A resizable, array-backed list of int primitives.
TIntDoubleHashMap An open addressed Map implementation for int keys and double values.
TIntDoubleIterator Iterator for maps of type int and double.
TIntFloatHashMap An open addressed Map implementation for int keys and float values.
TIntFloatIterator Iterator for maps of type int and float.
TIntHash An open addressed hashing implementation for int primitives.
TIntHashSet An open addressed set implementation for int primitives.
TIntIntHashMap An open addressed Map implementation for int keys and int values.
TIntIntIterator Iterator for maps of type int and int.
TIntIterator Iterator for int collections.
TIntLongHashMap An open addressed Map implementation for int keys and long values.
TIntLongIterator Iterator for maps of type int and long.
TIntObjectHashMap An open addressed Map implementation for int keys and Object values.
TIntObjectIterator Iterator for maps of type int and Object.
TIntStack A stack of int primitives, backed by a TIntArrayList.
TLinkableAdaptor Adapter for TLinkable interface which implements the interface and can therefore be extended trivially to create TLinkable objects without having to implement the obvious.
TLinkedList A LinkedList implementation which holds instances of type TLinkable.
TLongArrayList A resizable, array-backed list of long primitives.
TLongDoubleHashMap An open addressed Map implementation for long keys and double values.
TLongDoubleIterator Iterator for maps of type long and double.
TLongFloatHashMap An open addressed Map implementation for long keys and float values.
TLongFloatIterator Iterator for maps of type long and float.
TLongHash An open addressed hashing implementation for long primitives.
TLongHashSet An open addressed set implementation for long primitives.
TLongIntHashMap An open addressed Map implementation for long keys and int values.
TLongIntIterator Iterator for maps of type long and int.
TLongIterator Iterator for long collections.
TLongLongHashMap An open addressed Map implementation for long keys and long values.
TLongLongIterator Iterator for maps of type long and long.
TLongObjectHashMap An open addressed Map implementation for long keys and Object values.
TLongObjectIterator Iterator for maps of type long and Object.
TObjectDoubleHashMap An open addressed Map implementation for Object keys and double values.
TObjectDoubleIterator Iterator for maps of type Object and double.
TObjectFloatHashMap An open addressed Map implementation for Object keys and float values.
TObjectFloatIterator Iterator for maps of type Object and float.
TObjectHash An open addressed hashing implementation for Object types.
TObjectIdentityHashingStrategy This object hashing strategy uses the System.identityHashCode method to provide identity hash codes.
TObjectIntHashMap An open addressed Map implementation for Object keys and int values.
TObjectIntIterator Iterator for maps of type Object and int.
TObjectLongHashMap An open addressed Map implementation for Object keys and long values.
TObjectLongIterator Iterator for maps of type Object and long.
TPrimitiveHash The base class for hashtables of primitive values.
 

Package gnu.trove Description

GNU Trove: High performance collections for Java.

Objectives

The GNU Trove library has two objectives:

  1. Provide "free" (as in "free speech" and "free beer"), fast, lightweight implementations of the java.util Collections API. These implementations are designed to be pluggable replacements for their JDK equivalents.
  2. Whenever possible, provide the same collections support for primitive types. This gap in the JDK is often addressed by using the "wrapper" classes (java.lang.Integer, java.lang.Float, etc.) with Object-based collections. For most applications, however, collections which store primitives directly will require less space and yield significant performance gains.

Hashtable techniques

The Trove maps/sets use open addressing instead of the chaining approach taken by the JDK hashtables. This eliminates the need to create Map.Entry wrappper objects for every item in a table and so reduces the O (big-oh) in the performance of the hashtable algorithm. The size of the tables used in Trove's maps/sets is always a prime number, improving the probability of an optimal distribution of entries across the table, and so reducing the the likelihood of performance-degrading collisions. Trove sets are not backed by maps, and so using a THashSet does not result in the allocation of an unused "values" array.

Hashing strategies

Trove's maps/sets support the use of custom hashing strategies, allowing you to tune collections based on characteristics of the input data. This feature also allows you to define hash functions when it is not feasible to override Object.hashCode(). For example, the java.lang.String class is final, and its implementation of hashCode() takes O(n) time to complete. In some applications, however, it may be possible for a custom hashing function to save time by skipping portions of the string that are invariant.

Using java.util.HashMap, it is not possible to use Java language arrays as keys. For example, this code:

    char[] foo, bar;
    foo = new char[] {'a','b','c'};
    bar = new char[] {'a','b','c'};
    System.out.println(foo.hashCode() == bar.hashCode() ? "equal" : "not equal");
    System.out.println(foo.equals(bar) ? "equal" : "not equal");
    
produces this output:
    not equal
    not equal
    
And so an entry stored in a java.util.HashMap with foo as a key could not be retrieved with bar, since there is no way to override hashCode() or equals() on language array objects.

In a gnu.trove.THashMap, however, you can implement a TObjectHashingStrategy to enable hashing on arrays:

    class CharArrayStrategy implements TObjectHashingStrategy {
        public int computeHashCode(Object o) {
            char[] c = (char[])o;
            // use the shift-add-xor class of string hashing functions
            // cf. Ramakrishna and Zobel, "Performance in Practice of String Hashing Functions"
            int h = 31; // seed chosen at random
            for (int i = 0; i < c.length; i++) { // could skip invariants
                h = h ^ ((h << 5) + (h >> 2) + c[i]); // L=5, R=2 works well for ASCII input
            }
            return h;
        }

        public boolean equals(Object o1, Object o2) {
            char[] c1 = (char[])o1;
            char[] c2 = (char[])o2;
            if (c1.length != c2.length) { // could drop this check for fixed-length keys
                return false;
            }
            for (int i = 0, len = c1.length; i < len; i++) { // could skip invariants
                if (c1[i] != c2[i]) {
                    return false;
                }
            }
            return true;
        }
    }
    

Iterators in primitive collections

As of release 0.1.7, Trove's primitive mappings include access through Iterators as well as procedures and functions. The API documentation on those classes contains several examples showing how these can be used effectively and explaining why their semantics differ from those of java.util.Iterator.

Miscellaneous

N.B. using Map.entrySet on a Trove Map is supported, but not encouraged. The reason is that this API requires the creation of the Map.Entry Objects that all other parts of Trove manage to avoid. An alternative is to implement the appropriate Procedure interface and use it to invoke the Map's forEachEntry API. Map.keySet and Map.values are not similarly encumbered; nevertheless, the forEachKey, forEachValue, and transformValues APIs will yield slightly better performance at the cost of compatibility with the interface of java.util.Map.


Last modified: Mon Sep 23 18:22:39 PDT 2002


GNU Trove

GNU Trove is copyright 2001-2003 Eric D. Friedman. All Rights Reserved.