JAVA Collection Framework

Where will you use ArrayList and where will you use LinkedList?
-------------------------------------------------------------------
ArrayList is faster for iteration and LinkedList is faster for insertion and deletion. So if the list will more frequently be read or searched than modifying
it then ArrayList is the better choice and the list will be modified more frequently than reading or searching then LinkedList is a better choice.

What is difference between array and ArrayList?
------------------------------------------------
Array is a fixed length data structure but ArrayList is resizable Collection.

Array elements must be of same type but ArrayList can contain different types of elements.

Array can contain premitive types but ArrayList cannot contain premitive types.

Arrays cannot use Generics but ArrayList can use Generics.

What is fail-fast, fail-tolerant and fail-safe property?
--------------------------------------------------------

Fail-fast property is to immediately respond to operations that might lead to failure or exception.

Fail-tolerant property allows to system to continue in case failures rather than completely stopping the system.

Fail-safe property assumes that the failure is safe for the system.

What is the difference between Iterator and ListIterator?
----------------------------------------------------------

ListIterator interface extends the interface Iterator.
ListIterator can be used only to iterate a List but Iterator can be used to iterate a Set or a List.
Iterator allows only forward traversal but ListIterator allows both forward and backward traversal.
ListIterator provides additional methods like add() , set()

What is the difference between Enumeration and Iterator interface?
--------------------------------------------------------------------
Enumeration was created to traverse through the elements of a Vector and the keys where as  Iterator is created to traverse through the elements of a Collection.
Enumeration is faster than Iterator.
Enumeration uses less memory than Iterator.

What is the difference between ArrayList and Vector?
-----------------------------------------------------
All the methods of Vector are synchronized but the methods of ArrayList are not synchronized
he Enumeration returned by Vector’s elements() method is not fail-fast whereas ArraayList have method to return Iterator.

What is the difference between List and Set?
-------------------------------------------
List is an ordered collection which allows duplicate elements but Set is an unordered collection which does not allow duplicate elements.

How a Set prevents inserting duplicate elements?
-------------------------------------------------
Set uses both equals() and hashCode() method to check for the duplicates. The equals() and hashCode() contract must be satisfied to prevent inserting duplicate
elements into a Set.

Which is a better choice in terms of Insertion and Iteration between List and Set?
-----------------------------------------------------------------------------------
In terms of Insertion List is faster than Set because List can directly add an element at the end but Set needs to perform a sequential check for a duplication
before adding. This duplication checking makes Set slower than List.

In terms of Iteration List is faster because it supports indexed access


What is the difference between HashSet and TreeSet?
-----------------------------------------------------
HashSet is not sorted but TreeSet is sorted by the natural ordering defined in the Comparable object’s compareTo() mothod or it can be created using the TreeSet
constructor using a Comparator.

HashSet is faster than TreeSet in case of iteration and insertion.

Can a null element be added to a HashSet or TreeSet?
-------------------------------------------------------
HashSet allows inserting null into it only once. TreeSet allows inserting null into it multiple times or disallows based on the definition of comparing of the
objects in Comparable.compateTo() or Comparator.compare() method.

What is the effect of implementing equals() but not implementing hashCode() in case of a List and Set?
-------------------------------------------------------------------------------------------------------
No impact will be observed in case of insertion and selection for Vector, ArrayList and LinkedList.

Duplicate elements will be inserted into a Set. If we search using the actual object reference that was used to insert only then the object will be found in HashSet
and LinkedHashSet.

If hashCode() is not overridden but equals() is overridden then Set will be able to distinguish duplicates?
-------------------------------------------------------------------------------------------------------------
The default implementation provided by the Object.hashCode()returns distinct integers for distinct objects because it returns the internal address of the object.
Hence if two objects are equal according to the equals() method even then the hashCode of them will be different, which is a violation of the hashCode contract and
the Set will consider them as different objects.


Explain the methods present in Queue interface?
----------------------------------------------------
offer(): Inserts an element if possible, otherwise returns false. This differs from the Collection.add() method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity or “bounded” queues.

remove(): Returns the head of this Queue and if this queue is empty then throws NoSuchElementException. It removes the head of this Queue.

element(): Returns the head of this Queue and if this Queue is empty then throws NoSuchElementException. It does not remove the head of this Queue.

peek(): Returns the head of this Queue and if this Queue is empty then returns null. It does not remove the head of this Queue.

poll(): Returns the head of this Queue and if this Queue is empty then returns null. It removes the head of this Queue.


What is PriorityQueue?
---------------------------
The elements of the priority queue are ordered according to their natural ordering, or by a Comparator. A priority queue does not permit null elements
also does not permit insertion of non-comparable objects

The head of this queue is the least element with respect to the specified ordering.

 What is ConcurrentHashMap?
--------------------------------
ConcurrentHashMap is a hash table supporting full concurrency of retrievals and adjustable expected concurrency for updates.



What are the default initial capacities of Vector, ArrayList, LinkedList, HashSet, LinkedHashSet, TreeSet, Hashtable, HashMap, LinkedHashMap and TreeMap?
---------------------------------------------------------------------------------------------------------------------------------------------------------
The default initial capacity of a Vector is 10 and it increases by 100%.
1
   
newCapacity = oldCapacity * 2

The default initial capacity of an ArrayList is 10 and it increases by 50%.
1
   
newCapacity = (oldCapacity * 3)/2 + 1

LinkedList starts with a single LinkedList.Entry reference which is a private static inner class.

The internal data structure of a HashSet is a HashMap whose default initial capacity is 16 with load factor of 0.75.

The internal data structure of a LinkedHashSet is a LinkedHashMap whose default initial capacity is 16 with load factor of 0.75.

The internal data structure of a TreeSet is a TreeMap that starts with a single TreeMap.Entry reference named root.

The default initial capacity of a HashTable is 11 with load factor of 0.75.
1
   
newCapacity = oldCapacity * 2 + 1

The default initial capacity of a HashMap is 16 with load factor of 0.75.

The default initial capacity of a LinkedHashMap is 16 with load factor of 0.75.

TreeMap starts with a single TreeMap.Entry reference named root.

While passing a Collection as argument to a function, how can we make sure the function will not be able to modify it?
----------------------------------------------------------------------------------------------------------------------

Collections.unmodifiableCollection() method returns a read only collection and any attempt to modify the collection throws an


What are different ways to iterate over a list? Which one is faster?
-----------------------------------------------------------------------
There are two ways to iterate over a list. We can use an iterator or we can use a for loop. Iterating using a for loop is faster because ArrayList is
internally an array so it provides indexed access and thus the values will be directly accessed as per the index.UnsupportedOperationException exception.

What are different ways to iterate over a Map? Which one is faster?
-----------------------------------------------------------------------

Map interface provides three different collection views: keySet(), values() and entrySet().

The keyset() method returns a Set of the keys and the get() method can be used to get the value. The values() method returns a Collection of only the values so
keys are not available.

The entrySet() method returns a Set of Map.Entry objects which contains both key and value. We can iterate over these views either by an Iterator or by a For loop.

Collection interface provides toArray() method so Map can be converted to an array and the array can be iterated. It provides three additional ways to iterate.


entrySet() method is the most efficient way to iterate through a Map and the For loop is more cleaner and readable than the Iterator.


Which collection classes provide random access of its elements?
-------------------------------------------------------------------
ArrayList and Vector implements the marker interface java.util.RandomAccess. Hence ArrayList, Vector and Stack provide random access of its elements.

How to avoid ConcurrentModificationException while iterating a collection?
---------------------------------------------------------------------------
We can use concurrent collection classes to avoid ConcurrentModificationException while iterating over a collection. For example we can use CopyOnWriteArrayList
instead of ArrayList.

How can we create a synchronized collection from given collection?
---------------------------------------------------------------------
We can use Collections.synchronizedCollection()

How can ArrayList be synchronized without using Vector?
-------------------------------------------------------
List list = Collections.synchronizedList(new ArrayList());

How can we make HashMap synchronized?
----------------------------------------
Map map = Collections.synchronizedMap(new HashMap());

How to obtain Array from an ArrayList?
-------------------------------------------
ArrayList.toArray() method returns an array

How to convert a String array to ArrayList?
--------------------------------------------
using Arrays.asList() converts an array to a List and ArrayList provides a constructor that constructs an ArrayList from a Collection.
example :   
String[] stringArray = { "one", "two", "three" };
List<String> stringList = Arrays.asList(stringArray);
ArrayList<String> stringArrayList = new ArrayList<String>(stringList);

How to reverse a List?
-------------------------
Collections.reverse()

Why String, Integer and other wrapper classes are considered good keys?
----------------------------------------------------------------------
String, Integer and other wrapper classes are final or immutable classes and they have overridden equals() and hashCode() method as per the contract so they are
considered good keys.

Why there is no concrete implementation of Iterator interface?
-------------------------------------------------------------
A concrete implementation of an Iterator must decide between an ordered iteration or an unordered iteration which clearly leads to an iterator either for a List or
for a Set. Iterators of a List must be ordered because ordering is the heart of List whereas Set does not need ordering as an essential property and ordering a Set
makes a very special type of Set. Thus iterators are more specific functionality to specific collection types rather than applicable to all types of Collection.
Hence subclasses of Collection provide iterators that are specific to that collection type.

Why there is no method like Iterator.add() to add elements to the collection?
-----------------------------------------------------------------------------
Adding elements to the collection during the iteration is an unclear functionality and leads to an unordered iteration which is not desirable for ordered
collections

What are common algorithms implemented in Collections Framework?
---------------------------------------------------------------
The common algorithms implemented in Collections Framework are: sorting, searching, shuffling, swaping, min, max, rotate, addAll, replaceAll, etc.

What is Big-O notation?
--------------------------------------------
Big O notation is used to represent the complexity of an algorithm based on the input size. It is useful to choose the best algorithm to solve a problem.

What is the performance of various Java collection implementations/algorithms? What is Big ‘O’ notation for each of them?
----------------------------------------------------------------------------------------------------------------------------

ArrayList: The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding N elements requires O(N) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

LinkedList: Performance of get and remove methods is linear time [ Big O Notation is O(N) ] – Performance of add and Iterator.remove methods is constant-time [ Big O Notation is O(1) ]

HashSet: This class offers constant time performance for the basic operations like add, remove, contains and size assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the HashSet instance’s size that is the number of elements plus the “capacity” of the backing HashMap instance that is the number of buckets. Thus, it’s very important not to set the initial capacity too high or the load factor too low if iteration performance is important.

LinkedHashSet: Like HashSet, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashSet, due to the added expense of maintaining the linked list, with one exception: Iteration over a LinkedHashSet requires time proportional to the size of the set, regardless of its capacity. Iteration over a HashSet is likely to be more expensive, requiring time proportional to its capacity.

A linked hash set has two parameters that affect its performance: initial capacity and load factor. They are defined precisely as for HashSet. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashSet, as iteration times for this class are unaffected by capacity.

TreeSet: This implementation provides guaranteed log(N) time cost for the basic operations like add, remove and contains.

Hashtable: An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. Note that the hash table is open: in the case of a “hash collision”, a single bucket stores multiple entries, which must be searched sequentially. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. The initial capacity and load factor parameters are merely hints to the implementation. The exact details as to when and whether the rehash method is invoked are implementation-dependent.

HashMap: This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the “capacity” of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

LinkedHashMap: Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.

A linked hash map has two parameters that affect its performance: initial capacity and load factor. They are defined precisely as for HashMap. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashMap, as iteration times for this class are unaffected by capacity.

TreeMap: This implementation provides guaranteed log(N) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest’s Introduction to Algorithms.
90. What is the difference between sorting performance of Arrays.sort() and Collections.sort()? Which one is faster? Which one to use and when?

Collections.sort() can sort only Lists and Arrays.sort() can sort only arrays. Internally Collections.sort() converts the List to an array and then it calls Arrays.sort() to sort it and then it converts the sorted array into a List whereas Arrays.sort() directly sorts the array.

Hence Arrays.sort() is faster than Collections.sort().

When we have a List we can use Collections.sort() and when we have an array we can use Arrays.sort().


What are best practices related to Java Collections Framework?
---------------------------------------------------------------
1. Choose the right type of collection based on the need.
2. Optimize the initial capacity to avoid rehashing or resizing.
3. Override equals() and hashCode() methods as per the contract.
4. Use polymorphic references to List, Set and Map instead of their concrete implementation.
5. Use Generics for type safety at compile time.
6. Use immutable classes as key in Map.
7. Use Collections utility methods for algorithms like sorting, searching, shuffling, swapping, reversing, synchronizing, read only collections, etc. rather than
writing own implementation.

What is load factor?
--------------------------
Load factor is the ratio of the number of elements of the hash table and the number of buckets.

What is Hashing?
-------------------
Hashing means using some function or algorithm to map object data to some representative integer value.

What is Hash Collision?
---------------------------
If the hash codes of two or more objects are same then it is known as hash collision.

What is Re-hashing?
-----------------------
Rebuilding the internal data structure of the hash table is known as rehashing. When the size of the hash table exceeds the threshold = capacity * load factor,
then all the elements are moved to a new bigger hash table. The hash code is calculated again to determine the bucket number so it is called rehashing.


How does put() and get() method of HashMap work?
-------------------------------------------------
The put() method with key and value is used to insert an element into the HashMap. The hash code of the key is calculated and the bucket is determined from the
hash code. If the bucket is empty then a new HashMap.Entry(hash, key, value, next) element is inserted into the bucket. If the bucket is not empty then all the
keys in the linked list is compared with the equals method to check if an element with the same key is already there or not. If the key is found then the value is
overwritten otherwise a new HashMap.Entry(hash, key, value, next) element is inserted at the end.

The get() method is used to get the value for a given key. The hash code of the key is calculated and the bucket is determined from the hash code. The linked list
present into the bucket is sequentially searched for the key. If the hash code matches and the key passes either == or equals() method then the value stored there
is returned.

 What will happen if two different HashMap key objects have same hashcode? How will you retrieve Value object if two Keys will have same hashcode?
-----------------------------------------------------------------------------------------------------------------------------------------------------
Two different HashMap key objects have same hashcode is known as hash collision. HashMap uses a doubly linked list for each bucket to resolve hash collision.
Both the keys will be stored into the same bucket as different nodes of the linked list.

The nodes of this linked list are of type HashMap.Entry(hash, key, value, next). The get() method is used to get the value for a given key. It will perform a
sequential search into the linked list present into the bucket. Since the hash code is same the key will be identified by any of the == or equals() method and
then the value stored into the HashMap.Entry will be returned.