Collections : Java Glossary

by Roedy Green ©1996-2008 Canadian Mind Products
Go to : punctuation 0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z (all)

Collections

The Collection interface is a feature of JDK 1.2+. A collection in data structure terms, is a group of elements. Most of the collection classes live in the java.util package Some types of collections that derive from Collection include the following:

Collection Classes and Interfaces
Class	Interface or Collection	Synchronised	Notes
AbstractCollection	abstract class		a class to act as skeleton to build most classes that implement the Collection interface..
java.lang.reflect.Array	class		Reflection classes used to dynamically create Array objects where you don’t know anything about them at compile time. You probably were looking for Arrays instead.
java.lang.sql.Array	class		A class for storing and retrieving arrays in an SQL database. You probably were looking for Arrays instead.
ArrayList	class	no	A non-thread-safe List that is marginally faster than thread-safe Vector. In versions prior to JDK 1.4, the difference was more pronounced — 3 to 4 times faster. Rolling your own array is about 4 times faster than Vector. In earlier non-optimising JVMs, the difference was more like 40 times faster. The main overhead of using ArrayList and Vector is the casting needed to fish out the elements. ArrayList is like a [] array that automatically grows. Lookup by dense ints. Considerably faster than a HashMap.
Arrays	class	no	static methods for sorting and searching ordinary arrays, e.g. binarySearch, fill, sort. asList converts an array into a List Collection you can then feed to methods expecting a Collection or List. Don’t confuse this with the two Array classes.
Collection	interface	no	The interface that all collections implement that guarantee you can always add, remove, clear, size, iterator, contains, toArray etc. in a standard way. Don’t confuse this with the Collections class. toArray can be made smarter if you pass it an empty array to fill just the right size. Then you have an array of specific classes, not just generic Objects. Use it like this: Dogs[] dogs = ( Dogs [] )dogArrayList.toArray ( new Dogs [dogArrayList.size()] ); The Collection.toString method implemented by all Collections is a great debugging tool to dump out the entire contents of a Collection in a reasonably human-readable format enclosing each element in [].
Collections	class	no	static methods for operating on collections, e.g. min, max, shuffle. Don’t confuse the Collections class with the Collection interface.
javax.swing.tree.DefaultTreeModel	class	no	This was written to support Swing’s Jtree, but it will suffice as a generic Tree collection.
HashMap	class	no	a Map, an unsynchronized Hashtable. Allows unordered lookup by key, usually a String. It is thread safe if you only do lookups. Otherwise you must synchronise externally, or use a Hashtable. No duplicates allowed.
HashSet	class	no	a Set, a collection of unique objects, without ability to lookup by key, usually a String. Not ordered. Often used to maintain a list of legal values, e.g. state abbreviations. You can quickly find out if a given value is in the legal list.
Hashtable	class	yes	a Map, a synchronised HashMap. Allows unordered lookup by key, usually a String. Note, this is spelled Hashtable not HashTable.
IdentityHashMap	class	no	It is like a Hashtable. Used in manipulating graphs where you have to keep track of which nodes have already been visited. New in Java 1.4.
LinkedHashMap	class	no	a HashMap that also threads the objects together, usually in insertion order. This way you can retrieve the elements in insertion order with almost no more overhead than a HashMap. New in JDK 1.4.
LinkedList	class	no	a List that behaves like Vector, but implemented as a doubly linked chain of objects. Fast for insert/ delete. Slow for indexing.
List	interface		specifies an ordered sequence of elements. Implemented by ArrayList, Vector and LinkedList.
Map	interface		supports lookup of objects by unique key. Keys may or may not be ordered.
RandomAccess	interface		Interface does not do anything. It is just a marker that lets you know random access to a List is efficient. e.g. LinkedList would not implement it, whereas ArrayList would. New in Java 1.4.
Set	interface		a mathematical set of elements, with no duplication. No lookup by key.
SortedMap	interface		Map interface that guarantees sorted keys, usually Strings. implemented by TreeMap.
SortedSet	interface		Set interface that guarantees iteration will be in ascending order. Implemented by TreeSet
Stack	class		pushdown stack, a LIFO (Last In First Out) queue. You can also fudge a simple LIFO stack with LinkedList using use only addFirst, removeFirst.
TreeMap	class	no	a SortedMap using a Red-Black tree. Allows ordered lookup by key, usually Strings. Does not allow duplicate keys, unless you cheat to fool it into thinking they are not really duplicates. Slower than HashMap.
TreeSet	class	no	a SortedSet using a Red-Black tree. Allows ordered access, but no access by key. Slower than HashSet.
Vector	class	yes	a List. This is the same old Vector you are familiar with, now implementing Collection. It acts like a []- style array that automatically grows as needed. It is a synchronised ArrayList, i.e. suitable for use when more than one thread accesses the Vector.

Missing Collections

Collections that you would expect to find in JDK 1.4-, but which are not included are:

FIFOQueue, a FIFO (First In First Out) buffering queue.
FIFOPriorityQueue, a FIFO queue with N levels of priority, so that the top priority items are normally taken first, but it is possible to service the lower priorities less frequently, e.g. serve four from top level, for every two from next level for every one from the level below, or with priority bumping if an item waits in a queue past a given threshhold. You could use it for applications like airline boarding, emergency waiting rooms, computer task scheduling or even your personal todo list. You can fudge a simple FIFO queue with LinkedList using use only addFirst, removeLast.
SortedList that gives the illusion of always automatically staying sorted.
Cached collections that automatically drop elements not used in a long time to keep the collection from growing too large.
Persistent collections that automatically load from disk and save back to disk.
For other missing collections check out these sources:
AmberArcher
Jakarta Common Collections (incudes bidirectional map)
PCJ
Trove4J
Walt Disney Tea Trove (includes: FlyweightSet, PropertyMap, SortedArrayList)

In JDK 1.5 some of these deficiencies were rectified with the Queue interface.

Duplicate Keys

Nearly all the collections prevent you from storing duplicate keys. There are several ways around that:

Write your own collection that permit duplicates.
Invent tie breaker logic to create auxilary tail ends to the key to artificially make all keys unique. E.g. First key "rover" goes in as "rover" and the next as "rover2" Before inserting, you must alway check if the key has already been added, and if so, try a tie breaker until you find one that has not.
Instead of storing data objects in your map, store a FIFOQueue of data objects that share the same key. This preserves FIFO order on duplicates. When there are no duplicate for a given keys, store a data object directly. You could similarly handle the problem with ArrayLists of duplicates instead of FIFOQueues. FIFOQueues have the advantage of not needing to estimate the number of duplicates for each key ahead of time.

The new java.lang.Comparable interface makes it easier to sort Collections. Even String implements it.

Even if you are stuck with JDK 1.1, you can still retrofit some of the 1.2 JDK Collections classes. You won’t be able to use any of the natural ordering methods since they require adding the java.lang.Comparable interface to the core classes.

Learning More

Sun’s JDK Technote Guide on Collections Summary : available:

on the web at java.Sun.com
in the JDK 1.6.0_06 on your local J: drive.

Sun’s Javadoc on the Collection interface class : available:

on the web at java.Sun.com
in the JDK 1.6.0_06 or in the older JDK 1.5.0_15 or the even older JDK 1.4.2_17 on your local J: drive.

Sun’s Javadoc on the Collections class : available:

on the web at java.Sun.com
in the JDK 1.6.0_06 or in the older JDK 1.5.0_15 or the even older JDK 1.4.2_17 on your local J: drive.

ArrayList
Collections of Source Code
generics
HashCode
HashMap
Hashtable
Iterator
Queue
sort
stack
TreeMap
TreeSet
Vector

	Please email your feedback for publication, errors, omissions, broken/redirected link reports and suggestions to improve this page to Roedy Green :
	Canadian Mind Products
	mindprod.com IP:[65.110.21.43]
	Your face IP:[38.103.63.17]	The information on this page is for non-military use only.
	You are visitor number 126,735.	Military use includes use by defence contractors.
	You can get a fresh copy of this page from:	or possibly from your local J: drive (Java virtual drive/Mindprod website mirror)
	http://mindprod.com/jgloss/collection.html	J:\mindprod\jgloss\collection.html