Describe core collection interfaces.

The following list describes the core collection interfaces:
  • Collection — the root of the collection hierarchy. A collection represents a group of objects known as its elements. The Collection interface is the least common denominator that all collections implement and is used to pass collections around and to manipulate them when maximum generality is desired. Some types of collections allow duplicate elements, and others do not. Some are ordered and others are unordered. The Java platform doesn't provide any direct implementations of this interface but provides implementations of more specific subinterfaces, such as Set and List. Also see The Collection Interface section.
  • Set — a collection that cannot contain duplicate elements. This interface models the mathematical set abstraction and is used to represent sets, such as the cards comprising a poker hand, the courses making up a student's schedule, or the processes running on a machine. See also The Set Interface section.
  • List — an ordered collection (sometimes called a sequence). Lists can contain duplicate elements. The user of a List generally has precise control over where in the list each element is inserted and can access elements by their integer index (position). If you've used Vector, you're familiar with the general flavor of List. Also see The List Interface section.
  • Queue — a collection used to hold multiple elements prior to processing. Besides basic Collection operations, a Queue provides additional insertion, extraction, and inspection operations.
  • Queues typically, but do not necessarily, order elements in a FIFO (first-in, first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator or the elements' natural ordering. Whatever the ordering used, the head of the queue is the element that would be removed by a call to remove or poll. In a FIFO queue, all new elements are inserted at the tail of the queue. Other kinds of queues may use different placement rules. Every Queue implementation must specify its ordering properties. Also see The Queue Interface section.
  • Map — an object that maps keys to values. A Map cannot contain duplicate keys; each key can map to at most one value. If you've used Hashtable, you're already familiar with the basics of Map. Also see The Map Interface section.
The last two core collection interfaces are merely sorted versions of Set and Map:
  • 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 and membership rolls. Also see The SortedSet Interface section.
  • SortedMap — a Map that maintains its mappings in ascending key order. This is the Map analog of SortedSet. Sorted maps are used for naturally ordered collections of key/value pairs, such as dictionaries and telephone directories. Also see The SortedMap Interface section.

What are legacy classes and interfaces present  in Collections framework ?
  • Enumeration ---Interface
  • Dictonary ------Abstract class
  • Hashtable -----Concrete class
  • Properties -----Concrete class
  • Vector -----Concrete class
  • Stack  -----Concrete class 
  • Basic collection types
    The first part of the decision is choosing what "basic category" of organisation or functionality your data needs to have. The broad types are as follows:
    Collection typeFunctionalityTypical uses
    List
    • Essentially a variable-size array;
    • You can usually add/remove items at any arbitrary position;
    • The order of the items is well defined (i.e. you can say what position a given item goes in in the list).
    Most cases where you just need to store or iterate through a "bunch of things" and later iterate through them.
    Set
    • Things can be "there or not"— when you add items to a set, there's no notion of how many times the item was added, and usually no notion of ordering.

    • Remembering "which items you've already processed", e.g. when doing a web crawl;
    • Making other yes-no decisions about an item, e.g. "is the item a word of English", "is the item in the database?" , "is the item in this category?" etc.
    Map
    • Stores an association or mapping between "keys" and "values"
    Used in cases where you need to say "for a given X, what is the Y"? It is often useful for implementing in-memory caches or indexes. For example:
    • For a given user ID, what is their cached name/User object?
    • For a given IP address, what is the cached country code?
    • For a given string, how many instances have I seen?
    Queue
    • Like a list, but where you only ever access the ends of the list (typically, you add to one end and remove from the other).

    • Often used in managing tasks performed by different threads in an application (e.g. one thread receives incomming connections and puts them on a queue; other "worker" threads take connections off the queue for processing);
    • For traversing hierarchical structures such as a filing system, or in general where you need to remember "what data to process next", whilst also adding to that list of data;
    • Related to the previous point, queues crop up in various algorithms, e.g. build the encoding tree for Huffman compression.
     

    Which Java List to use?

    A list is the simplest of structures. It keeps its elements in the same order in which they are inserted and allows duplicates. There are essentially three underlying list classes:
    ClassFeatures/implementationWhen to use
    ArrayList
    • Allows elements to be efficiently read by index.
    • Adding/removing the last element is efficient.
    • Not synchronized in any way.
    In most cases.
    LinkedList
    • First and last elements can be accessed efficiently;
    • Other elements cannot be efficiently accessed by index;
    • Not synchronized in any way.
    Effectively, functions as a non-synchronized queue. In practice, rarely used: when you need a queue, you often need it to be concurrent or to provide other functionality; other implementations are often more useful.
    CopyOnWriteArrayList
    • Allows safe concurrent access;
    • Reads are efficient and non-blocking;
    • Modifications are not efficient (since a brand new copy of the list is taken each time).
    Where you need concurrent access and where frequency of reads far outweights frequency of modifications.

    If you need concurrent access to a list and CopyOnWriteArrayList is not appropriate (either because the list is large or because reads don't outnumber writes), then the best you can really do is place a synchronized wrapper around an ordinary ArrayList:
    List l = Collections.synchronizedList(new ArrayList());
    Note that this gives you thread-safe access, but it's not truly concurrent in the sense that each access to the list will lock the entire list during the access.
    Remember if you do this that you must always synchronize on the list while iterating over it (and in some cases this could be bad for concurrency). In practice, you should think carefully whether this type of list makes much sense. If a list is being continually altered by different threads, for example, what value do the individual index numbers really have?

    Which Java Map to use?

    The JDK provides various Map implementations depending on:
  • whether you need to maintain the keys in sorted order, in some fixed order or whether no particular order is required;
  • whether you require efficient concurrent access (i.e. where multiple threads can access the map efficiently and can perform atomic updates on the map).
Depending on these requirements, the various Map implementations are as follows:
Ordering of keysNon-concurrentConcurrent
No particular orderHashMapConcurrentHashMap
SortedTreeMapConcurrentSkipListMap
FixedLinkedHashMap

Which Java Set to use?

Conceptually, a set serves to record whether or not an object belongs to a particular group. But a set is usually implemented as a degenerate type of map, in which each item added to the set is mapped to some special object meaning "present in the set". Therefore, especially in the non-current case, the choices in deciding which set implementation to use are largely similar to in the previous section: do you need a predictable iteration order and/or concurrent access? The available Set implementations are then as follows:
Ordering of keysNon-concurrentConcurrent
No particular orderHashSet
SortedTreeSetConcurrentSkipListSet
FixedLinkedHashSetCopyOnWriteArraySet

Perhaps surprisingly, Java doesn't provide a set implementation based on ConcurrentHashMap, though you could make such a subclass trivially yourself. Another option that requires no code is to use a ConcurrentSkipListSet, although you will be paying (in efficiency) for sorting that you don't really need1.
As with CopyOnWriteArrayList (on which it is actually based), the CopyOnWriteArraySet class is suited to cases where the set is relatively small and reads far outweight writes. Any modification of the set is expensive (since a brand new copy is created each time), but reads are non-blocking.

No comments:

Post a Comment