Choosing One of the Provided Implementation Variants

When you are developing a program that uses a collection, you should begin by using the default implementation and go on to a final tuning phase where you choose implementations according to the actual requirements of your application. You can determine these requirements by profiling or by using other measurement tools. You need to choose between a variety of implementations provided by the Collection Classes as well as how to create your own implementation classes.

The collection implementations can be based on other collection classes. The based-on concept provides a systematic framework for choosing the most appropriate implementations. It is also useful for extending the Collection Classes with other basic implementations, such as specific kinds of search trees, and for using these implementations as the basis for other data abstractions such as sets, maps, and bags.

You can implement a given collection type (bag, key sorted set, etc.) in a number of different ways. The Collection Classes provide multiple implementation variants for collections because different variants have different performance and storage use characteristics. After you have coded and debugged an application that uses the Collection Classes, you can change an implementation to a variant that is well-suited to the ways in which you use the collection. For example, six implementation variants are listed for key set, including the default key set. These variants are implemented using the following concrete techniques:

• Sequences
  • List
  • Table
  • Diluted table
• Trees
  • AVL tree (the technique used for the default key set)
  • B* tree
• Hash table

As it turns out, the implementation variants for key set encompass all the concrete techniques used by the Collection Classes. Other collections may only use some of the techniques in the list above. If you want to choose the best implementation variant for your program, you need to know the advantages of each concrete technique.

Introduction to the Collection Classes
Collection Class Hierarchy
Flat Collections
Trees
AVL Tree
B* Tree
Diluted Table
Hash Table
List
Table

Class Template Naming Conventions
Possible Implementation Paths
Taking Advantage of the Abstract Class Hierarchy
Instantiating the Collection Classes
Troubleshooting Problems while Using the Collection Class Library