GNU Trove

Package gnu.trove

GNU Trove: High performance collections for Java.

See:
          Description

Interface Summary
TByteByteProcedure Interface for procedures that take two parameters of type byte and byte.
TByteDoubleProcedure Interface for procedures that take two parameters of type byte and double.
TByteFloatProcedure Interface for procedures that take two parameters of type byte and float.
TByteFunction Interface for functions that accept and return one byte primitive.
TByteHashingStrategy Interface to support pluggable hashing strategies in maps and sets.
TByteIntProcedure Interface for procedures that take two parameters of type byte and int.
TByteLongProcedure Interface for procedures that take two parameters of type byte and long.
TByteObjectProcedure Interface for procedures that take two parameters of type byte and Object.
TByteProcedure Interface for procedures with one byte paramater.
TByteShortProcedure Interface for procedures that take two parameters of type byte and short.
TDoubleByteProcedure Interface for procedures that take two parameters of type double and byte.
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.
TDoubleShortProcedure Interface for procedures that take two parameters of type double and short.
TFloatByteProcedure Interface for procedures that take two parameters of type float and byte.
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.
TFloatShortProcedure Interface for procedures that take two parameters of type float and short.
TIntByteProcedure Interface for procedures that take two parameters of type int and byte.
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.
TIntShortProcedure Interface for procedures that take two parameters of type int and short.
TLinkable Interface for Objects which can be inserted into a TLinkedList.
TLongByteProcedure Interface for procedures that take two parameters of type long and byte.
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.
TLongShortProcedure Interface for procedures that take two parameters of type long and short.
TObjectByteProcedure Interface for procedures that take two parameters of type Object and byte.
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.
TObjectShortProcedure Interface for procedures that take two parameters of type Object and short.
TShortByteProcedure Interface for procedures that take two parameters of type short and byte.
TShortDoubleProcedure Interface for procedures that take two parameters of type short and double.
TShortFloatProcedure Interface for procedures that take two parameters of type short and float.
TShortFunction Interface for functions that accept and return one short primitive.
TShortHashingStrategy Interface to support pluggable hashing strategies in maps and sets.
TShortIntProcedure Interface for procedures that take two parameters of type short and int.
TShortLongProcedure Interface for procedures that take two parameters of type short and long.
TShortObjectProcedure Interface for procedures that take two parameters of type short and Object.
TShortProcedure Interface for procedures with one short paramater.
TShortShortProcedure Interface for procedures that take two parameters of type short and short.
 

Class Summary
HashFunctions Provides various hash functions.
PrimeFinder Used to keep hash table capacities prime numbers.
TByteArrayList A resizable, array-backed list of byte primitives.
TByteByteHashMap An open addressed Map implementation for byte keys and byte values.
TByteByteIterator Iterator for maps of type byte and byte.
TByteDoubleHashMap An open addressed Map implementation for byte keys and double values.
TByteDoubleIterator Iterator for maps of type byte and double.
TByteFloatHashMap An open addressed Map implementation for byte keys and float values.
TByteFloatIterator Iterator for maps of type byte and float.
TByteHash An open addressed hashing implementation for byte primitives.
TByteHashSet An open addressed set implementation for byte primitives.
TByteIntHashMap An open addressed Map implementation for byte keys and int values.
TByteIntIterator Iterator for maps of type byte and int.
TByteIterator Iterator for byte collections.
TByteLongHashMap An open addressed Map implementation for byte keys and long values.
TByteLongIterator Iterator for maps of type byte and long.
TByteObjectHashMap An open addressed Map implementation for byte keys and Object values.
TByteObjectIterator Iterator for maps of type byte and Object.
TByteShortHashMap An open addressed Map implementation for byte keys and short values.
TByteShortIterator Iterator for maps of type byte and short.
TDoubleArrayList A resizable, array-backed list of double primitives.
TDoubleByteHashMap An open addressed Map implementation for double keys and byte values.
TDoubleByteIterator Iterator for maps of type double and byte.
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.
TDoubleShortHashMap An open addressed Map implementation for double keys and short values.
TDoubleShortIterator Iterator for maps of type double and short.
TFloatArrayList A resizable, array-backed list of float primitives.
TFloatByteHashMap An open addressed Map implementation for float keys and byte values.
TFloatByteIterator Iterator for maps of type float and byte.
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.
TFloatShortHashMap An open addressed Map implementation for float keys and short values.
TFloatShortIterator Iterator for maps of type float and short.
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.
TIntByteHashMap An open addressed Map implementation for int keys and byte values.
TIntByteIterator Iterator for maps of type int and byte.
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.
TIntShortHashMap An open addressed Map implementation for int keys and short values.
TIntShortIterator Iterator for maps of type int and short.
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.
TLongByteHashMap An open addressed Map implementation for long keys and byte values.
TLongByteIterator Iterator for maps of type long and byte.
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.
TLongShortHashMap An open addressed Map implementation for long keys and short values.
TLongShortIterator Iterator for maps of type long and short.
TObjectByteHashMap An open addressed Map implementation for Object keys and byte values.
TObjectByteIterator Iterator for maps of type Object and byte.
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.
TObjectShortHashMap An open addressed Map implementation for Object keys and short values.
TObjectShortIterator Iterator for maps of type Object and short.
TPrimitiveHash The base class for hashtables of primitive values.
TShortArrayList A resizable, array-backed list of short primitives.
TShortByteHashMap An open addressed Map implementation for short keys and byte values.
TShortByteIterator Iterator for maps of type short and byte.
TShortDoubleHashMap An open addressed Map implementation for short keys and double values.
TShortDoubleIterator Iterator for maps of type short and double.
TShortFloatHashMap An open addressed Map implementation for short keys and float values.
TShortFloatIterator Iterator for maps of type short and float.
TShortHash An open addressed hashing implementation for short primitives.
TShortHashSet An open addressed set implementation for short primitives.
TShortIntHashMap An open addressed Map implementation for short keys and int values.
TShortIntIterator Iterator for maps of type short and int.
TShortIterator Iterator for short collections.
TShortLongHashMap An open addressed Map implementation for short keys and long values.
TShortLongIterator Iterator for maps of type short and long.
TShortObjectHashMap An open addressed Map implementation for short keys and Object values.
TShortObjectIterator Iterator for maps of type short and Object.
TShortShortHashMap An open addressed Map implementation for short keys and short values.
TShortShortIterator Iterator for maps of type short and short.
 

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-2005 Eric D. Friedman. All Rights Reserved.