What are Collection related
features in Java 8?
Java 8 has brought major changes in the Collection
API. Some of the changes are:
·
Java Stream API
collection classes for supporting sequential as well as parallel processing
·
Iterable interface is extended with forEach() default
method that we can use to iterate over a collection. It is very helpful when
used with lambda expressions because it’s argument Consumer is a function
interface.
·
Miscellaneous
Collection API improvements such as forEachRemaining(Consumer
action)method in Iterator interface, Map replaceAll(), compute(), merge() methods.
Collection Framework is representing a unified
architecture for storing and manipulating the group of objects. Using
collection framework, you can store the objects as a list or
as a set or as a queue or as a map and
perform operations like adding an object or removing an object or sorting
the objects without much hard work.
Some of the benefits of collections framework are
1.
Reduced development
effort by using core collection classes rather than implementing our own
collection classes.
2. Code quality is enhanced with the use of well tested
collections framework classes.
3. Reduced effort for code maintenance by using
collection classes shipped with JDK.
4.
Reusability and
Interoperability
Java 1.5 came with Generics and all collection
interfaces and implementations use it heavily. Generics allow us to provide the
type of Object that a collection can contain, so if you try to add any element
of other type it throws compile time error.
This avoids ClassCastException at Runtime because you will get the error at compilation. Also Generics make code clean since we don’t need to use casting and instanceof operator.
This avoids ClassCastException at Runtime because you will get the error at compilation. Also Generics make code clean since we don’t need to use casting and instanceof operator.
Collection is the root of the collection hierarchy. A
collection represents a group of objects known as its elements. The Java
platform doesn’t provide any direct implementations of this interface.
Set is a collection that cannot contain duplicate
elements. This interface models the mathematical set abstraction and is used to
represent sets, such as the deck of cards.
List is an ordered collection and can contain
duplicate elements. You can access any element from it’s index. List is more
like array with dynamic length.
A Map is an object that maps keys to values. A map
cannot contain duplicate keys: Each key can map to at most one value.
Why Collection doesn’t extend Cloneable and Serializable interfaces?
“there is no need to do it “. Extending
an interface simply means that you are creating a subtype of interface, in
other words a more specialized behavior and Collection interface is not
expected to do what Cloneable and Serializable interfaces do.
Another reason is that not everybody will have a
reason to have Cloneable collection because if it has very large data, then
every unnecessary clone operation will consume a big memory.
Beginners might use it without knowing the consequences.
Another reason is that Cloneable and
Serializable are very specialized behavior and so should be
implemented only when required. For example, many concrete classes in
collection implement these interfaces. So if you want this feature. use these
collection classes otherwise use their alternative classes.
“because they are incompatible “. Collection
has a method add(Object o). Map cannot have such method because it need
key-value pair. There are other reasons also such as Map supports keySet,
valueSet etc. Collection classes does not have such views.
Due to such big differences, Collection interface
was not used in Map interface, and it was built in separate hierarchy.
Iterator is an interface. It is found in java.util
package. It provides methods to iterate over any Collection.
The main difference between Iterator and Enumeration
is that Iterator has remove() method while Enumeration doesn't.
Hence , using Iterator we can manipulate objects by adding and removing the objects from the collections. Enumeration behaves like a read only interface as it can only traverse the objects and fetch it.
Hence , using Iterator we can manipulate objects by adding and removing the objects from the collections. Enumeration behaves like a read only interface as it can only traverse the objects and fetch it.
Why there is not method like Iterator.add() to add elements to the
collection?
The sole purpose of an Iterator is to enumerate
through a collection. All collections contain the add() method to serve your
purpose. There would be no point in adding to an Iterator because the collection
may or may not be ordered. And add() method can not have same
implementation for ordered and unordered collections.
What are different ways to iterate over a list?
You can iterate over a list using following ways:
- Iterator loop
- For loop
- For loop (Advance)
- While loop
What is the difference between List and Set?
Set contain only unique elements while List can contain duplicate elements.
Set is unordered while List is ordered. List maintains the order in which the objects are added.
Set is unordered while List is ordered. List maintains the order in which the objects are added.
List does not prevent inserting null elements (as
many you like), but Set will allow only one null element.
Difference between Vector and ArrayList?
- All the methods of Vector is synchronized. But, the methods of
ArrayList is not synchronized.
- Vector is a Legacy class added in first release of JDK. ArrayList
was part of JDK 1.2, when collection framework was introduced in java.
- By default, Vector doubles the size of its array when it is re-sized internally. But, ArrayList increases by half of its size when it is re-sized.
ArrayList and LinkedList both implement List
interface but there are some differences between them.
1.
ArrayList is an
index based data structure backed by Array, so it provides random access to its
elements with performance as O(1) but LinkedList stores data as list of nodes
where every node is linked to its previous and next node. So even though there
is a method to get the element using index, internally it traverse from start
to reach at the index node and then return the element, so performance is O(n)
that is slower than ArrayList.
2. Insertion, addition or removal of an element is
faster in LinkedList compared to ArrayList because there is no concept of
resizing array or updating index when element is added in middle.
3.
LinkedList
consumes more memory than ArrayList because every node in LinkedList stores
reference of previous and next elements.
How HashSet store elements?
You must know that HashMap store key-value pairs,
with one condition i.e. keys will be unique. HashSet uses Map’s this feature to
ensure uniqueness of elements. In HashSet class, a map declaration is as below:
private transient HashMap
//This is added as value for each key
private static final Object PRESENT = new
Object();
|
So when you store an element in HashSet, it
stores the element as key in map and “PRESENT” object as value. (See
declaration above).
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
|
Can a null element added to a TreeSet or HashSet?
As you see, There is no null check in add() method
in previous question. And HashMap also allows one null key, so one “null” is
allowed in HashSet.
TreeSet uses the same concept as HashSet for
internal logic, but uses NavigableMap for storing the elements.
private transient NavigableMap
// Dummy value to associate with an Object in the
backing Map
private static final Object PRESENT = new
Object();
|
NavigableMap is subtype of SortedMap which does not
allow null keys. So essentially, TreeSet also does not support null
keys. It will throw NullPointerException if you try to add null element in
TreeSet.
What is the
difference between Queue and Stack?
Queue is a data structure which is based on FIFO (first in first out) property. An example of Queue in real world is buying movie tickets in the multiplex or cinema theatres.
Stack is a data structure which is based on LIFO (last in first out) property. An example of Stack in real world is insertion or removal of CD from the CD case.
Queue is a data structure which is based on FIFO (first in first out) property. An example of Queue in real world is buying movie tickets in the multiplex or cinema theatres.
Stack is a data structure which is based on LIFO (last in first out) property. An example of Stack in real world is insertion or removal of CD from the CD case.
1.
We can use
Iterator to retrieve Set and List collections whereas ListIterator can be used
with Lists only.
2. Iterator can retrieve in forward direction only
whereas ListIterator can be used to retrieve in both the directions.
3.
ListIterator
inherits from Iterator interface and comes with extra functionalities like
adding an element, replacing an element, getting index position for previous
and next elements.
We can iterate over a list in two different ways –
using iterator and using for-each loop.
List strList = new
ArrayList<>();
//using for-each loop
for(String obj : strList){
System.out.println(obj);
}
//using iterator
Iterator it = strList.iterator();
while(it.hasNext()){
String obj
= it.next();
System.out.println(obj);
}
Using iterator is more thread-safe because it makes
sure that if underlying list elements are modified, it will
throw ConcurrentModificationException.
Iterator fail-fast property checks for any
modification in the structure of the underlying collection everytime we try to
get the next element. If there are any modifications found, it
throwsConcurrentModificationException. All the implementations of Iterator in
Collection classes are fail-fast by design except the concurrent collection
classes like ConcurrentHashMap and CopyOnWriteArrayList.
Iterator fail-safe property work with the clone of
underlying collection, hence it’s not affected by any modification in the
collection. By design, all the collection classes
in java.util package are fail-fast whereas collection classes
in java.util.concurrent are fail-safe.
Fail-fast iterators throw ConcurrentModificationException whereas fail-safe iterator never throws ConcurrentModificationException.
Fail-fast iterators throw ConcurrentModificationException whereas fail-safe iterator never throws ConcurrentModificationException.
We can use concurrent collection classes to
avoid ConcurrentModificationException while iterating over a
collection, for example CopyOnWriteArrayList instead of ArrayList.
What is the difference between HashSet and TreeSet ?
Main differences between HashSet and TreeSet are :
a. HashSet maintains the inserted elements in random order while TreeSet maintains elements in the sorted order
b. HashSet can store null object while TreeSet cannot store null object.
Main differences between HashSet and TreeSet are :
a. HashSet maintains the inserted elements in random order while TreeSet maintains elements in the sorted order
b. HashSet can store null object while TreeSet cannot store null object.
HashMap stores key-value pair
in Map.Entry static nested class implementation. HashMap works on
hashing algorithm and uses hashCode() and equals() method
in put and get methods.
When we call put method by passing
key-value pair, HashMap uses Key hashCode() with hashing to find out the index
to store the key-value pair. The Entry is stored in the LinkedList, so if there
are already existing entry, it uses equals() method to check if the passed key
already exists, if yes it overwrites the value else it creates a new entry and
store this key-value Entry.
When we call get method by passing Key,
again it uses the hashCode() to find the index in the array and then use
equals() method to find the correct Entry and return it’s value.
The other important things to know about HashMap are
capacity, load factor, threshold resizing. HashMap initial default capacity
is 16 and load factor is 0.75. Threshold is capacity
multiplied by load factor and whenever we try to add an entry, if map size is
greater than threshold, HashMap rehashes the contents of map into a new array
with a larger capacity. The capacity is always power of 2, so if you know that
you need to store a large number of key-value pairs, for example in caching
data from database, it’s good idea to initialize the HashMap with correct
capacity and load factor.
HashMap uses Key object hashCode() and equals()
method to determine the index to put the key-value pair. These methods are also
used when we try to get value from HashMap. If these methods are not
implemented correctly, two different Key’s might produce same hashCode() and
equals() output and in that case rather than storing it at different location,
HashMap will consider them same and overwrite them.
Similarly all the collection classes that doesn’t
store duplicate data use hashCode() and equals() to find duplicates, so it’s
very important to implement them correctly. The implementation of equals() and
hashCode() should follow these rules.
- If o1.equals(o2), then o1.hashCode() ==
o2.hashCode()should always be true.
- If o1.hashCode() == o2.hashCode is true, it doesn’t mean
that o1.equals(o2) will be true.
Can we
replace Hashtable with ConcurrentHashMap?
Yes, we can replace Hashtable with ConcurrentHashMap
and that's what suggested in Java documentation of ConcurrentHashMap. but you
need to be careful with code which relies on locking behavior of Hashtable.
Since Hashtable locks whole Map instead of a portion of Map, compound
operations like if(Hashtable.get(key) == null) put(key, value) works in
Hashtable but not in concurrentHashMap. instead of this use putIfAbsent()
method of ConcurrentHashMap
HashMap and Hashtable both implements Map interface
and looks similar, however there are following difference between HashMap and
Hashtable.
1.
HashMap allows
null key and values whereas Hashtable doesn’t allow null key and values.
2. Hashtable is synchronized but HashMap is not
synchronized. So HashMap is better for single threaded environment, Hashtable
is suitable for multi-threaded environment.
3. LinkedHashMap was introduced in Java 1.4 as a
subclass of HashMap, so in case you want iteration order, you can easily switch
from HashMap to LinkedHashMap but that is not the case with Hashtable whose
iteration order is unpredictable.
4. HashMap provides Set of keys to iterate and hence
it’s fail-fast but Hashtable provides Enumeration of keys that doesn’t support
this feature.
5.
Hashtable is
considered to be legacy class and if you are looking for modifications of Map
while iterating, you should use ConcurrentHashMap
For inserting, deleting, and locating elements in a
Map, the HashMap offers the best alternative. If, however, you need to traverse
the keys in a sorted order, then TreeMap is your better alternative. Depending
upon the size of your collection, it may be faster to add elements to a
HashMap, then convert the map to a TreeMap for sorted key traversal.
What are different Collection views provided by Map interface?
Map interface provides 3 views of key-values pairs
stored in it:
- key set view
- value set view
- entry set view
All the views can be navigated using iterators.
What is the difference between HashMap and ConcurrentHashMap?
Main differences between HashMap and ConcurrentHashMap are:
a. HashMap is not synchronized while ConcurrentHashMap is synchronized.
b. HashMap can have one null key and any number of null values while ConcurrentHashMap does not allow null keys and null values
Main differences between HashMap and ConcurrentHashMap are:
a. HashMap is not synchronized while ConcurrentHashMap is synchronized.
b. HashMap can have one null key and any number of null values while ConcurrentHashMap does not allow null keys and null values
How do you use a custom object as key in Collection classes like
HashMap ?
If one is using the custom object as key then one needs to override equals() and hashCode() method and one also need to fulfil the contract.
If you want to store the custom object in the SortedCollections like SortedMap then one needs to make sure that equals() method is consistent to the compareTo() method. If inconsistent, then collection will not follow their contracts, that is, Sets may allow duplicate elements.
If one is using the custom object as key then one needs to override equals() and hashCode() method and one also need to fulfil the contract.
If you want to store the custom object in the SortedCollections like SortedMap then one needs to make sure that equals() method is consistent to the compareTo() method. If inconsistent, then collection will not follow their contracts, that is, Sets may allow duplicate elements.
What is hash-collision in Hashtable? How it was handled in Java?
In Hashtable , if two different keys have the same hash value then it lead to hash -collision. A bucket of type linkedlist used to hold the different keys of same hash value.
In Hashtable , if two different keys have the same hash value then it lead to hash -collision. A bucket of type linkedlist used to hold the different keys of same hash value.
What is EnumSet?
java.util.EnumSet is Set implementation to use
with enum types. All of the elements in an enum set must come from a single
enum type that is specified, explicitly or implicitly, when the set is created.
EnumSet is not synchronized and null elements are not allowed. It also provides
some useful methods like copyOf(Collection c), of(E first, E… rest) and
complementOf(EnumSet s).
What is IdentityHashMap?
IdentityHashMap is a class present in java.util package. It implements the Map interface with a hash table , using reference equality instead of object equality when comparing keys and values.In other words , in IdentityHashMap two keys k1 and k2 are considered equal if only if (k1==k2).
IdentityHashMap is not synchronized.
Iterators returned by the iterator() method are fail-fast , hence , will throw ConcurrentModificationException.
IdentityHashMap is a class present in java.util package. It implements the Map interface with a hash table , using reference equality instead of object equality when comparing keys and values.In other words , in IdentityHashMap two keys k1 and k2 are considered equal if only if (k1==k2).
IdentityHashMap is not synchronized.
Iterators returned by the iterator() method are fail-fast , hence , will throw ConcurrentModificationException.
What is WeakHashMap?
WeakHashMap is a class present in java.util package similar to IdentityHashMap. It is a Hashtable based implementation of Map interface with weak keys. An entry in WeakHashMap will automatically be removed when its key is no longer in ordinary use. More precisely the presence of a mapping for a given key will not prevent the key from being discarded by the garbage collector.
It permits null keys and null values.
Like most collection classes this class is not synchronized. A synchronized WeakHashMap may be constructed using the Collections.synchronizedMap() method.
Iterators returned by the iterator() method are fail-fast , hence , will throw ConcurrentModificationException
WeakHashMap is a class present in java.util package similar to IdentityHashMap. It is a Hashtable based implementation of Map interface with weak keys. An entry in WeakHashMap will automatically be removed when its key is no longer in ordinary use. More precisely the presence of a mapping for a given key will not prevent the key from being discarded by the garbage collector.
It permits null keys and null values.
Like most collection classes this class is not synchronized. A synchronized WeakHashMap may be constructed using the Collections.synchronizedMap() method.
Iterators returned by the iterator() method are fail-fast , hence , will throw ConcurrentModificationException
How will you make Collections readOnly ?
We can make the Collection readOnly by using the
following lines code:
General :
Collections.unmodifiableCollection(Collection c)
Collections.unmodifiableMap(Map m)
Collections.unmodifiableMap(Map m)
Collections.unmodifiableList(List l)
Collections.unmodifiableSet(Set s)
What are concurrent Collection Classes?
Java 1.5 Concurrent package (java.util.concurrent)
contains thread-safe collection classes that allow collections to be modified
while iterating. By design Iterator implementation in java.utilpackages
are fail-fast and throws ConcurrentModificationException. But Iterator
implementation injava.util.concurrent packages are fail-safe and we can
modify the collection while iterating. Some of these classes
are CopyOnWriteArrayList, ConcurrentHashMap, CopyOnWriteArraySet.
java.util.concurrent.BlockingQueue is a Queue
that supports operations that wait for the queue to become non-empty when
retrieving and removing an element, and wait for space to become available in
the queue when adding an element.
BlockingQueue interface is part of java collections
framework and it’s primarily used for implementing producer consumer problem.
We don’t need to worry about waiting for the space to be available for producer
or object to be available for consumer in BlockingQueue as it’s handled by implementation
classes of BlockingQueue.
Java provides several BlockingQueue implementations
such as ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue,
SynchronousQueue etc.
Both Queue and Stack are used to store data before
processing them. java.util.Queue is an interface whose implementation
classes are present in java concurrent package. Queue allows retrieval of
element in First-In-First-Out (FIFO) order but it’s not always the case. There
is also Deque interface that allows elements to be retrieved from both end of
the queue.
Stack is similar to queue except that it allows elements to be retrieved in Last-In-First-Out (LIFO) order.
Stack is a class that extends Vector whereas Queue is an interface.
Stack is similar to queue except that it allows elements to be retrieved in Last-In-First-Out (LIFO) order.
Stack is a class that extends Vector whereas Queue is an interface.
Comparable and Comparator interfaces are used to
sort collection or array of objects.
- Comparable Interface is actually from java.lang package.
- It will have a method compareTo(Object obj)to sort objects
- Comparator Interface is actually from java.util package.
- It will have a method compare(Object obj1, Object obj2)to sort
objects
Comparable interface is used to provide the natural
sorting of objects and we can use it to provide sorting based on single logic.
Comparator interface is used to provide different algorithms for sorting and we
can choose the comparator we want to use to sort the given collection of
objects.
If we need to sort an array of Objects, we can
use Arrays.sort(). If we need to sort a list of objects, we can
use Collections.sort(). Both these classes have overloaded sort() methods
for natural sorting (using Comparable) or sorting based on criteria (using
Comparator).
Collections internally uses Arrays sorting method, so both of them have same performance except that Collections take sometime to convert list to array.
Collections internally uses Arrays sorting method, so both of them have same performance except that Collections take sometime to convert list to array.
What is Big-O notation? Give some examples?
The Big-O notation describes the performance of an
algorithm in terms of number of elements in a data structure. Since Collection
classes are actually data structures, we usually tend to use Big-O notation to choose
the collection implementation to use based on time, memory and performance.
Example 1: ArrayList get(index i) is a
constant-time operation and doesn’t depend on the number of elements in the
list. So it’s performance in Big-O notation is O(1).
Example 2: A linear search on array or list performance is O(n) because we need to search through entire list of elements to find the element.
Example 2: A linear search on array or list performance is O(n) because we need to search through entire list of elements to find the element.
What is CopyOnWriteArrayList? How it is different from
ArrayList in Java?
CopyOnWriteArrayList is a thread safe variant of ArrayList in which all mutative operations like add, set are implemented by creating a fresh copy of the underlying array.
It guaranteed not to throw ConcurrentModificationException.
It permits all elements including null. It is introduced in jdk 1.5
CopyOnWriteArrayList is a thread safe variant of ArrayList in which all mutative operations like add, set are implemented by creating a fresh copy of the underlying array.
It guaranteed not to throw ConcurrentModificationException.
It permits all elements including null. It is introduced in jdk 1.5
What is UnsupportedOperationException?
This exception is thrown on invoked methods
which are not supported by actual collection type.
For example, if you make a read-only list list using
“Collections.unmodifiableList(list)” and then call add() or remove() method,
what should happen. It should clearly throw UnsupportedOperationException.
Which collection classes provide random access of it’s elements?
ArrayList, HashMap, TreeMap, Hashtable classes
provide random access to it’s elements.
No comments:
Post a Comment