gnu.trove

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Development » trove » gnu.trove 
gnu.trove
GNU Trove API Documentation

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
Java Source File NameTypeComment
HashFunctions.javaClass Provides various hash functions.
O2PHashMapTest.javaClass
P2OHashMapTest.javaClass
P2PHashMapTest.javaClass
PrimeFinder.javaClass Used to keep hash table capacities prime numbers. Not of interest for users; only for implementors of hashtables.

Choosing prime numbers as hash table capacities is a good idea to keep them working fast, particularly under hash table expansions.

However, JDK 1.2, JGL 3.1 and many other toolkits do nothing to keep capacities prime.

PrimeFinderTest.javaClass Created: Sun Nov 4 11:37:24 2001
author:
   Eric D.
SerializationProcedure.javaClass Implementation of the variously typed procedure interfaces that supports writing the arguments to the procedure out on an ObjectOutputStream. In the case of two-argument procedures, the arguments are written out in the order received.

Any IOException is trapped here so that it can be rethrown in a writeObject method.

Created: Sun Jul 7 00:14:18 2002
author:
   Eric D.
SerializationTest.javaClass
TArrayListTest.javaClass
THash.javaClass Base class for hashtables that use open addressing to resolve collisions. Created: Wed Nov 28 21:11:16 2001
author:
   Eric D.
THashIterator.javaClass Implements all iterator functions for the hashed object set. Subclasses may override objectAtIndex to vary the object returned by calls to next() (e.g.
THashMap.javaClass An implementation of the Map interface which uses an open addressed hash table to store its contents. Created: Sun Nov 4 08:52:45 2001
author:
   Eric D.
THashMapTest.javaClass Created: Sat Nov 3 10:31:38 2001
author:
   Eric D.
THashSet.javaClass An implementation of the Set interface that uses an open-addressed hash table to store its contents. Created: Sat Nov 3 10:38:17 2001
author:
   Eric D.
THashSetTest.javaClass Created: Sat Nov 3 10:33:15 2001
author:
   Eric D.
TIdentityHashMapTest.javaClass
TIdentityHashSetTest.javaClass
TIterator.javaClass Abstract iterator class for THash implementations.
TLinkable.javaInterface Interface for Objects which can be inserted into a TLinkedList.

Created: Sat Nov 10 15:23:41 2001


author:
   Eric D.
TLinkableAdapter.javaClass 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.javaClass A LinkedList implementation which holds instances of type TLinkable.

Using this implementation allows you to get java.util.LinkedList behavior (a doubly linked list, with Iterators that support insert and delete operations) without incurring the overhead of creating Node wrapper objects for every element in your list.

The requirement to achieve this time/space gain is that the Objects stored in the List implement the TLinkable interface.

The limitations are that you cannot put the same object into more than one list or more than once in the same list.

TLinkedListTest.javaClass Created: Sat Nov 10 15:57:07 2001
author:
   Eric D.
TObjectFunction.javaInterface Interface for functions that accept and return one Object reference. Created: Mon Nov 5 22:19:36 2001
author:
   Eric D.
TObjectHash.javaClass An open addressed hashing implementation for Object types. Created: Sun Nov 4 08:56:06 2001
author:
   Eric D.
TObjectHashingStrategy.javaInterface Interface to support pluggable hashing strategies in maps and sets.
TObjectHashIterator.javaClass Created: Wed Nov 28 21:30:53 2001
author:
   Eric D.
TObjectIdentityHashingStrategy.javaClass This object hashing strategy uses the System.identityHashCode method to provide identity hash codes.
TObjectObjectProcedure.javaInterface Interface for procedures that take two Object parameters. Created: Mon Nov 5 22:03:30 2001
author:
   Eric D.
TObjectProcedure.javaInterface Interface for procedures with one Object parameter. Created: Mon Nov 5 21:45:49 2001
author:
   Eric D.
ToObjectArrayProcedure.javaClass A procedure which stores each value it receives into a target array. Created: Sat Jan 12 10:13:42 2002
author:
   Eric D.
TPrimitiveHash.javaClass The base class for hashtables of primitive values.
TPrimitiveIterator.javaClass Implements all iterator functions for the hashed object set. Subclasses may override objectAtIndex to vary the object returned by calls to next() (e.g.
TStackTest.javaClass
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.