Java Collections Framework & Map

Learn how to used the Java Collections framework and the Map interface.
Tutorial covers version JDK 1.7.

Environment Tested

• 09/29/2011 - Windows 7, JDK 1.6.0_24, Eclipse Helios Service Release 2

Resources

• Oracle (Java's) Collections Tutorial - http://download.oracle.com/javase/tutorial/collections/index.html - by Josh Bloch
• Java SE API Documentation - (API v7) (API v6)
• Wikipedia's - http://en.wikipedia.org/wiki/Java_collections_framework

Abbreviations

• E - Element
• K - key
• V - value

The Big Picture

• A collection — is a container type object that groups multiple elements into a single object. Collections are used to store, retrieve, manipulate a group of data. A collection is similar to the JDK 1.1 Vector, Hashtable and array. The collections framework first appeared in JDK 1.2.
• UML Diagram of Collections Framework (this figure is from Oracles tutorial by Josh Bloch)

• Types of Collections
  • Collection - There are three main types of collections (interfaces): List, Set, Queue
    • SortedSet (interface) is a subinterface of Set.
  • Map - Notice that Map is technically NOT apart of the Collections classes but they are so similar that we group them together.
    • SortedMap (interface) is a subinterface of Map
• Here are some of the Implementations of the Collections Framework.  There are other more specialized implementations not mentioned here.
  • List interface (Most popular)
    • ArrayList (most common)
    • LinkedList
  • Set interface
    • HashSet (most common)
    • LinkedHashSet
    • TreeSet
  • Map interface
    • HashMap (most common)
    • LinkedHashMap
    • TreeMap
  • Queue interface
    • LinkedList (most common)
    • ArrayDeque
    • PriorityQueue

Reference Type Info

Code Examples

• NOTE: Make sure you read through the JUnit Test file and see how it uses the java source files. 
• I highly value code examples so I hope you enjoy!
• Download info:  If you download the zip of the tutorial then locate the directory "workspace".  Look in the \src\ directory for the .java source files and the \test\ directory for the .java JUnit test files.  The "workspacetext" directory has the .txt versions I use to display over the internet.
  Project/Directory name:  collections
• Collection Framework
  • Collection (Interface) - All the collection implementations have access to these methods!
    • JUnit (Testing) - collection/MyCollectionTest.txt - This is the main file to view and then reference the other files.
    • Java Source -  collection/MyCollectionData.txt - build the collections.
    • Java Source - collection/MyCollectionSort.txt - sort collections
    • Java Source - collection/MyCollectionTraverse.txt - traverse the collections.
    • Java Source - collection/MyItem.txt
  • List Interface
    • List (Interface) - NOTE: Remember to look at the "Collection" examples.
      • JUnit (Testing) - list/MyListTest.txt
      • Java Source - list/MyList.txt
    • ArrayList (Implementation) - NOTE: Remember to look at the "Collection" & "List" examples.
      • JUnit (Testing) - list/arraylist/MyArrayListTest.txt
      • Java Source - list/arraylist/MyArrayList.txt
    • LinkedList (Implementation) - NOTE: Remember to look at the "Collection" & "List" examples.
      • JUnit (Testing) - list/linkedlist/MyLinkedListTest.txt
      • Java Source - list/linkedlist/MyLinkedList.txt
  • Set
    • Set (Interface) - NOTE: Remember to look at the "Collection" JUnit & Source files.
      • JUnit (Testing) - set/MySetTest.txt
      • Java Source - set/MySet.txt
    • HashSet (Implementation) - NOTE: Remember to look at the "Collection" & "Set" examples.
      • JUnit (Testing) - set/hashset/MyHashSetTest.txt
      • Java Source - set/hashset/MyHashSet.txt
    • LinkedHashSet (Implementation) - NOTE: Remember to look at the "Collection" & "Set" examples.
      • JUnit (Testing) - set/linkedhashset/MyLinkedHashSetTest.txt
      • Java Source - set/linkedhashset/MyLinkedHashSet.txt
    • TreeSet (Implementation) - NOTE: Remember to look at the "Collection" & "Set" examples.
      • JUnit (Testing) - set/treeset/MyTreeSetTest.txt
      • Java Source - set/treeset/MyTreeSet.txt
• Map (interface)
  • Map (Interface) (common to all Map)
    • JUnit (Testing) - map/MyMapTest.txt
    • Java Source - map/MyMap.txt
      Java Source - map/MyMapTraverse.txt - traversing a Map
  • HashMap (Implementation) - NOTE: Remember to look at the "Map" examples.
    • JUnit (Testing) - map/hashmap/MyHashMapTest.txt
    • Java Source - map/hashmap/MyHashMap.txt
  • LinkedHasMap (Implementation) - NOTE: Remember to look at the "Map" examples.
    • JUnit (Testing) - map/linkedhashmap/MyLinkedHashMapTest.txt
    • Java Source - map/linkedhashmap/MyLinkedHashMap.txt
  • TreeMap (Implementation) - NOTE: Remember to look at the "Map" examples.
    • JUnit (Testing) - map/treemap/MyTreeMapTest.txt
    • Java Source - map/treemap/MyTreeMap.txt

Collection Interface

• Collections Interface (API v7.0) - here are the methods available for implementations of the collections framework classes.
  • public interface Collection<E> extends Iterable<E> {
  • Methods (interface)
    • boolean add(E e) - Ensures that this collection contains the specified element (optional operation).
    • boolean addAll(Collection<? extends E> c) - Adds all of the elements in the specified collection to this collection (optional operation).
    • void clear() - Removes all of the elements from this collection (optional operation).
    • boolean contains(Object o) - Returns true if this collection contains the specified element.
    • boolean containsAll(Collection<?> c) - Returns true if this collection contains all of the elements in the specified collection.
    • boolean equals(Object o) - Compares the specified object with this collection for equality.
    • int hashCode() - Returns the hash code value for this collection.
    • boolean isEmpty() - Returns true if this collection contains no elements.
    • Iterator<E> iterator() - Returns an iterator over the elements in this collection.
    • boolean remove(Object o) - Removes a single instance of the specified element from this collection, if it is present (optional operation).
    • boolean removeAll(Collection<?> c) - Removes all of this collection's elements that are also contained in the specified collection (optional operation).
    • boolean retainAll(Collection<?> c) - Retains only the elements in this collection that are contained in the specified collection (optional operation).
    • int size() - Returns the number of elements in this collection.
    • Object[] toArray() - Returns an array containing all of the elements in this collection.
    • <T> T[] toArray(T[] a) - Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.
• Traversing a Collection
  • You can traverse a collection using an iterator or looping with ForLoop/ForEach/While.
  • Use "iterator" if you want to "remove" an element or iterate or multiple collections in parallel.

Iterator<E> Interface

• Iterator Inteface (API v7)
• Methods (interface)
  • boolean hasNext() - true if iteration has another element.
  • E next() - returns the next element.
  • void remove() - removes the item.

ListIterator<E> Interface

• ListIterator Interface (API v7)
• Methods (interface)
  • void add(E e) - Inserts the specified element into the list (optional operation).
  • boolean hasNext() - Returns true if this list iterator has more elements when traversing the list in the forward direction.
  • boolean hasPrevious() - Returns true if this list iterator has more elements when traversing the list in the reverse direction.
  • E next() - Returns the next element in the list and advances the cursor position.
  • int nextIndex() - Returns the index of the element that would be returned by a subsequent call to next().
  • E previous() - Returns the previous element in the list and moves the cursor position backwards.
  • int previousIndex() - Returns the index of the element that would be returned by a subsequent call to previous().
  • void remove() - Removes from the list the last element that was returned by next() or previous() (optional operation).
  • void set(E e) - Replaces the last element returned by next() or previous() with the specified element (optional operation).
     

Common Uses

• The most commonly used collection is the List using the ArrayList implementation. (ex: ArrayList list = new ArrayList();)

List (interface: java.util.List )

• List interface (API v7)
  • Features of List
    • duplicates: may contain duplicates
    • order: always ordered (sequence)
    • access: elements can be placed in a specific position
    • search: can searched elements within the list
    • Misc info
      • handled the same way as usual arrays
  • Additional Methods: (has Collection and these!)
    • void add(int index, E element) (optional operation)  - this one has an index option!
    • boolean addAll(int index, Collection<? extends E> c) - this one has an index option!
    • E get(int index)
    • int indexOf(Object o)
    • int lastIndexOf(Object o)
    • ListIterator<E> listIterator()
    • ListIterator<E> listIterator(int index)
    • E remove(int index) - this one returns the Element and removes!
    • E set(int index, E element)
    • List<E> subList(int fromIndex, int toIndex)
  • Other related methods
    • java.util.Arrays.asList (API v7) - static <T> List<T> asList(T... a)  - Returns a fixed-size list backed by the specified array.
• Implementations of List interface
  • ArrayList (API v7) (implementation: java.util.ArrayList)
    • Method Signature:
      public class ArrayList<E>
      extends AbstractList<E>
      implements List<E>, RandomAccess, Cloneable, Serializable
    • Additional features of ArrayList.
      • Very fast.
      • Replaces Vector (JDK 1.1) but doesn't have the synchronization overhead.
      • Generally use instead of LinkedList.
      • Has 1 tuning parameter: initial capacity
    • Additional Methods: (has Collection, List and these!)
      • Object clone() - Returns a shallow copy of this ArrayList instance.
      • void ensureCapacity(int minCapacity) - Increases the capacity of this ArrayList instance, if necessary.
      • protected void removeRange(int fromIndex, int toIndex) - Removes from this list all of the elements fromIndex (inclusive) thru toIndex (exclusive).
        void trimToSize() - Trims the capacity of this ArrayList instance to be the list's current size.
  • LinkedList (API v7) (implementation: java.util.LinkedList)
    • Method Signature:
      public class LinkedList<E>
      extends AbstractSequentialList<E>
      implements List<E>, Deque<E>, Cloneable, Serializable
    • Additional features of LinkedList
      • Use instead of ArrayList if you frequently: add elements to the beginning, delete elements from the interior.
      • Implements the Queue & Deque interface and has seven additional methods: clone, addFirst, getFirst, removeFirst, addLast, getLast, and removeLast.
    • Additional Methods: (has Collection, List and these!)
      • void addFirst(E e)
      • void addLast(E e)
      • Object clone()
      • Iterator<E> descendingIterator() - Returns an iterator over the elements in this deque in reverse sequential order.
      • E element() - Retrieves, but does not remove, the head (first element) of this list.
      • E getFirst()
      • E getLast()
      • boolean offer(E e) - Adds the specified element as the tail (last element) of this list.
      • boolean offerFirst(E e) - Inserts the specified element at the front of this list.
      • boolean offerLast(E e) - Inserts the specified element at the end of this list.
      • E peek() - Retrieves, but does not remove, the head (first element) of this list.
      • E peekFirst() - Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
      • E peekLast() - Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.
      • E poll() - Retrieves and removes the head (first element) of this list.
      • E pollFirst() - Retrieves and removes the first element of this list, or returns null if this list is empty.
      • E pollLast() - Retrieves and removes the last element of this list, or returns null if this list is empty.
      • E pop() - Pops an element from the stack represented by this list. (Note: The element is removed from the list.)
      • void push(E e) - Pushes an element onto the stack represented by this list. (Top of stack!)
      • E removeFirst() - Removes and returns the first element from this list.
      • boolean removeFirstOccurrence(Object o) - Removes the first occurrence of the specified element in this list (when traversing the list from head to tail).
      • E removeLast() - Removes and returns the last element from this list.
      • boolean removeLastOccurrence(Object o) - Removes the last occurrence of the specified element in this list (when traversing the list from head to tail).

    Special purpose implementations:

    • CopyOnWriteArrayList (API v7) - well suited to maintaining event-handler lists.

Set: (interface: java.util.Set)

• Set (API v7)
• Features of Set
  • methods: only methods from the interface Collection (no new ones added).
  • duplicates: cannot contain duplicates
  • order: no indexing (no method get(<index>))
  • access: provide random access to their elements
  • nulls: allowed in HashSet & LinkedHashSet.  Not allowed in TreeSet.
• Additional Methods: (has Collection and these!)
  • None - No additional behavior (methods) is added in the Set interface from it's superclass "Collection".
• Implementations
  • java.util.HashSet (API v7) - no guaranteed order, best performance
    • Method Signature
      public class HashSet<E>
      extends AbstractSet<E>
      implements Set<E>, Cloneable, Serializable
  • java.util.LinkedHashSet (API v7) - insertion order.
    • Method Signature
      public class LinkedHashSet<E>
      extends HashSet<E>
      implements Set<E>, Cloneable, Serializable
  • java.util.TreeSet - has sorting capability (API v7) - order based on value, slower
    • Method Signature
      public class TreeSet<E>
      extends AbstractSet<E>
      implements NavigableSet<E>, Cloneable, Serializable
• Subinterfaces
  • SortedSet (API v7)
  • NavigableSet (API v7) 

Queue: (interface: java.util.Queue)

• Queue (API v7)
  • Features of Queue
    • provides additional insertion, extraction, and inspection operations
    • Queue - insertions at the rear and removals at the front. (FIFO - first-in, first-out)
    • Deque - front & back queue
• Subinterfaces
  • java.util.BlockingQueue
  • java.util.Deque - creates a double-ended queue (forwards, backwards or both). You can use a forward and backward iterator.
• Implementations
  • java.util.LinkedList - implements Queue and Deque
  • java.util.ArrayDeque - implements Queue and Deque.
  • java.util.PriorityQueue - ordered by priority (sorted)

Maps: (interface: java.util.Map)

• NOTE: Map is not a true collection but we will cover it any way.  It is technically not a Collection because it does not have the Collection class in it's heirachy.
• Map Interface (API v7)
  • Methods (interface)
    • void clear() - Removes all of the mappings from this map (optional operation).
    • boolean containsKey(Object key) - Returns true if this map contains a mapping for the specified key.
    • boolean containsValue(Object value) - Returns true if this map maps one or more keys to the specified value.
    • Set<Map.Entry<K,V>> entrySet() - Returns a Set view of the mappings contained in this map.
    • boolean equals(Object o) - Compares the specified object with this map for equality.
    • V get(Object key) - Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
    • int hashCode() - Returns the hash code value for this map.
    • boolean isEmpty() - Returns true if this map contains no key-value mappings.
    • Set<K> keySet() - Returns a Set view of the keys contained in this map.
    • V put(K key, V value) - Associates the specified value with the specified key in this map (optional operation).
    • void putAll(Map<? extends K,? extends V> m) - Copies all of the mappings from the specified map to this map (optional operation).
    • V remove(Object key) - Removes the mapping for a key from this map if it is present (optional operation).
    • int size() - Returns the number of key-value mappings in this map.
    • Collection<V> values() - Returns a Collection view of the values contained in this map.
  • Subinterfaces
    • SortedMap interface (API v7) - SortedMap.html
  • Features of Maps
    • connect unique keys with values
    • duplicates: can contain duplicate values. Not duplicate keys.
    • order (HashMap): no guarantee of order.
      order (LinkedHashMap): access by order inserted into the map.
      order (TreeMap): sorted order (order based on the constructor used).
    • access: provide random access to its keys
    • Misc info
      • replaces Hashtable.
• Implementations
  • java.util.HashMap (API v7) - public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
    • Additional Methods: (has Map)
      Object clone() - Returns a shallow copy of this HashMap instance: the keys and values themselves are not cloned.
    • Features of HashMap
      • order: no guarantee of order.
  • java.util.LinkedHashMap (API v7)
    • Additional Methods: (has Map)
      protected boolean removeEldestEntry(Map.Entry<K,V> eldest) - Returns true if this map should remove its eldest entry.
    • Features of LinkedHashMap
      • order: insertion-order
  • java.util.TreeMap (API v7) - has sorting capability.
    • Additional Methods: (has Map)
      • Map.Entry<K,V> ceilingEntry(K key) - Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.
      • K ceilingKey(K key) - Returns the least key greater than or equal to the given key, or null if there is no such key.
      • Object clone() - Returns a shallow copy of this TreeMap instance.
      • Comparator<? super K> comparator() - Returns the comparator used to order the keys in this map, or null if this map uses the natural ordering of its keys.
      • NavigableSet<K> descendingKeySet() - Returns a reverse order NavigableSet view of the keys contained in this map.
      • NavigableMap<K,V> descendingMap() - Returns a reverse order view of the mappings contained in this map.
      • Set<Map.Entry<K,V>> entrySet() - Returns a Set view of the mappings contained in this map.
      • Map.Entry<K,V> firstEntry() - Returns a key-value mapping associated with the least key in this map, or null if the map is empty.
      • K firstKey() - Returns the first (lowest) key currently in this map.
      • Map.Entry<K,V> floorEntry(K key) - Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.
      • K floorKey(K key) - Returns the greatest key less than or equal to the given key, or null if there is no such key.
      • SortedMap<K,V> headMap(K toKey) - Returns a view of the portion of this map whose keys are strictly less than toKey.
      • NavigableMap<K,V> headMap(K toKey, boolean inclusive) - Returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey.
      • Map.Entry<K,V> higherEntry(K key) - Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.
      • K higherKey(K key) - Returns the least key strictly greater than the given key, or null if there is no such key.
      • Map.Entry<K,V> lastEntry() - Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
      • K lastKey() - Returns the last (highest) key currently in this map.
      • Map.Entry<K,V> lowerEntry(K key) - Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.
      • K lowerKey(K key) - Returns the greatest key strictly less than the given key, or null if there is no such key.
      • NavigableSet<K> navigableKeySet() - Returns a NavigableSet view of the keys contained in this map.
      • Map.Entry<K,V> pollFirstEntry() - Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty.
      • Map.Entry<K,V> pollLastEntry() - Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
      • NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) - Returns a view of the portion of this map whose keys range from fromKey to toKey.
      • SortedMap<K,V> subMap(K fromKey, K toKey) - Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.
      • SortedMap<K,V> tailMap(K fromKey) - Returns a view of the portion of this map whose keys are greater than or equal to fromKey.
      • NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) - Returns a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey.
         
• Special Purpose Implementations
  • EnumMap (API v7)
  • WeakHashMap (API v7)
  • IdentityHashMap (API v7)
  • ConcurrentHashMap (API v7)

Future Items

• More sorting examples
• Conversions from one Implementation to another.
  Collection<Type> noDups = new LinkedHashSet<Type>(c); - no duplicates.  Then return the original collection.