Java Collections Framework

Objectives

• compare and contrast the classes in the Java Collections Framework
• use various classes in the Java Collections Framework

Collections

• A collection is an object that represents a group of objects
• Sets are collections with no duplicates allowed
• Lists are ordered collections with duplicates allowed
• Queues are ordered collections used to hold elements for processing; queues are often ordered as FIFO (first-in, first-out), but priority queues base the order on the relative priority of each element
• Maps are used to associate keys with values; duplicate keys are not allowed; each key can map to no more than one value; the Map interface in Java is distinct from the Collection interface
• Oracle's Java Collections Framework documentation
• Oracle's Java Collections Framework tutorial
• Vector
  • a vector is like an array, but it can automatically grow and shrink
  • the Vector class is thread-safe (can be safely used with multithreading)
  • the Vector class has largely been supplanted by the ArrayList and LinkedList classes which offer better performance, but which are not thread-safe
  • see TestVector.java
• ArrayList: items stored internally as array, so insert and delete may be slow, but direct access via index is very fast
• LinkedList: items stored internally in a doubly-linked list with pointers to both front and back of the list; insert and delete are relatively fast, but direct access via index is slow
• ArrayList and LinkedList can be made synchronized (thread-safe) by wrapping them in a synchronization wrapper
• The Arrays class contains a number of methods that can be used for manipulating arrays; see TestArrays.java
• The Collections class contains many methods useful for dealing with Collections. The impemented algorithms include sort, shuffle, reverse, fill, copy, and binarySearch, which all operate on List objects. It also contains min and max methods, which operate on arbitrary Collection objects. See TestArrays.java
• List objects can effect the underlying array they were built on; see TestSync.java
• Commonly used Collections Framework implementations
  • ArrayList: uses a resizable array to hold a list of objects
  • LinkedList: uses a linked list to hold a list of objects; also provides Queue operations
  • HashSet: uses a hash table to hold a set of objects
  • TreeSet: uses a tree structure to hold a set of objects
  • LinkedHashSet: uses a hash table and linked list to hold a set of objects
  • HashMap: uses a hash table to hold a mapping of keys to values
  • TreeMap: uses a tree structure to hold a mapping of keys to values
  • LinkedHashMap: uses a hash table and linked list to hold a mapping of keys to values
  • PriorityQueue: uses a heap to provide an ordered queue
  • Note: ArrayList, HashSet, and HashMap are generally preferred over the other implementations in most cases
  • Note: Since queues are often used in multithreaded applications, there are a number of specialized (concurrent) Queue implementations