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