I have captured the important notes on Java Collectionsthrough various reference across the web which may be useful to others to have quick refresh.
The key interfaces used by the collections framework are List, Set
and Map.
The List and Set extends the Collection interface.
- Map is
an interface for a key-value map
- HashMap is
a Map that uses a hash table for its implementation
- Hashtable is
a synchronized version of HashMap
- TreeMap uses
a tree to implement a map
- ConcurrentHashMap allows for multiple threads to access it at the same
time safely
- LinkedHashMap preserves
the iteration order that things were inserted in (others don’t provide a
fixed iteration order)
Vector/Hashtable
|
ArrayList /HashMap
|
It’s synchronized by default.
|
It’s not synchronized
|
Hashtable doesn’t allow nulls.
|
HashMap allows null values as key and value.
|
Enumerations returned by Vector/Hashtable isn't fail-fast.
|
Iterator in the ArrayList/HashMap is fail-fast
|
Hashtable can’t retain the order.
|
HashMap can retain the order of objects in the Collection
with key-value pair by swaping to LinkedHashMap.
|
temporarily synchronize collections as needed:
Map myMap = Collections.synchronizedMap
(myMap);
List
myList = Collections.synchronizedList
(myList);
Array
|
List/Stack
|
It’s faster, if you know the size upfront
|
Can grow/Shrink from their initial size as needed.
|
These are more abstract than arrays and
access is restricted.
For example, a stack allows access to only
last item inserted.
|
|
Initial Capacity default is 10
It increase by factor of 1.5
|
|
Inserting
n elements
at the back of an ArrayList is
guaranteed to take total O(n) time. |
Array
|
ArrayList
|
Array is a fixed
length data structure
|
|
You can not change length of Array once
created in Java
|
ArrayList re-size itself when gets full depending upon capacity and
load factor
|
Array can contain both primitives and Objects
in Java
|
you can not store primitives in ArrayList, it can only contain Objects
|
Though automatic resize of ArrayList may slow
down insertion a bit
|
Set (HashSet , TreeSet)
|
List (ArrayList,
LinkedList, Vector)
|
A Set is a collection with
unique
elements and
prevents
duplication
within the collection.
Elements
are unordered. Need to implement SortedSet.
|
A List is a collection with
an ordered
sequence of elements
and
may
contain duplicates.
|
HashSet and TreeSet are implementations
of a Set
interface.
|
ArrayList, LinkedList
and
Vector
are
implementations of a List
interface.
(i.e. an index based)
|
A TreeSet implements
the SortedSet
|
ArrayList use RandomAccess interface , its access elements
randomly And Linked list use Queue interface , it adding and deleting elements
from both side so insertion and deletion elements are fast
ArrayList
|
LinkedList
|
It's implemented using resizable array
|
It's implemented using doublyLinkedList.
|
Array provides O(1) performance for get(index) method
but remove is costly in ArrayList as you need to rearrange all elements
|
LinkedList doesn't provide Random or index based access
and you need to iterate over linked list to retrieve any element
which is of order O(n).
|
Adding and Removing is very slow as it has to rearrange all elements.
|
Adding and Remove are easy and fast in LinkedList. adding
is O(1) operation in LinkedList.
Linked lists enable you to insert objects at the head or in the middle of the list without shuffling all subsequent elements along. |
Fast for RandomAccess
|
Slow
|
TreeSet
|
LinkedHashSet
|
HashSet
|
TreeSet
maintains sorting order.
|
For
Insertion order
|
HashSet does
not maintain any order
|
TreeSet is a
SortedSet implementation which allows it to keep elements in the sorted order
defined by either Comparable or Comparator interface.
|
||
TreeSet is bit
slower because of sorting operation it needs to perform on each insertion.
|
LinkedHashSet
is second on performance or almost similar to HashSet.
|
HashSet is
fastest.
|
TreeSet
provides guaranteed O(log(n)) time for common operations like add, remove and
contains
|
LinkedHashSet
offer constant time performance e.g. O(1) for add, contains and remove given
hash function uniformly distribute elements in bucket.
|
HashSet
offer constant time performance e.g. O(1) for add, contains and remove given
hash function uniformly distribute elements in bucket.
|
TreeSet is
backed up by NavigableMap in Java and by default it uses TreeMap
|
LinkedHashSet
is implemented using HashSet and LinkedList
|
HashSet is
backed by an HashMap instance
|
TreeSet
doesn't allow null
|
LinkedHashSet
allows null
|
HashSet allows
null
|
TreeSet uses
compareTo() method for maintaining ordering.
|
LinkedHashSet
uses equals() method in Java for comparison
|
HashSet uses
equals() method in Java for comparison
|
Map
A map can contain duplicate
values, but the keys in a map must be distinct.
HashMap,
WeakHashMap, TreeMap and Hashtable are
implementations of a Map
LinkedHashMap
extends HashMap and implements Map
A TreeMap is an ordered HashMap, which implements the SortedMap
interface.
Property
|
HashMap
|
TreeMap
|
LinkedHashMap
|
Order
|
No guarantee will remain constant over time
|
Sorted according to the natural ordering
|
Insertion-order
|
Get/Put/remove/ containskey
|
O(1)
|
O(log(n))
Because the TreeMap stores the keys based on their natural ordering, the hashCode method is not used at all. Each element put into the TreeMap rebalances the tree, so that searching, deletion, and further insertion can always be performed as efficiently as possible: O(log n) . |
O(1) + expense of
maintaining linkedlist.
|
Interfaces
|
Map
|
NavigableMap
SortedMap
Map
|
Map
|
Null
Values/Keys
|
Allowed
|
Only values
|
Allowed
|
Implementation
|
Buckets
|
Red-Black tree
|
Double-linked buckets
|
HashMap is implemented as a hash table, and there is no
ordering on keys or values.
|
TreeMap is implemented based on red-black tree structure,
and it is ordered by the key.
|
LinkedHashMap preserves the insertion order
|
Iterator
|
ListIterator
|
Enables you to traverse through a collection in
the forward direction only, for obtaining or removing elements.
|
Allows
bidirectional traversal of list and also allows the modification of elements.
|
Collection ordering
SortedSet and SortedMap interfaces
maintain sorted order.
The classes, which implement the Comparable
interface, impose natural order.
By implementing Comparable, sorting
an array of objects or a collection (List etc) is as simple as:
Arrays.sort(myArray);
Collections.sort(myCollection);
Comparable interface
|
Comparator interface
|
The “Comparable” allows
itself to compare with another
similar object (i.e. A class
that implements Comparable
becomes an object to be compared with).
|
The Comparator is used to compare two different objects.
|
The method compareTo()
is specified in the interface.
|
int compare(Object o1,
Object o2)
|
Not
possible to sort by multiple fields.
|
Can have more control by having own
Comparator class. Here we can sort by multiple fields [first by id and
then by name…]
|
References:
Hashing
No comments:
Post a Comment