Collection
Question:Comparable and Comparator?
Question:What is return type of compareTo?
Answer : return type is integer.
Comparable
|
Comparator
|
Comparable provides single sorting sequence. In other words, we can sort the collection on the basis of single element such as id or name or price etc.
|
Comparator provides multiple sorting sequence. In other words, we can sort the collection on the basis of multiple elements such as id, name and price etc.
|
Comparable affects the original class i.e. actual class is modified.
|
Comparator doesn't affect the original class i.e. actual class is not modified.
|
Comparable provides compareTo() method to sort elements.
|
Comparator provides compare() method to sort elements.
|
Comparable is found in java.lang package.
|
Comparator is found in java.util package.
|
We can sort the list elements of Comparable type byCollections.sort(List) method.
|
We can sort the list elements of Comparator type byCollections.sort(List,Comparator) method.
|
Answer : return type is integer.
Question: What is the diff between TreeSet and LinkedHashSet?
Answer:
1. LinkedHashSet follows the insertion order and TreeSet follows the natural ordering decided by the comparable implementation done for the source object, the natural ordering of the TreeSet can be altered by creating the object of tree set with the comparator as the argument.
2. TreeSet is implementing the SortedSet Interface but LinkedHashSet has not.
3. All operations having log(n) time for treeset but hashset has the constant time in case LinkedHashSet.
4.LinkedHashSet can take any object as its internal node, but the there has to be Comparable implementation of the Object which is about to be added in the treeset, or else we need to pass the comparator to the Constructor of the TreeSet.
Question:Collections.reverse and Collections.reverseOrder.
Answer:
1. LinkedHashSet follows the insertion order and TreeSet follows the natural ordering decided by the comparable implementation done for the source object, the natural ordering of the TreeSet can be altered by creating the object of tree set with the comparator as the argument.
2. TreeSet is implementing the SortedSet Interface but LinkedHashSet has not.
3. All operations having log(n) time for treeset but hashset has the constant time in case LinkedHashSet.
4.LinkedHashSet can take any object as its internal node, but the there has to be Comparable implementation of the Object which is about to be added in the treeset, or else we need to pass the comparator to the Constructor of the TreeSet.
Question:Collections.reverse and Collections.reverseOrder.
Question: Can you explain how Arraylist is implemented.
Answer : How ArrayList works internally in java?
Basic Data Structure used in an ArrayList is -
private transient Object[] elementData;
So it's an array of Object(Just the declaration.) When we actually create an arrayList following piece of code is executed -
this.elementData = new Object[initialCapacity];
You create an ArrayList as follows -
List<String> myList = new ArrayList<String>(); OR
List<String> myList = new ArrayList<String>(6);
1st one invokes a default constructor while the second will invoke a constructor with an integer argument. When we create an ArrayList in the 2nd way it will internally create an array of Object with size specified in the constructor argument(6 in our case). Default value is 10 i.e if no size is supplied array with size 10 is created.
Code for it is as follows -
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
this(10);
}
Once you tell this interviewer can be sure you know what data structure is internally used.Now we know ArrayList is better than normal arrays as it is size dynamically increases. But how does this take place internally? How much does the size increase?
Inside .add() method there is this check. Before adding element into the array it will check what is the current size of filled elements and what is the maximum size of the array. If size of filled elements is greater than maximum size of the array(or will be after adding current element) then size of the array must be increased. But if you know array basic you cannot dynamically increase the array size. So what happens internally is a new Array is created with size 1.5*currentSize and the data from old Array is copied into this new Array.
Code for it is as follows -
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
Question : Can you explain How HashMap is implemented in Java?
Answer : Below are the short info on how it has been done:
- HashMap has a inner class called Entry which stores key-value pairs.
- Above Entry object is stored in Entry[ ](Array) called table
- An index of table is logically known as bucket and it stores first element of linkedlist
- Key object’s hashcode() is used to find bucket of that Entry object.
- If two key object ‘s have same hashcode , they will go in same bucket of table array.
- Key object ‘s equals() method is used to ensure uniqueness of key object.
- Value object ‘s equals() and hashcode() method is not used at all
Question: What will happen if the we try to use collections.sort on User Defined Class?
Question : What is the difference between Iterator and ListIterator?
Answer : Iterator vs ListIterator
1) Iterator is used for traversing List and Set both.
We can use ListIterator to traverse List only, we cannot traverse Set using ListIterator.
2) We can traverse in only forward direction using Iterator.
Using ListIterator, we can traverse a List in both the directions (forward and Backward).
3) We cannot obtain indexes while using Iterator
We can obtain indexes at any point of time while traversing a list using ListIterator. The methods nextIndex() and previousIndex() are used for this purpose.
4) We cannot add element to collection while traversing it using Iterator, it throws ConcurrentModificationException when you try to do it, however we remove the element using the iterator's remove method, but we should not call the add or remove method using the list reference as it will give concurrentmodification exception.
We can add element at any point of time while traversing a list using ListIterator, but make sure we are using iterator's add and remove method not the list add an remove method.
5) We cannot replace the existing element value when using Iterator.
By using set(E e) method of ListIterator we can replace the last element returned by next() or previous() methods.
Answer : Iterator vs ListIterator
1) Iterator is used for traversing List and Set both.
We can use ListIterator to traverse List only, we cannot traverse Set using ListIterator.
2) We can traverse in only forward direction using Iterator.
Using ListIterator, we can traverse a List in both the directions (forward and Backward).
3) We cannot obtain indexes while using Iterator
We can obtain indexes at any point of time while traversing a list using ListIterator. The methods nextIndex() and previousIndex() are used for this purpose.
4) We cannot add element to collection while traversing it using Iterator, it throws ConcurrentModificationException when you try to do it, however we remove the element using the iterator's remove method, but we should not call the add or remove method using the list reference as it will give concurrentmodification exception.
We can add element at any point of time while traversing a list using ListIterator, but make sure we are using iterator's add and remove method not the list add an remove method.
5) We cannot replace the existing element value when using Iterator.
By using set(E e) method of ListIterator we can replace the last element returned by next() or previous() methods.
Question : What is the difference between add and set in List/ArrayList?
Answer : Here is the diff between both the method.
Answer : for-each is an advanced looping construct. Internally it creates an Iterator and iterates over the the Collection. Only possible advantage of using actual Iterator object over for-each construct is that you can modify your collection using Iterator's methods like .remove(). Modifying the collection without using Iterator's methods while iterating will led to ConcurrentModificationException.
Question: What is Collection API?
Answer : Here is the diff between both the method.
- add(int index, E element) : Inserts the specified element at the specified position in this list (optional operation).
- set(int index, E element) : Replaces the element at the specified position in this list with the specified element (optional operation).
Answer : for-each is an advanced looping construct. Internally it creates an Iterator and iterates over the the Collection. Only possible advantage of using actual Iterator object over for-each construct is that you can modify your collection using Iterator's methods like .remove(). Modifying the collection without using Iterator's methods while iterating will led to ConcurrentModificationException.
Question: What is Collection API?
Answer: The Collection API is a set of classes and interfaces that support operation on collections of objects. These classes and interfaces are more flexible, more powerful, and more regular than the vectors, arrays, and hashtables if effectively replaces.
Example of classes: HashSet, HashMap, ArrayList, LinkedList, TreeSet and TreeMap.
Example of interfaces: Collection, Set, List and Map.
Question : If the Same key is added with the different value into the hashMap what will happen?Answer : It will replace the existing value for the existing key. It will return the previous value which was replaced so we can audit what was there, if it returns null it means the new key has been added else it means it has replaced the returned values.
Question : How to find if the key exists in the map?
Answer : use containsKey method.
Question : How to find if the value existing the map?Answer : call the containesValue method?
Question: Is Iterator and ListIterator is a Class or Interface? What is its use?
Answer: Iterator is an interface which is used to step through the elements of a Collection.
Question: What's the main difference between a Vector and an ArrayList
Answer: Java Vector class is internally synchronized and ArrayList is not, the method inside the vector are synchronized whereas in ArrayList it's not.
Question: You are planning to do an indexed search in a list of objects. Which of the two Java collections should you use: ArrayList or LinkedList?
Answer: ArrayList
Question : When to use ArrayList and when to User LinkedList?
Answer : Linked lists are preferable over arrays when:
a) you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)
b) you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big
c) you don't need random access to any elements
d) you want to be able to insert items in the middle of the list (such as a priority queue)
Arrays are preferable when:
a) you need indexed/random access to elements
b) you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array.
c) you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.
d) memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.
Question: What is the Vector class?
Answer: The Vector class provides the capability to implement a growable array of objects, with the benefit of thread safety as the methods for add is synchronized.
What is Interface Deque?
Answer : A linear collection that supports element insertion and removal at both ends. The name deque is short for "double ended queue" and is usually pronounced "deck". Most Deque implementations place no fixed limits on the number of elements they may contain, but this interface supports capacity-restricted deques as well as those with no fixed size limit.
This interface defines methods to access the elements at both ends of the deque. Methods are provided to insert, remove, and examine the element. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value (either null or false, depending on the operation). The latter form of the insert operation is designed specifically for use with capacity-restricted Deque implementations; in most implementations, insert operations cannot fail.
The twelve methods described above are summarized in the following table:
This interface extends the Queue interface. When a deque is used as a queue, FIFO (First-In-First-Out) behavior results. Elements are added at the end of the deque and removed from the beginning. The methods inherited from the Queue interface are precisely equivalent to Deque methods as indicated in the following table:
Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class. When a deque is used as a stack, elements are pushed and popped from the beginning of the deque. Stack methods are precisely equivalent to Deque methods as indicated in the table below:
Note that the peek method works equally well when a deque is used as a queue or a stack; in either case, elements are drawn from the beginning of the deque.
This interface provides two methods to remove interior elements, removeFirstOccurrence and removeLastOccurrence.
Unlike the List interface, this interface does not provide support for indexed access to elements.
While Deque implementations are not strictly required to prohibit the insertion of null elements, they are strongly encouraged to do so. Users of any Deque implementations that do allow null elements are strongly encouraged not to take advantage of the ability to insert nulls. This is so because null is used as a special return value by various methods to indicated that the deque is empty.
Deque implementations generally do not define element-based versions of the equals and hashCode methods, but instead inherit the identity-based versions from class Object.
Question : Which collections supports iterator?
Answer : Set,List and the Map's entryset and entrykeys.
Question : What is ArrayBlockingQueue?
Answer : A Queue that additionally supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element. A BlockingQueue does not accept null elements. Implementations throw NullPointerException on attempts to add, put or offer a null. A null is used as a sentinel value to indicate failure of poll operations.
What is ArrayDeque?
Answer : The java.util.ArrayDeque class provides resizable-array and implements the Deque interface. Following are the important points about Array Deques:
Question : What is ConcurrentLinkedQueue?
Answer: ConcurrentLinkedQueue is an unbounded thread-safe queue based on linked nodes. This queue orders elements as a FIFO (first-in-first-out). The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue.
A ConcurrentLinkedQueue is a good choice when many threads share access to a common collection. Like most other concurrent collection implementations, this class does not permit the use of null elements.
This java example spawns off two threads. One puts strings on the queue and the other takes strings off the queue.
What is ConcurrentSkipListSet?
What is copyOnWriteArrayList and what is the diff between ArrayList and CopyOnWriteArrayList
Answer : CopyOnWriteArrayList is a concurrent Collection class introduced in Java 5 Concurrency API along with its popular cousin ConcurrentHashMap in Java. CopyOnWriteArrayList implements List interface like ArrayList, Vector and LinkedList but its a thread-safe collection and it achieves its thread-safety in a slightly different way than Vector or other thread-safe collection class. As name suggest CopyOnWriteArrayList creates copy of underlying ArrayList with every mutation operation e.g. add or set. Normally CopyOnWriteArrayList is very expensive because it involves costly Array copy with every write operation but its very efficient if you have a List where Iteration outnumber mutation e.g. you mostly need to iterate the ArrayList and don't modify it too often. Iterator of CopyOnWriteArrayList is fail-safe and doesn't throw ConcurrentModificationException even if underlying CopyOnWriteArrayList is modified once Iteration begins because Iterator is operating on separate copy of i. Consequently all the updates made on CopyOnWriteArrayList is not available to Iterator. In this Java Collection tutorial we will see What is CopyOnWriteArrayList in Java, Difference between ArrayList and CopyOnWriteArrayList in Java and One simple Java program example on How to use CopyOnWriteArrayList in Java.
1) First and foremost difference between CopyOnWriteArrayList and ArrayList in Java is that CopyOnWriteArrayList is a thread-safe collection while ArrayList is not thread-safe and can not be used in multi-threaded environment.
2) Second difference between ArrayList and CopyOnWriteArrayList is that Iterator of ArrayList is fail-fast and throw ConcurrentModificationException once detect any modification in List once iteration begins but Iterator of CopyOnWriteArrayList is fail-safe and doesn't throw ConcurrentModificationException.
3) Third difference between CopyOnWriteArrayList vs ArrayList is that Iterator of former doesn't support remove operation while Iterator of later supports remove() operation.
Question : Give the program example for the CopyOnWriteArrayList?
What is copyOnWriteArraySet?
Answer: CopyOnWriteArraySet is little brother of CopyOnWriteArrayList class. These are special purpose collection classes which was added on JDK 1.5, along with their most popular cousin ConcurrentHashMap. They are part of concurrent collection framework and reside in java.util.concurrent package. CopyOnWriteArraySet is best suited as read-only collection whose size is small enough to copy if some mutative operation happens, for example you can use CopyOnWriteArraySet to store object at start-up of application and let multiple application thread access them during application life time. If an new condition or object comes up during that time, it can also be added into this Set, with incurring cost of creating a new array. One of the most important thing to know about CopyOnWriteArraySet is that it is backed by CopyOnWriteArrayList, which means it also share all basic properties of CopyOnWriteArrayList. Another important thing to remember is that Iterators of this collection class doesn't support remove() operation, trying to remove an element while iterating will result in UnSupportedOperationException. This is done to ensure speed during traversal, traversing this set implementation using Iterator is fast and cannot encounter interference from other threads. Iterators actually rely on unchanging snapshots of the array at the time the iterators were constructed. In short, use CopyOnWriteArraySet if set is small enough to copy on add, set or remove, and main purpose is to read data with occasional updates. Also if you want to remove elements during iteration, don't use this Set implementation because its iterator doesn't support remove(), and throws java.lang.UnsupportedOperationException
What is DelayQueue?
What is EnumSet?
What is JobStateReason?
What is LinkedBlockingDequeue?
What is LinkedBlockingQueue?
What is PriorityBlockingQueue?
What is PriorityQueue?
Answer: An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).
The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.
This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe PriorityBlockingQueue class.
Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).
This class is a member of the Java Collections Framework.
What is RoleList?
What is RoleUnResolvedList?
What is Stack?
Answer : The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.
When a stack is first created, it contains no items.
A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
Deque<Integer> stack = new ArrayDeque<Integer>();
What is SynchronousQueue?
Question: What is the Map interface?
Answer: The Map interface replaces the JDK 1.1 Dictionary class and is used associate keys with values.
Question: What is the Collection interface?
Answer: The Collection interface provides support for the implementation of a mathematical bag - an unordered collection of objects that may contain duplicates.
Question: What is the Set interface?
Answer: The Set interface provides methods for accessing the elements of a finite mathematical set. Sets do not allow duplicate elements.
Question: What's the difference between a queue and a stack
Answer: Stacks works by last-in-first-out rule (LIFO), while queues use the FIFO rule
Question: What are different types of collections
Answer: A collection has no special order and does not reject duplicates
A list is ordered and does not reject duplicates
A set has no special order but rejects duplicates
A map supports searching on a key field, values of which must be unique
Question: Tell me something about Arrays.
Answer: Arrays are fast to access, but are inefficient if the number of elements grow and if you have to insert or delete an element
Question : Difference between HashMap and HashTable / HashMap vs HashTable
Synchronization or Thread Safe : This is the most important difference between two . HashMap is non synchronized and not thread safe.On the other hand, HashTable is thread safe and synchronized.
Null keys and null values : Hashmap allows one null key and any number of null values, while Hashtable do not allow null keys and null values in the HashTable object.
Iterating the values: Hashmap object values are iterated by using iterator .HashTable is the only class other than vector which uses enumerator to iterate the values of HashTable object. difference between hashmap and hashtable
Fail-fast iterator : The iterator in Hashmap is fail-fast iterator while the enumerator for Hashtable is not. According to Oracle Docs, if the Hashtable is structurally modified at any time after the iterator is created in any way except the iterator's own remove method , then the iterator will throw ConcurrentModification Exception. Structural modification means adding or removing elements from the Collection object (here hashmap or hashtable) . Thus the enumerations returned by the Hashtable keys and elements methods are not fail fast.We have already explained the difference between iterator and enumeration.
Performance : Hashmap is much faster and uses less memory than Hashtable as former is unsynchronized . Unsynchronized objects are often much better in performance in compare to synchronized object like Hashtable in single threaded environment.
Superclass and Legacy : Hashtable is a subclass of Dictionary class which is now obsolete in Jdk 1.7 ,so ,it is not used anymore. It is better off externally synchronizing a HashMap or using a ConcurrentMap implementation (e.g ConcurrentHashMap).HashMap is the subclass of the AbstractMap class. Although Hashtable and HashMap has different superclasses but they both are implementations of the "Map" abstract data type.
Question : When to use HashMap ?
Answer: If your application do not require any multi-threading task, in other words hashmap is better for non-threading applications. HashTable should be used in multithreading applications.
Question: What is the Vector class?
Answer: The Vector class provides the capability to implement a growable array of objects What modifiers may be used with an inner class that is a member of an outer class? A (non-local) inner class may be declared as public, protected, private, static, final, or abstract.
Question: What is difference between ArrayList and Vector?Answer :
1) Synchronization - ArrayList is not thread-safe whereas Vector is thread-safe. In Vector class each method like add(), get(int i) is surrounded with a synchronized block and thus making Vector class thread-safe.
2) Data growth - Internally, both the ArrayList and Vector hold onto their contents using an Array. When an element is inserted into an ArrayList or a Vector, the object will need to expand its internal array if it runs out of room. A Vector defaults to doubling the size of its array, while the ArrayList increases its array size by 50 percent.
Question: How can Arraylist be synchronized without using Vector?Answer : Arraylist can be synchronized using:
Question : If synchronizedList/map/set is used, if we do any operation in the original collection will it affect the returned collection from the synchronized method or vice versa?
Answer : Both represent the same copy so any operation happened on any copy will affect both the collection, but ideally we should use the synchronzed version as it will give the expected output, but if we try to use the combination of both or just unsynchronized one, then we can't expect the outcome.
Question: If an Employee class is present and its objects are added in an arrayList. Now I want the list to be sorted on the basis of the employeeID of Employee class. What are the steps?
Answer : Follow the steps :
[Repeat]
Question: What is difference between HashMap and HashTable?
Answer : Both collections implements Map. Both collections store value as key-value pairs. The key differences between the two are
1. Hashmap is not synchronized in nature but Hashtable is.
2. The key and value for the hashmap can be null but for Hashtable it should be non null.
3. HashMap permits null values and only one null key, while Hashtable doesn't allow key or value as null.
Question : What is Fail-safe?
Answer: if the Hashtable is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException�
Example as follows:
But if we replace the HashMap with the ConcurrentHashMap then the program will run smoothly.
So one thing is to observe here is it is not only add the data, but also modify the ongoing iterator as the iterator of the
Question : Provide the diff between ConcurrentHashMap vs Hashtable vs Synchronized Map?
Answer : Though all three collection classes are thread-safe and can be used in multi-threaded, concurrent Java application, there is significant difference between them, which arise from the fact that how they achieve their thread-safety. Hashtable is a legacy class from JDK 1.1 itself, which uses synchronized methods to achieve thread-safety. All methods of Hashtable are synchronized which makes them quite slow due to contention if number of thread increases. Synchronized Map is also not very different than Hashtable and provides similar performance in concurrent Java programs. Only difference between Hashtable and Synchronized Map is that later is not a legacy and you can wrap any Map to create it's synchronized version by using Collections.synchronizedMap() method. On the other hand, ConcurrentHashMap is especially designed for concurrent use i.e. more than one thread. By default it simultaneously allows 16 threads to read and write from Map without any external synchronization. It is also very scalable because of stripped locking technique used in internal implementation of ConcurrentHashMap class. Unlike Hashtable and Synchronized Map, it never locks whole Map, instead it divides the map in segments and locking is done on those. Though it perform better if number of reader threads is greater than number of writer threads.
Question: What are the classes implementing List interface?
Answer : There are three classes that implement List interface:
1) ArrayList : It is a resizable array implementation. The size of the ArrayList can be increased dynamically also operations like add,remove and get can be formed once the object is created. It also ensures that the data is retrieved in the manner it was stored. The ArrayList is not thread-safe.
2) Vector: It is thread-safe implementation of ArrayList. The methods are wrapped around a synchronized block.
3) LinkedList: the LinkedList also implements Queue interface and provide FIFO(First In First Out) operation for add operation. It is faster if than ArrayList if it performs insertion and deletion of elements from the middle of a list.
Question : Which all classes implement Set interface?
Answer : A Set is a collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. HashSet, SortedSet, LinkedHashSet and TreeSet are the commnly used class which implements Set interface.
SortedSet - It is an interface which extends Set. A the name suggest , the interface allows the data to be iterated in the ascending order or sorted on the basis of Comparator or Comparable interface. All elements inserted into the interface must implement Comparable or Comparator interface.
TreeSet - It is the implementation of SortedSet interface. This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains). The class is not synchronized.
HashSet: This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element. This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets
LinkedHashSet: Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). Note that insertion order is not affected if an element is re-inserted into the set. (An element e is reinserted into a set s if s.add(e) is invoked when s.contains(e) would return true immediately prior to the invocation.)
Question : What is difference between List and a Set?
Answer :
1) List can contain duplicate values but Set doesnt allow. Set allows only to unique elements.
2) List allows retrieval of data to be in same order in the way it is inserted but Set doesnt ensures the sequence in which data can be retrieved.(Except HashSet)
Question : What is difference between Arrays and ArrayList ?
Answer : Arrays are created of fix size whereas ArrayList is of not fix size. It means that once array is declared as :
int [] intArray= new int[6];
intArray[7] // will give ArraysOutOfBoundException.
Also the size of array cannot be incremented or decremented. But with arrayList the size is variable.
Once the array is created elements cannot be added or deleted from it. But with ArrayList the elements can be added and deleted at runtime.
List list = new ArrayList();
list.add(1);
list.add(3);
list.remove(0) // will remove the element from the 1st location.
ArrayList is one dimensional but array can be multidimensional.
int[][][] intArray= new int[3][2][1]; // 3 dimensional array
To create an array the size should be known or initalized to some value. If not initialized carefully there could me memory wastage. But arrayList is all about dynamic creation and there is no wastage of memory.
Question : When to use ArrayList or LinkedList ?
Answer : Adding new elements is pretty fast for either type of list. For the ArrayList, doing random lookup using "get" is fast, but for LinkedList, it's slow. It's slow because there's no efficient way to index into the middle of a linked list. When removing elements, using ArrayList is slow. This is because all remaining elements in the underlying array of Object instances must be shifted down for each remove operation. But here LinkedList is fast, because deletion can be done simply by changing a couple of links. So an ArrayList works best for cases where you're doing random access on the list, and a LinkedList works better if you're doing a lot of editing in the middle of the list.
Question : Consider a scenario. If an ArrayList has to be iterate to read data only, what are the possible ways and which is the fastest?
Answer : It can be done in two ways, using for loop or using iterator of ArrayList. The first option is faster than using iterator. Because value stored in arraylist is indexed access. So while accessing the value is accessed directly as per the index.
Question : Now another question with respect to above question is if accessing through iterator is slow then why do we need it and when to use it.
Answer : For loop does not allow the updation in the array(add or remove operation) inside the loop whereas Iterator does. Also Iterator can be used where there is no clue what type of collections will be used because all collections have iterator.
Question: Which design pattern Iterator follows?Answer : It follows Iterator design pattern. Iterator Pattern is a type of behavioral pattern. The Iterator pattern is one, which allows you to navigate through a collection of data using a common interface without knowing about the underlying implementation. Iterator should be implemented as an interface. This allows the user to implement it anyway its easier for him/her to return data. The benefits of Iterator are about their strength to provide a common interface for iterating through collections without bothering about underlying implementation.
Example of Iteration design pattern - Enumeration The class java.util.Enumeration is an example of the Iterator pattern. It represents and abstract means of iterating over a collection of elements in some sequential order without the client having to know the representation of the collection being iterated over. It can be used to provide a uniform interface for traversing collections of all kinds.
Question: Is it better to have a HashMap with large number of records or n number of small hashMaps?
Answer : It depends on the different scenario one is working on:
1) If the objects in the hashMap are same then there is no point in having different hashmap as the traverse time in a hashmap is invariant to the size of the Map.
2) If the objects are of different type like one of Person class , other of Animal class etc then also one can have single hashmap but different hashmap would score over it as it would have better readability.
Question : Why is it preferred to declare: List<String> list = new ArrayList<String>(); instead of ArrayList<String> = new ArrayList<String>();
Answer : It is preferred because:
If later on code needs to be changed from ArrayList to Vector then only at the declaration place we can do that.
The most important one – If a function is declared such that it takes list. E.g void showDetails(List list);
When the parameter is declared as List to the function it can be called by passing any subclass of List like ArrayList,Vector,LinkedList making the function more flexible
Question: What is difference between iterator access and index access?
Answer : Index based access allow access of the element directly on the basis of index. The cursor of the datastructure can directly goto the 'n' location and get the element. It doesnot traverse through n-1 elements.
In Iterator based access, the cursor has to traverse through each element to get the desired element. So to reach the 'n'th element it need to traverse through n-1 elements.
Insertion,updation or deletion will be faster for iterator based access if the operations are performed on elements present in between the datastructure.
Insertion,updation or deletion will be faster for index based access if the operations are performed on elements present at last of the datastructure.
Traversal or search in index based datastructure is faster.
ArrayList is index access and LinkedList is iterator access.
Question: How to sort list in reverse order?Answer : To sort the elements of the List in the reverse natural order of the strings, get a reverse Comparator from the Collections class with reverseOrder(). Then, pass the reverse Comparator to the sort() method.
List list = new ArrayList();
Comparator comp = Collections.reverseOrder();
Collections.sort(list, comp)
Question : Can we Add null element into Set?Answer : HashSet and LinkedHashSet can contain null, but at max there can be only one null element, not more than one null, but in TreeSet canot contain null, as the comparable/comparator used during the insertion will throw the null pointer exception.
Question : How to make a List (ArrayList,Vector,LinkedList) read only?Answer : A list implemenation can be made read only using Collections.unmodifiableList(list). This method returns a new list. If a user tries to perform add operation on the new list; UnSupportedOperationException is thrown.
Question : What is ConcurrentHashMap?Answer : A concurrentHashMap is thread-safe implementation of Map interface. In this class put and remove method are synchronized but not get method. This class is different from Hashtable in terms of locking; it means that hashtable use object level lock but this class uses bucket level lock thus having better performance.
Question : Which is faster to iterate LinkedHashSet or LinkedList?
Answer : LinkedList.
Question : Which data structure HashSet implements?
Answer: HashSet implements hashmap internally to store the data. The data passed to hashset is stored as key in hashmap with null as value.
Question : Arrange in the order of speed - HashMap , HashTable, Collections.synchronizedMap, concurrentHashmap?Answer : HashMap is fastest, ConcurrentHashMap,Collections.synchronizedMap,HashTable.
Question : What is identityHashMap?
Answer : The IdentityHashMap uses == for equality checking instead of equals(). This can be used for both performance reasons, if you know that two different elements will never be equals and for preventing spoofing, where an object tries to imitate another.
Question : What is WeakHashMap?
Answer : A hashtable-based Map implementation with weak keys. An entry in a 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, that is, made finalizable, finalized, and then reclaimed. When a key has been discarded its entry is effectively removed from the map, so this class behaves somewhat differently than other Map implementations.
Now below is the code for the same
If we run after sometime we get the following output
Let's say if we uncomment the 3rd comments.
Let's say we uncomment the 1st comments then we will get the following output
Now lets uncomment the 2nd comment then we will get the following output
Now Let's un comment the 4th and 2nd comment then we will get the following output.
Reason is the 4th comment will make memory to run out so garbage collector will try to reclaim the soft reference.
Example of classes: HashSet, HashMap, ArrayList, LinkedList, TreeSet and TreeMap.
Example of interfaces: Collection, Set, List and Map.
Question : If the Same key is added with the different value into the hashMap what will happen?Answer : It will replace the existing value for the existing key. It will return the previous value which was replaced so we can audit what was there, if it returns null it means the new key has been added else it means it has replaced the returned values.
Question : How to find if the key exists in the map?
Answer : use containsKey method.
Question : How to find if the value existing the map?Answer : call the containesValue method?
Question: Is Iterator and ListIterator is a Class or Interface? What is its use?
Answer: Iterator is an interface which is used to step through the elements of a Collection.
Question: What's the main difference between a Vector and an ArrayList
Answer: Java Vector class is internally synchronized and ArrayList is not, the method inside the vector are synchronized whereas in ArrayList it's not.
Question: You are planning to do an indexed search in a list of objects. Which of the two Java collections should you use: ArrayList or LinkedList?
Answer: ArrayList
Question : When to use ArrayList and when to User LinkedList?
Answer : Linked lists are preferable over arrays when:
a) you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)
b) you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big
c) you don't need random access to any elements
d) you want to be able to insert items in the middle of the list (such as a priority queue)
Arrays are preferable when:
a) you need indexed/random access to elements
b) you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array.
c) you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.
d) memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.
Question: What is the Vector class?
Answer: The Vector class provides the capability to implement a growable array of objects, with the benefit of thread safety as the methods for add is synchronized.
What is Interface Deque?
Answer : A linear collection that supports element insertion and removal at both ends. The name deque is short for "double ended queue" and is usually pronounced "deck". Most Deque implementations place no fixed limits on the number of elements they may contain, but this interface supports capacity-restricted deques as well as those with no fixed size limit.
This interface defines methods to access the elements at both ends of the deque. Methods are provided to insert, remove, and examine the element. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value (either null or false, depending on the operation). The latter form of the insert operation is designed specifically for use with capacity-restricted Deque implementations; in most implementations, insert operations cannot fail.
The twelve methods described above are summarized in the following table:
| First Element (Head) | Last Element (Tail) | |||
| Throws exception | Special value | Throws exception | Special value | |
| Insert | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| Remove | removeFirst() | pollFirst() | removeLast() | pollLast() |
| Examine | getFirst() | peekFirst() | getLast() | peekLast() |
This interface extends the Queue interface. When a deque is used as a queue, FIFO (First-In-First-Out) behavior results. Elements are added at the end of the deque and removed from the beginning. The methods inherited from the Queue interface are precisely equivalent to Deque methods as indicated in the following table:
| Queue Method | Equivalent Deque Method |
add(e) | addLast(e) |
offer(e) | offerLast(e) |
remove() | removeFirst() |
poll() | pollFirst() |
element() | getFirst() |
peek() | peekFirst() |
Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class. When a deque is used as a stack, elements are pushed and popped from the beginning of the deque. Stack methods are precisely equivalent to Deque methods as indicated in the table below:
| Stack Method | Equivalent Deque Method |
push(e) | addFirst(e) |
pop() | removeFirst() |
peek() | peekFirst() |
Note that the peek method works equally well when a deque is used as a queue or a stack; in either case, elements are drawn from the beginning of the deque.
This interface provides two methods to remove interior elements, removeFirstOccurrence and removeLastOccurrence.
Unlike the List interface, this interface does not provide support for indexed access to elements.
While Deque implementations are not strictly required to prohibit the insertion of null elements, they are strongly encouraged to do so. Users of any Deque implementations that do allow null elements are strongly encouraged not to take advantage of the ability to insert nulls. This is so because null is used as a special return value by various methods to indicated that the deque is empty.
Deque implementations generally do not define element-based versions of the equals and hashCode methods, but instead inherit the identity-based versions from class Object.
Question : Which collections supports iterator?
Answer : Set,List and the Map's entryset and entrykeys.
Question : What is ArrayBlockingQueue?
Answer : A Queue that additionally supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element. A BlockingQueue does not accept null elements. Implementations throw NullPointerException on attempts to add, put or offer a null. A null is used as a sentinel value to indicate failure of poll operations.
What is ArrayDeque?
Answer : The java.util.ArrayDeque class provides resizable-array and implements the Deque interface. Following are the important points about Array Deques:
- Array deques have no capacity restrictions so they grow as necessary to support usage.
- They are not thread-safe; in the absence of external synchronization.
- They do not support concurrent access by multiple threads.
- Null elements are prohibited in the array deques.
- They are faster than Stack and LinkedList.
- This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces.
Question : What is descendingIterator().
Answer : The java.util.ArrayDeque.descendingIterator() method returns an iterator over the elements in this deque in reverse sequential order.
Question : What is offer() in queue?
Answer : The java.util.ArrayDeque.offer(E e) method inserts the specified element E at the end of this deque. This method returns true if the element was added to this deque, else false. it doesn't allow null element hence it will throw NullPointerException if the specified element is null.
Question : What is peek() in queue?
Answer : The java.util.ArrayDeque.peek() method retrieves the head of the queue(but does not remove) represented by this deque.Returns null if this deque is empty.
Question : What is poll() in queue?
Answer : The java.util.ArrayDeque.poll() retrieves and removes the head of the queue represented by this deque.Returns null if this deque is empty.
Question : What is ConcurrentLinkedQueue?
Answer: ConcurrentLinkedQueue is an unbounded thread-safe queue based on linked nodes. This queue orders elements as a FIFO (first-in-first-out). The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue.
A ConcurrentLinkedQueue is a good choice when many threads share access to a common collection. Like most other concurrent collection implementations, this class does not permit the use of null elements.
This java example spawns off two threads. One puts strings on the queue and the other takes strings off the queue.
public class ConcurrentLinkedQueueExample {
public static void main(String[] args) {
ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<String>();
Thread producer = new Thread(new Producer(queue));
Thread consumer = new Thread(new Consumer(queue));
producer.start();
consumer.start();
}
}
// the producer puts strings on the queue
class Producer implements Runnable {
ConcurrentLinkedQueue<String> queue;
Producer(ConcurrentLinkedQueue<String> queue){
this.queue = queue;
}
public void run() {
System.out.println("Producer Started");
try {
for (int i = 1; i < 10; i++) {
queue.add("String" + i);
System.out.println("Added: String" + i);
//Thread.currentThread().sleep(200);
//Thread.currentThread().wait(200);
}
} catch (Exception ex) {
ex.printStackTrace();
}
}
}
// the consumer removes strings from the queue
class Consumer implements Runnable {
ConcurrentLinkedQueue<String> queue;
Consumer(ConcurrentLinkedQueue<String> queue){
this.queue = queue;
}
public void run() {
String str;
System.out.println("Consumer Started");
for (int x = 0; x < 10; x++) {
while ((str = queue.poll()) != null) {
System.out.println("Removed: " + str);
}
try {
// Thread.currentThread().sleep(500);
// Thread.currentThread().wait(200);
} catch (Exception ex) {
ex.printStackTrace();
}
}
}
}
|
What is ConcurrentSkipListSet?
What is copyOnWriteArrayList and what is the diff between ArrayList and CopyOnWriteArrayList
Answer : CopyOnWriteArrayList is a concurrent Collection class introduced in Java 5 Concurrency API along with its popular cousin ConcurrentHashMap in Java. CopyOnWriteArrayList implements List interface like ArrayList, Vector and LinkedList but its a thread-safe collection and it achieves its thread-safety in a slightly different way than Vector or other thread-safe collection class. As name suggest CopyOnWriteArrayList creates copy of underlying ArrayList with every mutation operation e.g. add or set. Normally CopyOnWriteArrayList is very expensive because it involves costly Array copy with every write operation but its very efficient if you have a List where Iteration outnumber mutation e.g. you mostly need to iterate the ArrayList and don't modify it too often. Iterator of CopyOnWriteArrayList is fail-safe and doesn't throw ConcurrentModificationException even if underlying CopyOnWriteArrayList is modified once Iteration begins because Iterator is operating on separate copy of i. Consequently all the updates made on CopyOnWriteArrayList is not available to Iterator. In this Java Collection tutorial we will see What is CopyOnWriteArrayList in Java, Difference between ArrayList and CopyOnWriteArrayList in Java and One simple Java program example on How to use CopyOnWriteArrayList in Java.
1) First and foremost difference between CopyOnWriteArrayList and ArrayList in Java is that CopyOnWriteArrayList is a thread-safe collection while ArrayList is not thread-safe and can not be used in multi-threaded environment.
2) Second difference between ArrayList and CopyOnWriteArrayList is that Iterator of ArrayList is fail-fast and throw ConcurrentModificationException once detect any modification in List once iteration begins but Iterator of CopyOnWriteArrayList is fail-safe and doesn't throw ConcurrentModificationException.
3) Third difference between CopyOnWriteArrayList vs ArrayList is that Iterator of former doesn't support remove operation while Iterator of later supports remove() operation.
Question : Give the program example for the CopyOnWriteArrayList?
public class CopyOnWriteArrayListExample {
public static void main(String[] args) {
List<String> copyOnWriteArrayList = new CopyOnWriteArrayList<String>(){{
add("1");
add("2");
add("3");
add("4");
add("5");
add("6");
}};
Iterator<String> iterator = copyOnWriteArrayList.iterator();
while(iterator.hasNext()){
String str = iterator.next();
if(str.intern() == "2"){
//Added the element without any exception
copyOnWriteArrayList.add("2");
}
}
iterator = copyOnWriteArrayList.iterator();
while(iterator.hasNext()){
String str = iterator.next();
//iterating over the modified list
System.out.println(str);
}
iterator = copyOnWriteArrayList.iterator();
while(iterator.hasNext()){
String str = iterator.next();
if(str.intern() == "2"){
//Removing the index = 2 element without any issue
copyOnWriteArrayList.remove(2);
}
}
iterator = copyOnWriteArrayList.iterator();
while(iterator.hasNext()){
String str = iterator.next();
//iterating over the modified list
System.out.println(str);
}
iterator = copyOnWriteArrayList.iterator();
while(iterator.hasNext()){
String str = iterator.next();
//Not supported operation
if(str.intern() == "2"){
iterator.remove();
}
}
}
}
|
What is copyOnWriteArraySet?
Answer: CopyOnWriteArraySet is little brother of CopyOnWriteArrayList class. These are special purpose collection classes which was added on JDK 1.5, along with their most popular cousin ConcurrentHashMap. They are part of concurrent collection framework and reside in java.util.concurrent package. CopyOnWriteArraySet is best suited as read-only collection whose size is small enough to copy if some mutative operation happens, for example you can use CopyOnWriteArraySet to store object at start-up of application and let multiple application thread access them during application life time. If an new condition or object comes up during that time, it can also be added into this Set, with incurring cost of creating a new array. One of the most important thing to know about CopyOnWriteArraySet is that it is backed by CopyOnWriteArrayList, which means it also share all basic properties of CopyOnWriteArrayList. Another important thing to remember is that Iterators of this collection class doesn't support remove() operation, trying to remove an element while iterating will result in UnSupportedOperationException. This is done to ensure speed during traversal, traversing this set implementation using Iterator is fast and cannot encounter interference from other threads. Iterators actually rely on unchanging snapshots of the array at the time the iterators were constructed. In short, use CopyOnWriteArraySet if set is small enough to copy on add, set or remove, and main purpose is to read data with occasional updates. Also if you want to remove elements during iteration, don't use this Set implementation because its iterator doesn't support remove(), and throws java.lang.UnsupportedOperationException
What is DelayQueue?
What is EnumSet?
What is JobStateReason?
What is LinkedBlockingDequeue?
What is LinkedBlockingQueue?
What is PriorityBlockingQueue?
What is PriorityQueue?
Answer: An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).
The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.
This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe PriorityBlockingQueue class.
Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).
This class is a member of the Java Collections Framework.
What is RoleList?
What is RoleUnResolvedList?
What is Stack?
Answer : The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.
When a stack is first created, it contains no items.
A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
Deque<Integer> stack = new ArrayDeque<Integer>();
What is SynchronousQueue?
Question: What is the Map interface?
Answer: The Map interface replaces the JDK 1.1 Dictionary class and is used associate keys with values.
Question: What is the Collection interface?
Answer: The Collection interface provides support for the implementation of a mathematical bag - an unordered collection of objects that may contain duplicates.
Question: What is the Set interface?
Answer: The Set interface provides methods for accessing the elements of a finite mathematical set. Sets do not allow duplicate elements.
Question: What's the difference between a queue and a stack
Answer: Stacks works by last-in-first-out rule (LIFO), while queues use the FIFO rule
Question: What are different types of collections
Answer: A collection has no special order and does not reject duplicates
A list is ordered and does not reject duplicates
A set has no special order but rejects duplicates
A map supports searching on a key field, values of which must be unique
Question: Tell me something about Arrays.
Answer: Arrays are fast to access, but are inefficient if the number of elements grow and if you have to insert or delete an element
Question : Difference between HashMap and HashTable / HashMap vs HashTable
Synchronization or Thread Safe : This is the most important difference between two . HashMap is non synchronized and not thread safe.On the other hand, HashTable is thread safe and synchronized.
Null keys and null values : Hashmap allows one null key and any number of null values, while Hashtable do not allow null keys and null values in the HashTable object.
Iterating the values: Hashmap object values are iterated by using iterator .HashTable is the only class other than vector which uses enumerator to iterate the values of HashTable object. difference between hashmap and hashtable
Fail-fast iterator : The iterator in Hashmap is fail-fast iterator while the enumerator for Hashtable is not. According to Oracle Docs, if the Hashtable is structurally modified at any time after the iterator is created in any way except the iterator's own remove method , then the iterator will throw ConcurrentModification Exception. Structural modification means adding or removing elements from the Collection object (here hashmap or hashtable) . Thus the enumerations returned by the Hashtable keys and elements methods are not fail fast.We have already explained the difference between iterator and enumeration.
Performance : Hashmap is much faster and uses less memory than Hashtable as former is unsynchronized . Unsynchronized objects are often much better in performance in compare to synchronized object like Hashtable in single threaded environment.
Superclass and Legacy : Hashtable is a subclass of Dictionary class which is now obsolete in Jdk 1.7 ,so ,it is not used anymore. It is better off externally synchronizing a HashMap or using a ConcurrentMap implementation (e.g ConcurrentHashMap).HashMap is the subclass of the AbstractMap class. Although Hashtable and HashMap has different superclasses but they both are implementations of the "Map" abstract data type.
Question : When to use HashMap ?
Answer: If your application do not require any multi-threading task, in other words hashmap is better for non-threading applications. HashTable should be used in multithreading applications.
Question: What is the Vector class?
Answer: The Vector class provides the capability to implement a growable array of objects What modifiers may be used with an inner class that is a member of an outer class? A (non-local) inner class may be declared as public, protected, private, static, final, or abstract.
Question: What is difference between ArrayList and Vector?Answer :
1) Synchronization - ArrayList is not thread-safe whereas Vector is thread-safe. In Vector class each method like add(), get(int i) is surrounded with a synchronized block and thus making Vector class thread-safe.
2) Data growth - Internally, both the ArrayList and Vector hold onto their contents using an Array. When an element is inserted into an ArrayList or a Vector, the object will need to expand its internal array if it runs out of room. A Vector defaults to doubling the size of its array, while the ArrayList increases its array size by 50 percent.
Question: How can Arraylist be synchronized without using Vector?Answer : Arraylist can be synchronized using:
- Collections.synchronizedList(List list)
- Collections.synchronizedMap(Map map)
- Collections.synchronizedSortedMap(Map map)
- Collections.synchronizedCollection(Collection c)
- Collections.synchronizedSet(Collection c)
- Collection.synchronizedSortedSet(Collection c)
Question : If synchronizedList/map/set is used, if we do any operation in the original collection will it affect the returned collection from the synchronized method or vice versa?
Answer : Both represent the same copy so any operation happened on any copy will affect both the collection, but ideally we should use the synchronzed version as it will give the expected output, but if we try to use the combination of both or just unsynchronized one, then we can't expect the outcome.
Question: If an Employee class is present and its objects are added in an arrayList. Now I want the list to be sorted on the basis of the employeeID of Employee class. What are the steps?
Answer : Follow the steps :
- Implement Comparable interface for the Employee class and override the compareTo(Object obj) method in which compare the employeeID
Now call Collections.sort() method and pass list as an argument. - Now consider that Employee class is a jar file.
- Since Comparable interface cannot be implemented, create Comparator and override the compare(Object obj, Object obj1) method .
- Call Collections.sort() on the list and pass comparator as an argument.
[Repeat]
Question: What is difference between HashMap and HashTable?
Answer : Both collections implements Map. Both collections store value as key-value pairs. The key differences between the two are
1. Hashmap is not synchronized in nature but Hashtable is.
2. The key and value for the hashmap can be null but for Hashtable it should be non null.
3. HashMap permits null values and only one null key, while Hashtable doesn't allow key or value as null.
Question : What is Fail-safe?
Answer: if the Hashtable is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException�
Example as follows:
public class IteratorFailSafeDemo {
public static void main(String[] args) {
Map<String, String> map_1 = new HashMap<String, String>(){
{
put("1","vikash_1");
put("2","vikash_2");
put("3","vikash_3");
put("4","vikash_4");
put("5","vikash_5");
}
};
for(Map.Entry<String, String> keyValue : map_1.entrySet()){
System.out.println(keyValue.getKey()+" ==== "+keyValue.getValue());
if(keyValue.getKey().intern() == "3"){
System.out.println("changing");
map_1.put("9", "vijay");
}
}
}
}
Output
1 ==== vikash_1
2 ==== vikash_2 3 ==== vikash_3 changing Exception in thread "main" java.util.ConcurrentModificationException at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429) at java.util.HashMap$EntryIterator.next(HashMap.java:1463) at java.util.HashMap$EntryIterator.next(HashMap.java:1461) at com.scjp.collections.map.IteratorFailSafeDemo.main(IteratorFailSafeDemo.java:32) |
But if we replace the HashMap with the ConcurrentHashMap then the program will run smoothly.
public class FailSafeTest {
public static void main(String[] args) {
Map<String, String> map_1 = new ConcurrentHashMap<String, String>(){
{
put("1","vikash_1");
put("2","vikash_2");
put("3","vikash_3");
put("4","vikash_4");
put("5","vikash_5");
}
};
for(Map.Entry<String, String> keyValue : map_1.entrySet()){
System.out.println(keyValue.getKey()+" ==== "+keyValue.getValue());
if(keyValue.getKey().intern() == "3"){
System.out.println("changing");
map_1.put("5", "vijay");
map_1.put("9", "sujay");
}
}
}
1 ==== vikash_1
2 ==== vikash_2
3 ==== vikash_3
changing
4 ==== vikash_4
5 ==== vijay
9 ==== sujay
|
Question : Provide the diff between ConcurrentHashMap vs Hashtable vs Synchronized Map?
Answer : Though all three collection classes are thread-safe and can be used in multi-threaded, concurrent Java application, there is significant difference between them, which arise from the fact that how they achieve their thread-safety. Hashtable is a legacy class from JDK 1.1 itself, which uses synchronized methods to achieve thread-safety. All methods of Hashtable are synchronized which makes them quite slow due to contention if number of thread increases. Synchronized Map is also not very different than Hashtable and provides similar performance in concurrent Java programs. Only difference between Hashtable and Synchronized Map is that later is not a legacy and you can wrap any Map to create it's synchronized version by using Collections.synchronizedMap() method. On the other hand, ConcurrentHashMap is especially designed for concurrent use i.e. more than one thread. By default it simultaneously allows 16 threads to read and write from Map without any external synchronization. It is also very scalable because of stripped locking technique used in internal implementation of ConcurrentHashMap class. Unlike Hashtable and Synchronized Map, it never locks whole Map, instead it divides the map in segments and locking is done on those. Though it perform better if number of reader threads is greater than number of writer threads.
Question: What are the classes implementing List interface?
Answer : There are three classes that implement List interface:
1) ArrayList : It is a resizable array implementation. The size of the ArrayList can be increased dynamically also operations like add,remove and get can be formed once the object is created. It also ensures that the data is retrieved in the manner it was stored. The ArrayList is not thread-safe.
2) Vector: It is thread-safe implementation of ArrayList. The methods are wrapped around a synchronized block.
3) LinkedList: the LinkedList also implements Queue interface and provide FIFO(First In First Out) operation for add operation. It is faster if than ArrayList if it performs insertion and deletion of elements from the middle of a list.
Question : Which all classes implement Set interface?
Answer : A Set is a collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. HashSet, SortedSet, LinkedHashSet and TreeSet are the commnly used class which implements Set interface.
SortedSet - It is an interface which extends Set. A the name suggest , the interface allows the data to be iterated in the ascending order or sorted on the basis of Comparator or Comparable interface. All elements inserted into the interface must implement Comparable or Comparator interface.
TreeSet - It is the implementation of SortedSet interface. This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains). The class is not synchronized.
HashSet: This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element. This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets
LinkedHashSet: Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). Note that insertion order is not affected if an element is re-inserted into the set. (An element e is reinserted into a set s if s.add(e) is invoked when s.contains(e) would return true immediately prior to the invocation.)
Question : What is difference between List and a Set?
Answer :
1) List can contain duplicate values but Set doesnt allow. Set allows only to unique elements.
2) List allows retrieval of data to be in same order in the way it is inserted but Set doesnt ensures the sequence in which data can be retrieved.(Except HashSet)
Question : What is difference between Arrays and ArrayList ?
Answer : Arrays are created of fix size whereas ArrayList is of not fix size. It means that once array is declared as :
int [] intArray= new int[6];
intArray[7] // will give ArraysOutOfBoundException.
Also the size of array cannot be incremented or decremented. But with arrayList the size is variable.
Once the array is created elements cannot be added or deleted from it. But with ArrayList the elements can be added and deleted at runtime.
List list = new ArrayList();
list.add(1);
list.add(3);
list.remove(0) // will remove the element from the 1st location.
ArrayList is one dimensional but array can be multidimensional.
int[][][] intArray= new int[3][2][1]; // 3 dimensional array
To create an array the size should be known or initalized to some value. If not initialized carefully there could me memory wastage. But arrayList is all about dynamic creation and there is no wastage of memory.
Question : When to use ArrayList or LinkedList ?
Answer : Adding new elements is pretty fast for either type of list. For the ArrayList, doing random lookup using "get" is fast, but for LinkedList, it's slow. It's slow because there's no efficient way to index into the middle of a linked list. When removing elements, using ArrayList is slow. This is because all remaining elements in the underlying array of Object instances must be shifted down for each remove operation. But here LinkedList is fast, because deletion can be done simply by changing a couple of links. So an ArrayList works best for cases where you're doing random access on the list, and a LinkedList works better if you're doing a lot of editing in the middle of the list.
Question : Consider a scenario. If an ArrayList has to be iterate to read data only, what are the possible ways and which is the fastest?
Answer : It can be done in two ways, using for loop or using iterator of ArrayList. The first option is faster than using iterator. Because value stored in arraylist is indexed access. So while accessing the value is accessed directly as per the index.
Question : Now another question with respect to above question is if accessing through iterator is slow then why do we need it and when to use it.
Answer : For loop does not allow the updation in the array(add or remove operation) inside the loop whereas Iterator does. Also Iterator can be used where there is no clue what type of collections will be used because all collections have iterator.
Question: Which design pattern Iterator follows?Answer : It follows Iterator design pattern. Iterator Pattern is a type of behavioral pattern. The Iterator pattern is one, which allows you to navigate through a collection of data using a common interface without knowing about the underlying implementation. Iterator should be implemented as an interface. This allows the user to implement it anyway its easier for him/her to return data. The benefits of Iterator are about their strength to provide a common interface for iterating through collections without bothering about underlying implementation.
Example of Iteration design pattern - Enumeration The class java.util.Enumeration is an example of the Iterator pattern. It represents and abstract means of iterating over a collection of elements in some sequential order without the client having to know the representation of the collection being iterated over. It can be used to provide a uniform interface for traversing collections of all kinds.
Question: Is it better to have a HashMap with large number of records or n number of small hashMaps?
Answer : It depends on the different scenario one is working on:
1) If the objects in the hashMap are same then there is no point in having different hashmap as the traverse time in a hashmap is invariant to the size of the Map.
2) If the objects are of different type like one of Person class , other of Animal class etc then also one can have single hashmap but different hashmap would score over it as it would have better readability.
Question : Why is it preferred to declare: List<String> list = new ArrayList<String>(); instead of ArrayList<String> = new ArrayList<String>();
Answer : It is preferred because:
If later on code needs to be changed from ArrayList to Vector then only at the declaration place we can do that.
The most important one – If a function is declared such that it takes list. E.g void showDetails(List list);
When the parameter is declared as List to the function it can be called by passing any subclass of List like ArrayList,Vector,LinkedList making the function more flexible
Question: What is difference between iterator access and index access?
Answer : Index based access allow access of the element directly on the basis of index. The cursor of the datastructure can directly goto the 'n' location and get the element. It doesnot traverse through n-1 elements.
In Iterator based access, the cursor has to traverse through each element to get the desired element. So to reach the 'n'th element it need to traverse through n-1 elements.
Insertion,updation or deletion will be faster for iterator based access if the operations are performed on elements present in between the datastructure.
Insertion,updation or deletion will be faster for index based access if the operations are performed on elements present at last of the datastructure.
Traversal or search in index based datastructure is faster.
ArrayList is index access and LinkedList is iterator access.
Question: How to sort list in reverse order?Answer : To sort the elements of the List in the reverse natural order of the strings, get a reverse Comparator from the Collections class with reverseOrder(). Then, pass the reverse Comparator to the sort() method.
List list = new ArrayList();
Comparator comp = Collections.reverseOrder();
Collections.sort(list, comp)
Question : Can we Add null element into Set?Answer : HashSet and LinkedHashSet can contain null, but at max there can be only one null element, not more than one null, but in TreeSet canot contain null, as the comparable/comparator used during the insertion will throw the null pointer exception.
Question : How to make a List (ArrayList,Vector,LinkedList) read only?Answer : A list implemenation can be made read only using Collections.unmodifiableList(list). This method returns a new list. If a user tries to perform add operation on the new list; UnSupportedOperationException is thrown.
Question : What is ConcurrentHashMap?Answer : A concurrentHashMap is thread-safe implementation of Map interface. In this class put and remove method are synchronized but not get method. This class is different from Hashtable in terms of locking; it means that hashtable use object level lock but this class uses bucket level lock thus having better performance.
Question : Which is faster to iterate LinkedHashSet or LinkedList?
Answer : LinkedList.
Question : Which data structure HashSet implements?
Answer: HashSet implements hashmap internally to store the data. The data passed to hashset is stored as key in hashmap with null as value.
Question : Arrange in the order of speed - HashMap , HashTable, Collections.synchronizedMap, concurrentHashmap?Answer : HashMap is fastest, ConcurrentHashMap,Collections.synchronizedMap,HashTable.
Question : What is identityHashMap?
Answer : The IdentityHashMap uses == for equality checking instead of equals(). This can be used for both performance reasons, if you know that two different elements will never be equals and for preventing spoofing, where an object tries to imitate another.
Question : What is WeakHashMap?
Answer : A hashtable-based Map implementation with weak keys. An entry in a 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, that is, made finalizable, finalized, and then reclaimed. When a key has been discarded its entry is effectively removed from the map, so this class behaves somewhat differently than other Map implementations.
Question : What is WeakReference ?
Answer : Weak reference objects, which do not prevent their referents from being made finalizable, finalized, and then reclaimed. Weak references are most often used to implement canonicalizing mappings.
Suppose that the garbage collector determines at a certain point in time that an object is weakly reachable. At that time it will atomically clear all weak references to that object and all weak references to any other weakly-reachable objects from which that object is reachable through a chain of strong and soft references. At the same time it will declare all of the formerly weakly-reachable objects to be finalizable. At the same time or at some later time it will enqueue those newly-cleared weak references that are registered with reference queues.
Question : What is SoftReference?
Answer : Soft reference objects, which are cleared at the discretion of the garbage collector in response to memory demand. Soft references are most often used to implement memory-sensitive caches.
Suppose that the garbage collector determines at a certain point in time that an object is softly reachable. At that time it may choose to clear atomically all soft references to that object and all soft references to any other softly-reachable objects from which that object is reachable through a chain of strong references. At the same time or at some later time it will enqueue those newly-cleared soft references that are registered with reference queues.
All soft references to softly-reachable objects are guaranteed to have been cleared before the virtual machine throws an OutOfMemoryError. Otherwise no constraints are placed upon the time at which a soft reference will be cleared or the order in which a set of such references to different objects will be cleared. Virtual machine implementations are, however, encouraged to bias against clearing recently-created or recently-used soft references.
Direct instances of this class may be used to implement simple caches; this class or derived subclasses may also be used in larger data structures to implement more sophisticated caches. As long as the referent of a soft reference is strongly reachable, that is, is actually in use, the soft reference will not be cleared. Thus a sophisticated cache can, for example, prevent its most recently used entries from being discarded by keeping strong referents to those entries, leaving the remaining entries to be discarded at the discretion of the garbage collector.
Question : Give the example of the WeakHashMap.
Answer : Following is the example of the weakhashmap.
First creating the Key Class
Answer : Weak reference objects, which do not prevent their referents from being made finalizable, finalized, and then reclaimed. Weak references are most often used to implement canonicalizing mappings.
Suppose that the garbage collector determines at a certain point in time that an object is weakly reachable. At that time it will atomically clear all weak references to that object and all weak references to any other weakly-reachable objects from which that object is reachable through a chain of strong and soft references. At the same time it will declare all of the formerly weakly-reachable objects to be finalizable. At the same time or at some later time it will enqueue those newly-cleared weak references that are registered with reference queues.
Question : What is SoftReference?
Answer : Soft reference objects, which are cleared at the discretion of the garbage collector in response to memory demand. Soft references are most often used to implement memory-sensitive caches.
Suppose that the garbage collector determines at a certain point in time that an object is softly reachable. At that time it may choose to clear atomically all soft references to that object and all soft references to any other softly-reachable objects from which that object is reachable through a chain of strong references. At the same time or at some later time it will enqueue those newly-cleared soft references that are registered with reference queues.
All soft references to softly-reachable objects are guaranteed to have been cleared before the virtual machine throws an OutOfMemoryError. Otherwise no constraints are placed upon the time at which a soft reference will be cleared or the order in which a set of such references to different objects will be cleared. Virtual machine implementations are, however, encouraged to bias against clearing recently-created or recently-used soft references.
Direct instances of this class may be used to implement simple caches; this class or derived subclasses may also be used in larger data structures to implement more sophisticated caches. As long as the referent of a soft reference is strongly reachable, that is, is actually in use, the soft reference will not be cleared. Thus a sophisticated cache can, for example, prevent its most recently used entries from being discarded by keeping strong referents to those entries, leaving the remaining entries to be discarded at the discretion of the garbage collector.
Question : Give the example of the WeakHashMap.
Answer : Following is the example of the weakhashmap.
First creating the Key Class
/**
* Creating the Key Object added the hashcode and equals method.
* @author Vikash
*/
class AKey {
String name;
public AKey(String name) {
this.name = name;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
AKey other = (AKey) obj;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}
|
Now below is the code for the same
public class WeakHashMapDemo {
public static void main(String[] args) {
AKey name = new AKey("vikash");
//1: WeakReference<AKey> reference = new WeakReference<AKey>(name);
//2: SoftReference<AKey> reference = new SoftReference<AKey>(name);
//3: Map<AKey, String> hashMap = new HashMap<AKey, String>();
Map<AKey, String> hashMap = new WeakHashMap<AKey, String>();
hashMap.put(name, "Mishra");
// nullifying it so that we have only one ref i.e. weak ref
name = null;
while (true) {
//4: list.add("vikash chandra mishra");
if (!hashMap.containsKey(new AKey("vikash"))) {
System.out.println(hashMap.size());
}
//Running System.gc so that we can have simulate the garbage collection.
//We will not call system.gc immediately, but after sometime,
//as soon as if condition succeeded
try {
Thread.sleep(50);
if (System.currentTimeMillis() % 7 == 0) {
System.gc();
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
|
If we run after sometime we get the following output
0
0
0
0
|
Let's say if we uncomment the 3rd comments.
Let's say we uncomment the 1st comments then we will get the following output
0
0
0
0
0
|
Now lets uncomment the 2nd comment then we will get the following output
Now Let's un comment the 4th and 2nd comment then we will get the following output.
0
0
0
0
0
|
Question : Give the example of the comparator and comparable?
package com.example.comparisons;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class ComparableExample {
public static void main(String[] args) {
List<Employee> empList = new ArrayList<Employee>(){
{
add(new Employee(8,"A"));
add(new Employee(3,"B"));
add(new Employee(2,"C"));
add(new Employee(5,"D"));
add(new Employee(4,"E"));
add(new Employee(7,"F"));
add(new Employee(6,"G"));
add(new Employee(1,"H"));
}
};
Comparator<Employee> cmp = new Comparator<Employee>() {
@Override
public int compare(Employee e1, Employee e2){
return e1.getName().compareTo(e2.getName());
}
};
Collections.sort(empList);
for (Employee e :empList){
System.out.println(e.toString());
}
Collections.sort(empList,cmp);
for (Employee e :empList){
System.out.println(e.toString());
}
}
}
class Employee implements Comparable<Employee>{
int age;
String name;
public Employee(){}
public Employee(int age,String name){
this.age = age;
this.name = name;
}
public int compareTo(Employee obj){
Employee emp = (Employee) obj;
if(this.getAge() > emp.getAge()){
return 1;
}else if(this.getAge() < emp.getAge()){
return -1;
}else{
return 0;
}
}
@Override
public String toString(){
return "Name : "+this.name+" Age : "+this.age;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
|
Name : H Age : 1
Name : C Age : 2
Name : B Age : 3
Name : E Age : 4
Name : D Age : 5
Name : G Age : 6
Name : F Age : 7
Name : A Age : 8
-----------------------------------------------
Name : A Age : 8
Name : B Age : 3
Name : C Age : 2
Name : D Age : 5
Name : E Age : 4
Name : F Age : 7
Name : G Age : 6
Name : H Age : 1
|
Question : How can you sort a HashMap?
package com.example.maps;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;
import java.util.TreeSet;
public class SortHashMap {
public static void main(String[] args) {
//Initializing the Map
Map<Long, String> map = new HashMap<Long, String>(){{
put(5l,"Vikash");
put(2l,"vijay");
put(3l,"Bikash");
put(6l,"Ajay");
put(1l,"Vikash");
put(4l,"Ajay");
}};
//This Map will keep the copy of above map,
//The key will be the values of above map
//if any value is repeated twice, we create
//the chain of keys corresponding to that
//So above map look like this, additionally
//the below map is tree map so it will sort
//its key internally. So after the iteration
//it looks like below structure.
// Ajay --> [4,6]
// Bikash --> [3]
// Vikash --> [1,5]
// vijay --> [2]
//Additionally the values are tree set hence
//when we create the key chain corresponding
//to a value found in the parent map the keys
//are also internally get sorted, hence we have
//Sorting based on values and if we have repeated
//values, then corresponding keys are also
//Internally sorted.
Map<String,TreeSet<Long>> copyMap = new TreeMap<String, TreeSet<Long>>();
for(Map.Entry<Long, String> entry : map.entrySet()){
if(copyMap.containsKey(entry.getValue())){
TreeSet<Long> s = copyMap.get(entry.getValue());
s.add(entry.getKey());
}else{
final Long l = entry.getKey();
copyMap.put(entry.getValue(), new TreeSet<Long>(){{
add(l);
}});
}
}
//This Map will give create the final sorted map,
//the choice of collection here is LinkedHashMap as
//it gurantees the order of entry, hence when we copy
//the entries from copyMap to the sortedMap, we will
//not lost our sorting.
Map<Long, String> sortedMap = new LinkedHashMap<Long, String>();
//copy start as we have values as set we will iterate
//through each values and treat those values as keys
//for the sorted map, the key here coming from the
//copyMap will become values for sorted map, and if values
//which are comming from copyMap are more than one, then
//each entryKey coming from copyMap will be substituted for
//each entryValues coming from copyMap.
for(Map.Entry<String, TreeSet<Long>> entry : copyMap.entrySet()){
for(Long l : entry.getValue()){
sortedMap.put(l, entry.getKey());
}
}
//Final Out come :
//4 Ajay
//6 Ajay
//3 Bikash
//1 Vikash
//5 Vikash
//2 vijay
for(Map.Entry<Long, String> entry : sortedMap.entrySet()){
System.out.println(entry.getKey()+" "+entry.getValue());
}
}
}
|
Question : What is the use of Collections.binarySearch()?
Answer : Searches the specified list for the specified object using the binary search algorithm. The list must be sorted into ascending order according to the natural ordering of its elements (as by the
sort(List) method) prior to making this call. If it is not sorted, the results are undefined. If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found.This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the
RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.- Returns: the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
Question : Prepare A chart for all the ArrayList and LinkedList?
ArrayList
|
LinkedList
| |
interfaces
|
Cloneable
Collection
List
RandomAccess
Serializble
|
Cloneable
Collection
List
Serializble
|
Constant time for crude operation.
|
Yes
|
Yes but slower than ArrayList
|
Synchronized
|
No
| |
How to synchronize
|
List list = Collections.synchronizedList(new ArrayList(...));
| |
Fail fast
|
Yes
| |
Exception on fail fast
|
ConcurrentModificationException
| |
How to increse the space at runtime?
|
ensureCapacity method.
| |
Reduce the space taken by the list
|
trimToSize() method.
| |
Clear the list
|
Clear()
|
Question: Performance wise report of collection.
Answer: Principal features of non-primary implementations :
- HashMap has slightly better performance than LinkedHashMap, but its iteration order is undefined
- HashSet has slightly better performance than LinkedHashSet, but its iteration order is undefined
- TreeSet is ordered and sorted, but slow
- TreeMap is ordered and sorted, but slow
- LinkedList has fast adding to the start of the list, and fast deletion from the interior via iteration
Question : Iteration wise report of Collection.
Answer : Iteration order for above implementations :
- HashSet - undefined
- HashMap - undefined
- LinkedHashSet - insertion order
- LinkedHashMap - insertion order of keys (by default), or 'access order'
- ArrayList - insertion order
- LinkedList - insertion order
- TreeSet - ascending order, according to Comparable / Comparator
- TreeMap - ascending order of keys, according to Comparable / Comparator
Question : What is the difference between comparable and comparator?
Answer: Comparator interface will ask you to implement compare method having return type int and accepts two arguments, 0 means equal, 1 means 1st argument is greater than second argument and -1 is 1st argument is less than 2nd argument.Comparable interface will ask you to implement compareTo method where it will compare with the current object with the passed object via argument, 0,1,-1 has same meaning as for the comparator. The Comparable interface is (IMO) best used to implement a natural order for lists of elements of the class. For example the low-to-high order of numbers represented by the Integer class. This ties in nicely with the order used by the variants of TreeSet, TreeMap, Arrays.sort() and Collections.sort() where no Compataror is specified. The Comparator interface is then used to create exotic orders, where exotic is anything not implemented by the Comparable interface. This also means the most obvious order for elements if a class doesn't implement Comparable, though a subclass may sometimes be a better choice then.Additionally if we are trying to implement comparator of two diffrent type which is practically of no use as if it is passed say e.g. sorting it will get confused if either of two object is of which type. So if we really wanted to use two diffrent type make sure they have a common property and they have common parent class.
Question : Describe all the method of the Collections Utility class.Answer :
- Binary Search : Search for the key, make sure the list is sorted as the search algorthm will be binary search.
- Copy : Copy the list to the destination source.
- disjoint : It will return true of two lists doesn't contain even a single common element.
- frequency : It will return the number of occurrences of key in the list.
- list : If we pass an enumeration then it will return the list out of it.
- max : Returns the maximum element of the given collection, according to the natural ordering of its elements. You can pass an comparator as an extra argument to get the max based on custom ordering.
- min : Returns the minimum element of the given collection, according to the natural ordering of its elements. You can pass an comparator as an extra argument to get the max based on custom ordering
- replaceAll : Replaces all occurrences of one specified value in a list with another.
- reverse : Reverses the order of the elements in the specified list.
- sort : it will sort the list, you can pass a comparator as an extra argument to have custom ordering for sorting.
- synchronizedList : return synchronized list.
- synchronizedMap : return synchronized map.
- synchronizedSet : return the synchronzed set.
Question : What is ListIterator?
Answer : An iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list. A ListIterator has no current element; its cursor position always lies between the element that would be returned by a call to previous() and the element that would be returned by a call to next(). In a list of length n, there are n+1 valid index values, from 0 to n, inclusive.
Question : what is listIterator(index) Method?Answer : Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position in this list. The specified index indicates the first element that would be returned by an initial call to next. An initial call to previous would return the element with the specified index minus one.
This implementation returns a straightforward implementation of the ListIterator interface that extends the implementation of the Iterator interface returned by the iterator() method. The ListIterator implementation relies on the backing list's get(int), set(int, E), add(int, E) and remove(int) methods.
Note that the list iterator returned by this implementation will throw an UnsupportedOperationException in response to its remove, set and add methods unless the list's remove(int), set(int, E), and add(int, E) methods are overridden.
This implementation can be made to throw runtime exceptions in the face of concurrent modification, as described in the specification for the (protected) modCount field.
Question : what is use of set(index, data)?
Answer : Replaces the element at the specified position in this list with the specified element.
Question : What happen when we add element in the set?Answer : It checks if the set already contains the same element, and return false, else it will add that element and returns true.
Question : What happen if we put duplicate element in the set?Answer : It will not allow to add the new value, and will return false if we have tried to add the existing value else return true, additionally the TreeSet will not allow the null value, upon adding it will throw null pointer exception
Question : Is Hashtable threadSafe?Answer : yes its thread safe as all the operation methods are synchronized.
Question : Is it possible to sort the key of TreeMap in non natural order?Answer : Yes Its possible, we need to pass the comparator object to the constructor.
Question : Diff between HashSet VS TreeSet vs LinkedHashSet
Answer :
HashSet
|
LinkedHashSet
|
TreeSet
|
|
How they work internally?
|
HashSet uses HashMap internally to store it’s elements.
|
LinkedHashSet uses LinkedHashMap internally to store it’s
elements.
|
TreeSet uses TreeMap internally to store it’s elements.
|
Order Of Elements
|
HashSet doesn’t maintain any order of elements.
|
LinkedHashSet maintains insertion order of elements. i.e
elements are placed as they are inserted.
|
TreeSet orders the elements according to supplied Comparator. If
no comparator is supplied, elements will be placed in their natural ascending
order.
|
Performance
|
HashSet gives better performance than the LinkedHashSet and
TreeSet.
|
The performance of LinkedHashSet is between HashSet and TreeSet.
It’s performance is almost similar to HashSet. But slightly in the slower
side as it also maintains LinkedList internally to maintain the insertion
order of elements.
|
TreeSet gives less performance than the HashSet and
LinkedHashSet as it has to sort the elements after each insertion and removal
operations.
|
Insertion, Removal And Retrieval Operations
|
HashSet gives performance of order O(1) for insertion, removal
and retrieval operations.
|
LinkedHashSet also gives performance of order O(1) for
insertion, removal and retrieval operations.
|
TreeSet gives performance of order O(log(n)) for insertion,
removal and retrieval operations.
|
How they compare the elements?
|
HashSet uses equals() and hashCode() methods to compare the
elements and thus removing the possible duplicate elements.
|
LinkedHashSet also uses equals() and hashCode() methods to
compare the elements.
|
TreeSet uses compare() or compareTo() methods to compare the
elements and thus removing the possible duplicate elements. It doesn’t use
equals() and hashCode() methods for comparision of elements.
|
Null elements
|
HashSet allows maximum one null element.
|
LinkedHashSet also allows maximum one null element.
|
TreeSet doesn’t allow even a single null element. If you try to
insert null element into TreeSet, it throws NullPointerException.
|
Memory Occupation
|
HashSet requires less memory than LinkedHashSet and TreeSet as
it uses only HashMap internally to store its elements.
|
LinkedHashSet requires more memory than HashSet as it also
maintains LinkedList along with HashMap to store its elements.
|
TreeSet also requires more memory than HashSet as it also
maintains Comparator to sort the elements along with the TreeMap.
|
When To Use?
|
Use HashSet if you don’t want to maintain any order of elements.
|
Use LinkedHashSet if you want to maintain insertion order of
elements.
|
Use TreeSet if you want to sort the elements according to some
Comparator.
|
Links
Comments
Post a Comment