Collection
- Containers that group multiple
items in a single unit
- Collection framework is
architecture to represent and manipulate collections in java in standard
way
- Collection FW consists of Interfaces/Implementation
Classes/Algorithm
Java Collection Interfaces:
- Foundation of Java collection
framework
- If unsupported operation is
invoked, a collection implementation throws an
UnsupportedOperationException
1.
Collection
Interface: No direct implementation of this interface.
2.
Iterator
Interface: Used to iterate over any collection
3.
Set
Interface: Can't have duplicates. Doesn't allow random access to an element. We
need to use iterator or for-each to traverse the elements of set.
4.
List Interface:
Ordered collection which can have duplicates. Elements can be accessed using
index. More like array with dynamic length.
5.
Queue Interface:
used to hold values before processing
6.
Dequeue Interface
7.
Map Interface:
key to value pair. Can’t contain duplicate keys. Key and value are 1:1. Implementation
are HashMap, TreeMap and LinkedHashMap
8.
ListIterator Interface:
Used to traverse the list in either direction, modify the list during traversal
and obtain iterator’s current position. Does not have any current element. Its
position lies in between elements. previous() returns the previous element and
next() returns the next element.
9.
SortedSet Interface:
Ordered set in ascending order
10. SortedMap Interface: Ordered map in
ascending order based in key
Collection
Interface: No direct
implementation of this interface. Common methods:
- int size(),
- boolean isEmpty(), boolean
contains(Object o), boolean add(E e), boolean remove (Object o)
- Iterator<E> iterator()
- Bulk operation : boolean
containsAll(Collection<?>), boolean addAll(Collection<? extends E> c),boolean retainAll(Collection<?> c),boolean removeAll(Collection<?> c), void clear()
Java Collection Classes:
- Usually not thread-safe
- Their iterator is fail-fast
(iterator fails as soon as structure of collection has been changed since
iteration has begun. Structural changes mean adding, removing updating any
element from collection while one thread is iterating over that
collection). ConcurrentModificationException is thrown
1.
ArrayList:
a.
Resizable-array
implementation of List Interface
b.
Allows
null and duplicates
c.
Unsynchronized
so better performance than Vector in single threaded environment
d.
Objects
added in order
e.
Default capacity=10
but can be changed using ensureCapacity(int minCapacity) method.
f.
ArrayListInterator
and ListIterator are fail-fast
g.
Supports generics
List list = new ArrayList() – not recommended
List<String> list = new ArrayList<String>();
-- recommended
2.
LinkedList:
a.
Implementation
of List and Dequeue interfaces
b.
Permits null
c.
Operations
that index into the list will traverse the list from beginning or the end,
whichever is closer to the specified index.
3.
HashMap: works
on hashing algorithm.
a.
Allows
null key and values
b.
Not ordered
collection and iterate over hashmap based on key but keys not guaranteed in
order of insertion
c.
Not
synchronized
d.
Stores entries
in multiple singly linked lists called buckets. Default number of bins is 16
and it is always power of 2
e.
Uses inner
class Node<K,V> for storing map entries
f.
Uses hashcode()
and equal() methods on keys for get() and put() operations.
g.
Not
thread-safe but can get thread-safe using Collections.synchronizedMap method at
the cost of performace
h.
How
hashmap works? http://www.journaldev.com/11560/java-hashmap
i.
Hashmap
load factor: used to figure out when hash map will be rehashed and bucket size increased.
By default, load factor=.75 and bucket/capapcity=16. Threshold=load factor*
capacity=12. When there are more than 12 mapping bucket size increases to the
next power of 2 i.e. 32. If we want to save space, we can increase load factor
to .8/.9 but get and set operation will take more time.
j.
remove()
remove the entry with this key
4.
TreeSet:
5.
HashSet: Implementation
of Set Interface backed by HashMap.
a.
No
guarantee for iteration order and permits null element.Doesn’t guarantee
insertion order
b.
Not
thread-safe but can get thread-safe using Collections.synchronizedSet method at
the cost of performace.
c.
Supports
Generics, to avoid ClassCastException at runtime
d.
Used HashMap
for storing elements, so the object should have good implementation of
hashCode() and equal() method to avoid unwanted results.
Java Collections API Algorithms
1.
Sorting
2.
Shuffling
3.
Searching
4.
Composition
5.
Min and
Max values
No comments:
Post a Comment