Java collections framework
Encyclopedia
The Java collections framework (JCF) is a set of classes
and interfaces
that implement commonly reusable collection data structure
s.
Although it is a framework
, it works in a manner of a library. The JCF provides both interfaces that define various collections and classes that implement them.
To address the need for reusable collection data structure
s, several independent frameworks were developed, the most used being Doug Lea
's Collections package, and ObjectSpace Generic Collection Library (JGL), whose main goal was consistency with the C++
Standard Template Library
(STL).
The collections framework was designed and developed primarily by Joshua Bloch
, and was introduced in JDK 1.2. It reused a lot of ideas and classes from Doug Lea's Collections package, which was deprecated as a result. Sun choose not to use the ideas of JGL, because they wanted a compact framework, and consistency with C++ was not among one of their goals.
Doug Lea later developed a concurrency
package
, comprising new Collection-related classes. An updated version of these concurrency utilities was included in JDK 5.0 as of JSR 166
.
can hold strings, and the elements from the collection can be used as strings without any casting required.
There are three main types of collections:
can be used more flexibly with its subinterface, . The BlockingQueue interface works like a regular queue, but additions to and removals from the queue are blocking. If remove is called on an empty queue, it can be set to wait either a specified time or indefinitely for an item to appear in the queue. Similarly, adding an item is subject to an optional capacity restriction on the queue, and the method can wait for space to become available in the queue before returning.
The interface is expanded by the subinterface. Deque creates a double-ended queue. While a regular queue only allows insertions at the rear and removals at the front, the deque allows insertions or removals to take place both at the front and the back. A deque is like a queue that can be used forwards or backwards, or both at once. Additionally, both a forwards and a backwards iterator can be generated. The Deque interface is implemented by and .
The interface works similarly to . The same methods for insertion and removal with time limits for waiting for the insertion or removal to become possible are provided. However, the interface also provides the flexibility of a deque. Insertions and removals can take place at both ends. The blocking function is combined with the deque function.
The interface is extended by the interface. Unlike a regular set, the elements in a sorted set are sorted, either by the element's compareTo method, or a method provided to the constructor of the sorted set. The first and last elements of the sorted set can be retrieved, and subsets can be created via minimum and maximum values, as well as beginning or ending at the beginning or ending of the sorted set. The SortedSet interface is implemented by
is extended further via the interface. It's similar to SortedSet, but there are a few additional methods. The floor, ceiling, lower, and higher methods find an element in the set that's close to the parameter. Additionally, a descending iterator over the items in the set is provided. As with SortedSet, implements NavigableSet.
The interface is extended by its subinterface, . This interface defines a map that's sorted by the keys provided. Using, once again, the compareTo method or a method provided in the constructor to the sorted map, the key-value pairs are sorted by the keys. The first and last keys in the map can be called. Additionally, submaps can be created from minimum and maximum keys. SortedMap is implemented by .
The interface extends in various ways. Methods can be called that find the key or map entry that's closest to the given key in either direction. The map can also be reversed, and an iterator in reverse order can be generated from it. It's implemented by .
Class (computer science)
In object-oriented programming, a class is a construct that is used as a blueprint to create instances of itself – referred to as class instances, class objects, instance objects or simply objects. A class defines constituent members which enable these class instances to have state and behavior...
and interfaces
Interface (Java)
An interface in the Java programming language is an abstract type that is used to specify an interface that classes must implement. Interfaces are declared using the interface keyword, and may only contain method signature and constant declarations...
that implement commonly reusable collection data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s.
Although it is a framework
Software framework
In computer programming, a software framework is an abstraction in which software providing generic functionality can be selectively changed by user code, thus providing application specific software...
, it works in a manner of a library. The JCF provides both interfaces that define various collections and classes that implement them.
History
Collection implementations in pre-JDK 1.2 versions of the Java platform included few data structure classes, but did not contain a collections framework. The standard methods for grouping Java objects were via the array, the , and the classes, which unfortunately were not easy to extend, and did not implement a standard member interface.To address the need for reusable collection data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s, several independent frameworks were developed, the most used being Doug Lea
Doug Lea
Doug Lea is a professor of computer science at State University of New York at Oswego where he specializes in concurrent programming and the design of concurrent data structures. He was on the Executive Committee of the Java Community Process and chaired JSR 166, which added concurrency utilities...
's Collections package, and ObjectSpace Generic Collection Library (JGL), whose main goal was consistency with the C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
Standard Template Library
Standard Template Library
The Standard Template Library is a C++ software library which later evolved into the C++ Standard Library. It provides four components called algorithms, containers, functors, and iterators. More specifically, the C++ Standard Library is based on the STL published by SGI. Both include some...
(STL).
The collections framework was designed and developed primarily by Joshua Bloch
Joshua Bloch
Joshua J. Bloch is a software engineer, currently employed at Google, and a technology author. He led the design and implementation of numerous Java platform features, including the Java Collections Framework, the java.math package, and the assert mechanism...
, and was introduced in JDK 1.2. It reused a lot of ideas and classes from Doug Lea's Collections package, which was deprecated as a result. Sun choose not to use the ideas of JGL, because they wanted a compact framework, and consistency with C++ was not among one of their goals.
Doug Lea later developed a concurrency
Concurrency (computer science)
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
package
Java package
A Java package is a mechanism for organizing Java classes into namespaces similar to the modules of Modula. Java packages can be stored in compressed files called JAR files, allowing classes to download faster as a group rather than one at a time...
, comprising new Collection-related classes. An updated version of these concurrency utilities was included in JDK 5.0 as of JSR 166
Java concurrency
The Java language and the JVM have been designed to support concurrent programming, and all execution in takes place in the context of threads. Objects and resources can be accessed by many separate threads; each thread has its own path of execution but can potentially access any object in the...
.
Architecture
Almost all collections in Java are derived from the interface. Collection defines the basic parts of all collections. The interface states the add and remove methods for adding to and removing from a collection respectively. Also required is the toArray method, which converts the collection into a simple array of all the elements in the collection. Finally, the contains method checks if a specified element is in the collection. The Collection interface is a subinterface of , so the iterator method is also provided. All collections have an iterator that goes through all of the elements in the collection. Additionally, Collection is a generic. Any collection can be written to store any class. For example, CollectionThere are three main types of collections:
- Lists: always ordered, may contain duplicates and can be handled the same way as usual arrays
- Sets: cannot contain duplicates and provide random access to their elements
- Maps: connect unique keys with values, provide random access to its keys and may host duplicate values
List Interface
Lists are implemented in the JCF via the interface. It defines a list as essentially a more flexible version of an array. Elements have a specific order, and duplicate elements are allowed. Elements can be placed in a specific position. They can also be searched for within the list. Two concrete classes implement List. The first is , which implements the list as an array. Whenever functions specific to a list are required, the class moves the elements around within the array in order to do it. The other implementation is . This class stores the elements in nodes that each have a pointer to the previous and next nodes in the list. The list can be traversed by following the pointers, and elements can be added or removed simply by changing the pointers around to place the node in its proper place.Queue Interfaces
The interface defines the queue data structure, which stores elements in the order in which they are inserted. New additions go to the end of the line, and elements are removed from the front. It creates a first-in first-out system. This interface is implemented by , , and . LinkedList, of course, also implements the List interface and can also be used as one. But it also has the Queue methods. ArrayDeque implements the queue as an array. Both LinkedList and ArrayDeque also implement the interface, giving it more flexibility.can be used more flexibly with its subinterface, . The BlockingQueue interface works like a regular queue, but additions to and removals from the queue are blocking. If remove is called on an empty queue, it can be set to wait either a specified time or indefinitely for an item to appear in the queue. Similarly, adding an item is subject to an optional capacity restriction on the queue, and the method can wait for space to become available in the queue before returning.
The interface is expanded by the subinterface. Deque creates a double-ended queue. While a regular queue only allows insertions at the rear and removals at the front, the deque allows insertions or removals to take place both at the front and the back. A deque is like a queue that can be used forwards or backwards, or both at once. Additionally, both a forwards and a backwards iterator can be generated. The Deque interface is implemented by and .
The interface works similarly to . The same methods for insertion and removal with time limits for waiting for the insertion or removal to become possible are provided. However, the interface also provides the flexibility of a deque. Insertions and removals can take place at both ends. The blocking function is combined with the deque function.
PriorityQueue Class
implements , but also alters it. Instead of elements being ordering by the order in which they are inserted, they are ordered by priority. The method used to determine priority is either the compareTo method in the elements or a method given in the constructor. The class creates this by using a heap to keep the items sorted.Set Interfaces
Java's interface defines the set. A set can't have any duplicate elements in it. Additionally, the set has no set order. As such, elements can't be found by index. Set is implemented by , , and . HashSet uses a hash table. More specifically, it uses a to store the hashes and elements and to prevent duplicates. extends this by creating a doubly linked list that links all of the elements by their insertion order. This ensures that the iteration order over the set is predictable. uses a red-black tree implemented by a . The red-black tree makes sure that there are no duplicates. Additionally, it allows TreeSet to implement .The interface is extended by the interface. Unlike a regular set, the elements in a sorted set are sorted, either by the element's compareTo method, or a method provided to the constructor of the sorted set. The first and last elements of the sorted set can be retrieved, and subsets can be created via minimum and maximum values, as well as beginning or ending at the beginning or ending of the sorted set. The SortedSet interface is implemented by
is extended further via the interface. It's similar to SortedSet, but there are a few additional methods. The floor, ceiling, lower, and higher methods find an element in the set that's close to the parameter. Additionally, a descending iterator over the items in the set is provided. As with SortedSet, implements NavigableSet.
Map Interfaces
Maps are defined by the interface in Java. Maps are simple data structures that associate a key with a value. The element is the value. This lets the map be very flexible. If the key is the hash code of the element, the map is essentially a set. If it's just an increasing number, it becomes a list. Maps are implemented by , , and . HashMap uses a hash table. The hashes of the keys are used to find the values in various buckets. LinkedHashMap extends this by creating a doubly linked list between the elements. This allows the elements to be accessed in the order in which they were inserted into the map. TreeMap, in contrast to HashMap and LinkedHashMap, uses a red-black tree. The keys are used as the values for the nodes in the tree, and the nodes point to the values in the map.The interface is extended by its subinterface, . This interface defines a map that's sorted by the keys provided. Using, once again, the compareTo method or a method provided in the constructor to the sorted map, the key-value pairs are sorted by the keys. The first and last keys in the map can be called. Additionally, submaps can be created from minimum and maximum keys. SortedMap is implemented by .
The interface extends in various ways. Methods can be called that find the key or map entry that's closest to the given key in either direction. The map can also be reversed, and an iterator in reverse order can be generated from it. It's implemented by .
See also
- Container (data structure)Container (data structure)In computer science, a container is a class, a data structure, or an abstract data type whose instances are collections of other objects. In other words; they are used for storing objects in an organized way following specific access rules...
- Standard Template LibraryStandard Template LibraryThe Standard Template Library is a C++ software library which later evolved into the C++ Standard Library. It provides four components called algorithms, containers, functors, and iterators. More specifically, the C++ Standard Library is based on the STL published by SGI. Both include some...
- Java concurrencyJava concurrencyThe Java language and the JVM have been designed to support concurrent programming, and all execution in takes place in the context of threads. Objects and resources can be accessed by many separate threads; each thread has its own path of execution but can potentially access any object in the...
External links
- 'Which Java Collection to use?' — by Janeve George
- 'The Java Tutorials - Collections' by Josh Bloch
- 'The Collections Framework' (Sun Java SE 6 documentation)
- Generic Types
- Java Generics and Collections
- Taming Tiger: The Collections Framework
- Collections Lessons
- CollectionSpy — A profiler for Java's Collections Framework.
- Java 6 Collection Tutorial — By Jakob Jenkov, Kadafi Kamphulusa