jump to navigation

Collections Framework July 28, 2005

Posted by Coolguy in J2SE.
trackback

Collections: A collection is an object that groups multiple
elements into a single unit. Collections are used to store, retrieve,manipulate, and communicate aggregate data.

Collections Framework
A collections framework is a unified architecture for representing and manipulating collections.All collections frameworks contain:

  • Interfaces: abstract data types representing collections. Interfaces allow collections to be manipulated independently of the details of their representation.
  • Implementations: concrete implementations of the collection interfaces. In essence, these are reusable data structures.
  • Algorithms: methods that perform useful computations, such as searching
    and sorting, on objects that implement collection interfaces.

Benefits of the Java Collections Framework

  • Reduces programming effort
  • Increases program speed and quality
  • Fosters software reuse

Collection interfaces:
Core collection interfaces are:

  • Collection
  • Set
  • List
  • Queue
  • Map
  • SortedSet
  • SortedMap

Collection

  • A collection represents a group of objects, known as its elements.
  • Classes that implement the Collection interface store objects as elements rather than primitives.This approach has the drawback that creating objects has a performance overhead and the elements must be cast back from Object to the appropriate type before being used.
  • It means that the collections do not check that the elements are all of the same type, as an object can be just about anything.
  • Some types of collections allow duplicate elements, and others do not.
  • Some are ordered and others unordered.
  • Platform doesn’t provide any direct implementations of this interface but provides implementations of more specific subinterfaces, such as Set and List
  • There are two ways to traverse collections:
    • for-each construct
    • using iterators

  • The for-each construct allows you to concisely traverse a collection or array using a for loop.
  • An Iterator is an object that enables you to traverse through a collection, and to remove elements from the collection selectively, if desired.
  • Use an iterator instead of the for-each construct when:
    • You need to remove the current element
    • You need to replace elements in a list or array as you traverse it
    • You need to iterate over multiple collections in parallel
  • Collection Interface Bulk Operations:
    • containsAll
    • addAll
    • removeAll
    • retainAll
    • clear

Set

  • A collection that cannot contain duplicate elements.
  • It thus matches nicely onto concepts such as a record set returned from a relational database
  • Allows at most one null element.
  • Platform contains three general-purpose Set implementations:

    Name Storage Order Performance
    HashSet Hash table None best-performing
    TreeSet Tree Based on their values substantially slower than HashSet
    LinkedHashSet Hash table with a linked list running through it Insertion-order Slightly higher than HashSet

  • Set Interface Operations:
    • size
    • isEmpty
    • contains
    • add
    • remove
    • iterator
    • containsAll
    • addAll
    • removeAll
    • retainAll

List

  • List is an ordered collection
  • Allows duplicate elements.
  • Multiple null elements are allowed
  • The user of a List generally has precise control over where in the List each element is inserted.
  • User can access elements by their integer index (position).
  • Platform contains two general-purpose List implementations:
    • ArrayList : Generally the better-performing implementation.
    • LinkedList: Offers better performance under certain circumstances.
  • Has methods for:
    • Positional Access: get, set, add,addAll and remove
    • Search:indexOf,lastIndexOf
    • List Iteration:listIterator
    • Range-view: subList
  • A List l may be sorted as follows:
    Collections.sort(l);
    • If the list consists of String elements, it will be sorted into alphabetical order
    • If it consists of Date elements, it will be sorted into chronological order.
    • The Comparable interface consists of a single method:
      public interface Comparable {
      public int compareTo(T o);
      }

Queue

  • A collection used to hold multiple elements prior to processing.
  • Besides basic Collection operations, queues provide additional insertion,extraction, and inspection operations.
  • Queues typically order elements in a FIFO (first-in-first-out) manner
  • Queues Interface Operations:
    • element
    • offer
    • peek
    • poll
    • remove

Map

  • An object that maps keys to values
  • Maps cannot contain duplicate keys.Each key can map to at most one value
  • Platform contains three general-purpose Map implementations: HashMap,TreeMap, and LinkedHashMap.
  • Map Interface Operations:
    • put
    • get
    • remove
    • containsKey
    • containsValue
    • size
    • isEmpty
    • putAll
    • clear
    • keySet
    • values
    • entrySet

SortedSet

  • A Set that maintains its elements in ascending order
  • Several additional operations are provided to take advantage of the ordering.
  • Sorted sets are used for naturally ordered sets, such as word lists.
  • SortedSet interface provides operations for:
    • Range view: Allows arbitrary range operations on the sorted set.
    • Endpoints: Returns the first or last element in the sorted set.
    • Comparator access: Returns the Comparator, if any, used to sort the set.

SortedMap

  • A Map that maintains its mappings in ascending order,sorted according to the keys’ natural order, or according to a Comparator provided at SortedMap creation time
  • Sorted maps are used for naturally ordered collections of key/value pairs,such as dictionaries
  • Map interface provides operations for:
    • Range view: Allows arbitrary range operations on the sorted set.
    • Endpoints: Returns the first or last element in the sorted set.
    • Comparator access: Returns the Comparator, if any, used to sort the set.

Set and Map collections ensure uniqueness,List do not ensure uniqueness but are sorted (ordered)

Implementations

  • Collections Framework provides several general-purpose implementations of the Set, List , and Map interfaces.
  • In each case, one implementation HashSet, ArrayList, and HashMap is clearly the one to use for most applications
Interfaces General-purpose Implementations
HashTable Resizablearray Tree Linked List Hash Table + LinkedList
Set HashSet TreeSet LinkedHashSet
List ArrayList LinkedList
Queue
Map HashMap TreeMap LinkedHashMap

Set Implementations

  • HashSet is much faster than TreeSet but offers no ordering guarantees.
  • LinkedHashSet is in some sense intermediate between HashSet and TreeSet.
  • The only reason TreeSet exists is because it maintains its elements in sorted order, so you only use it when you need a sorted list

List Implementations

  • The best approach is probably to choose ArrayList as default, and to change to LinkedList if there are performance problems due to many insertions and removals from the middle of the list.
  • While working with a fixed size group of elements array is best

Map Implementations

  • When choosing between implementations of Map, the size of the map is what most strongly affects performance.
  • When you are using a map your first choice should be HashMap, and only if you need a constantly sorted map will you need a TreeMap.

Queue Implementations

  • LinkedList implements the Queue interface, providing first-in-first-out queue operations for add, poll, and so on.

Algorithms

  • Are pieces of reusable functionality provided by the Java platform. All of them come from the Collections class, and all take the form of static methods whose first argument is the collection on which the operation is to be performed
  • Common algo’s are:
    • Sorting: Reorders a List
    • Shuffling: Destroys any trace of order that may have been present in a List
    • Routine Data Manipulation on lists:reverse,fill,copy,swap,addAll
    • Searching in list: binarySearch,
    • Composition on collections: frequency,disjoint
    • Finding Extreme Values in collection: min and max
Advertisements

Comments»

No comments yet — be the first.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: