Geeks With Blogs

Josh Reuben
Jumping around between programming languages, its very easy to forget what is what.

Here's my short summary of Java Collections (obviously you can go a step further with Guava !)


Collections Overview

  • In java.util package

  • generics, autoboxing/unboxing, ranged for loop, type safety.

  • Algorithms defined as static methods within the Collections class for all collections.

  • a collection can store only references, not primitive value types.

  • Autoboxing/unboxing allows passing / retrieving primative values – eg pass int to add() without having to manually wrap within an Integer.

The Collection Interfaces

Iterable --> Collection --> List

--> Queue --> Deque

--> Set --> SortedSet --> NavigatableSet

  • Dequeue – double ended

  • List – sequential

  • NavigatableSet – closest-match search

  • Set – must contain unique elements

collection interfaces:

  • Comparator defines how two objects are compared

  • Iterator / ListIterator enumerate objects within a collection.

  • RandomAccess - list indicates it supports efficient, random access to its elements.

the collection interfaces allow some methods to be optional.

All built-in collections are modifiable.

Collection Interface

  • extends Iterable interface

  • Methods: add(), addAll(),remove(), removeAll(), retainAll(),clear(), contains(), containsAll(), isEmpty(), size(), toArray()

  • equals() - compare 2 collections – depends on implementation - some compare values of elements, others compare references to those elements.

  • iterator(), returns an iterator to a collection.

List Interface

  • extends Collection – insertions and indexers. Methods:

  • add(E) / addLast() / add(int, E) / addAll(int, Collection) - insert elements at specified index.

  • get / set(index)

  • indexOf() / lastIndexOf() - find index of an object

  • subList() - obtain a sublist of a list

Set Interface

  • extends Collection to require unique elements.

  • add() - returns false if an attempt is made to add duplicate elements to a set.

SortedSet Interface

  • extends Set to be sorted in ascending order.

  • first() / last() - obtain first / last object in the set

  • subSet(first,last) / headSet(last) / tailSet(first) - obtain a subset of a sorted set

NavigableSet Interface

  • extends SortedSet - retrieval of elements based on the closest match to a given value or values.

Queue Interface

  • extends Collection to be FIFO. Can specify other ordering criteria. elements can only be removed from the head

  • poll() - get and remove element - returns null if the queue is empty

  • remove() - get and remove element - throws an exception if the queue is empty.

  • element() - get but dont remove element - throws an exception if the queue is empty.

  • peek() - get but dont remove element - returns null if the queue is empty

  • offer() - attempts to add an element to a queue. Because some queues have a fixed length and might be full, offer() can fail.

Deque Interface

  • a double-ended queue. D can function as standard, FIFO queues or LIFO stacks.

  • push() / pop() - to function as a stack.

  • descendingIterator() - returns an iterator that returns elements in reverse order. can be capacity-restricted.

  • addFirst() / offerFirst() / addLast() / offerLast() - add elements to the start / end of a list

  • getFirst() / peekFirst() / getLast() / peekLast() - obtain first / last element

  • removeFirst() / pollFirst() / removeLast() / pollLast() - remove first / last element

The Collection Classes

Some are abstract and some are concrete collections. possible to obtain synchronized versions.

AbstractCollection --> AbstractList --> AbstractSequentialList --> LinkedList

--> ArrayList

--> AbstractQueue --> ArrayDeque

--> PriorityQueue

--> AbstractSet --> EnumSet

--> HashSet --> LinkedHashSet

--> TreeSet

several legacy classes, such as Vector, Stack, and Hashtable

ArrayList Class

  • extends AbstractList implements List

  • dynamic array wrapper

  • ensureCapacity() - manually increase capacity

  • trimToSize() - reduce size of underlying array

  • toArray() - Obtain an Array from an ArrayList --> faster processing times.

    ArrayList<Integer> al = new ArrayList<Integer>();
    Integer ia[] = new Integer[al.size()];
    ia = al.toArray(ia);

LinkedList Class

  • extends AbstractSequentialList implements List, Deque, Queue

HashSet Class

  • extends AbstractSet implements Set

  • uses a hash table for storage - informational content of a key is used to automatically determine a unique hash code used as the index.

  • allows the execution time of add(), contains(), remove(), and size() to remain constant even for large sets.

  • The fill ratio (range: 0.0 – 1.0, default 0.75) - determines how full the hash set can be before it is resized upward.

  • does not guarantee the order of its elements, because the process of hashing doesn’t usually lend itself to the creation of sorted sets. If you need sorted storage, then another collection, such as TreeSet, is a better choice.

LinkedHashSet Class

  • extends HashSet

  • maintains a linked list of the entries in the set, in the order in which they were inserted --> insertion-order iteration over the set.

TreeSet Class

  • extends AbstractSet implements NavigableSet

  • uses a btree for storage - Objects are stored in sorted, ascending order --> fast access and retrieval

PriorityQueue Class

  • extends AbstractQueue implements Queue

  • prioritized based on the queue’s comparator - If no custom comparator is specified in ctor, then default comparator for the item type is used.

  • obtain a reference to the comparator by calling comparator() - If natural ordering is used for the invoking queue, null is returned.

ArrayDeque Class

extends AbstractCollection implements Deque

using it to create a stack:

    ArrayDeque<String> adq = new ArrayDeque<String>();
    adq.push("A");
    while(adq.peek() != null)
       System.out.print(adq.pop() + " ");

EnumSet Class

extends AbstractSet implements Set

restricts keys to an enum type. no public ctor - uses factory methods to create instances.

Iterator Interface

  • Iterator interface – enumerator - nables cycling through a collection, obtaining or removing elements

  • Iterable interface – ranged for over each enumerator element

  • ListIterator interface - extends Iterator , allows bidirectional traversal of a list, and the modification of elements.

Using an Iterator - Each of the collection classes provides an iterator() method that returns an iterator to the start of the collection. Loop using bool hasNext() and access each element by calling next().

Iterator<string> itr = als.iterator;

while(itr.hasNext()) {

String s = itr.next();

The For-Each Alternative to Iteratorsconvenient, but forward-only, unmodifiable:

for (string s : als) {

}

RandomAccess Interface

use instanceof to determine if a class implements an interface. implemented by ArrayList.

Maps

stores associations between key/value object pairs.

doesnt implement Iterable interface --> need to obtain a collection-view of a map in order to iterate.

The Map Interfaces

Map --> SortedMap --> NavigableMap

Map Interface
  • get() / put() - basic operations

  • entrySet() / keySet() / values() - obtain a collection-view Set of a map KVPs / keys / values

  • Map.Entry Interface - a KVP.

SortedMap Interface
  • extends Map

  • entries are maintained in ascending order of keys

  • headMap() / tailMap() / subMap() - obtain a submap

NavigableMap Interface
  • extends SortedMap

  • supports retrieval of entries based on the closest match to a given key or keys.

The Map Classes

AbstractMap --> EnumMap

--> HashMap --> LinkedHashMap

--> TreeMap

--> WeakHashMap

--> IdentityHashMap

AbstractMap Class- base

WeakHashMap Class- uses weak keys - allow a map element to be GC'd when its key is unused.

HashMap Class - uses a hash table to store the map – fast, unordered.

    HashMap<String, Double> hm = new HashMap<String, Double>();
    hm.put("blah", new Double(1234.56));
    Set<Map.Entry<String, Double>> set = hm.entrySet();.
    for(Map.Entry<String, Double> me : set) {
      System.out.print(me.getKey() + ": " + me.getValue());
TreeMap Class
  • extends AbstractMap implements NavigableMap

  • sorted in ascending key order or specified by a Comparator --> rapid retrieval

LinkedHashMap Class
  • extends HashMap

  • maintains a linked list of entries in the map, in insertion order (Order=true) / access order (Order=false)

  • methods: removeEldestEntry(), put() / putAll()

IdentityHashMap Class

uses reference equality when comparing elements. not for general use.

EnumMap Class

specifically for use with keys of an enum type.

Comparators

Comparator Interface

  • implement for applying custom order to collections

  • compare() / equals() - returns 0 if 2 objects are equal, 1 if obj1 is greater than obj2, else -1.

  • throws ClassCastException if the types of the objects are not compatible for comparison.

  • compareTo() reverse compares 2 strings

The Collection class Algorithms

  • Collections class defines static methods that work against various collections

  • checked* methods - dynamic typesafe view of a collection - ensures contains valid elements: checkedCollection(), checkedSet(), checkedList(), checkedMap().

  • synchronizedList() / synchronizedSet(), - get threadsafe (synchronized) copies of the various collections. iterators to synchronized collections must be used within synchronized blocks.

  • Unmodifiable* methods - returns unmodifiable views of the various collections

  • static immutable variables: EMPTY_SET, EMPTY_LIST, EMPTY_MAP.

  • reverseOrder() - returns a Comparator that reverses the comparison

  • shuffle() - randomize order

  • min(), max()

Array Methods

  • asList() - returns a List that is backed by a specified array (not a copy)

  • binarySearch() - find a specified value in a sorted array

  • copyOf() / copyOfRange() - returns a copy of an array

  • equals() - returns true if two arrays are equivalent

  • deepEquals() - determine if two arrays that contain nested arrays are equal.

  • fill() - assigns a value to all elements in an array.

  • sort() - sorts an array in ascending order. can specify a range within array to sort.

The Legacy Classes / Interfaces

Dictionary, Hashtable, Properties, Stack, Vector


The Concurrent Collections

  • ArrayBlockingQueue

  • ConcurrentHashMap

  • ConcurrentLinkedDeque /ConcurrentLinkedQueue

  • ConcurrentSkipListMap / ConcurrentSkipListSet

  • CopyOnWriteArrayList / CopyOnWriteArraySet

  • DelayQueue

  • LinkedBlockingDeque/ LinkedBlockingQueue / LinkedTransferQueue

  • PriorityBlockingQueue

  • SynchronousQueue

Posted on Sunday, March 1, 2015 3:51 PM Java | Back to top


Comments on this post: Java Collections Refresher

# re: Java Collections Refresher
Requesting Gravatar...
There are lots of important details that I learned from this information. - Dr. Thomas G. Devlin MD, PhD
Left by James Michael on Dec 20, 2016 9:22 AM

Your comment:
 (will show your gravatar)


Copyright © JoshReuben | Powered by: GeeksWithBlogs.net