More questions on Java Collection API, continued from our previous post linked here
Q 1. Explain the impacts of variable and fixed hashcodes for objects stored in hash based data structures ?
A. Fixed HashCode: If the hashcode of all the key objects are fixed and all of them return a same number then all the key-value pairs will go in same bucket. In this case the performance of hash based data structure will go down and time complexity for searching will be O(n). Reason is because all the key value pairs goes in same bucket hence jvm will need to traverse all the entries in the bucket to find the suitable key-value pair for the equals() method call.
Variable HashCode: If the hashcode of the key object is random then the location of key-value pair for this key in the bucket will be different everytime, as a result the same key will be stored multiple times in the HashMap with different bucket locations. During retrieval of a key-value pair it is also possible that the value associated is not returned (because of entirely new hashcode) hence the key-value pair be lost forever (or an entirely object may be returned) because jvm won't be able to search the key-value pair with a different hash code.
Q 2. Why are keys suggested to be immutable for HashMap ?
A. The key object are suggested to be immutable so that once the key is stored in a hash based data structure, lets say HashMap, then this key cannot be modified. If the key allowed to be modified after it is stored in HashMap then its hashcode will change (assume hashCode() is implemented properly). This way the key-value pair stored against the original key object will be lost forever because the hashCode is changed and the original key-value pair was kept at older hashcode location.
For this same reason, key are suggested to be immutable, so that they return a unique and same hashcode each time requested on same key object.
Q 3. How to safely create a Empty List or Set ?
A. If your program have such a situation where you need to take decision upon emptiness of List/Set then you should take utmost care while using empty list/set. You need to be careful because an empty List/Set returned by a thread can be filled by other thread and then the program flow may go at entirely different direction with probably wrong results.
The Collections class provides methods to create a empty list and set. They are Collections.emptyList() Collections.emptySet(). In the scenario described above one should use these methods because they return an immutable List/Set which cannot be modified once they are retrieved, this way an application can assure that the empty list/set returned will always remain empty.
Here one can argue that we can also use new HashSet<>() or new ArrayList<>(), but the objects returned by these constructors are not immutable and some other thread can fill them up and as said above if program takes decision upon emptiness of HashSet/List then it would fail in this case.
Q 4. Why HashSet does not have get(Object o)/get(index) method ?
A. Because HashSet is backed by HashMap and all the elements of HashSet are stored in HashMap. Now if we see get(object) of HashMap, it returns the object associated with the passed key, but in case of HashSet all the elements are stored as key and the value associated with all of these keys is a dummy Object(). So if get(object) was available for HashSet it would always return that dummy Object each time. Hence it is not available in HashSet.
get(index) cannot be available in HashSet because it is not linear data structure and the insertion order of elements is not maintained.
So only method remains to check if the object exists in HashSet is contains() which is again backed by HashMaps containsKey() method. If you see the source of contains() in HashSet.class you'll find that it calls map.containsKey() internally.
public boolean contains(Object o) {
return map.containsKey(o);
}
Q 5. What is a NavigableMap ?
A. A navigable map is basically extension of SortedMap of Java. The SortedMap is ordered according to the natural ordering of its keys (which implements Comparable interface), or by an external Comparator which is typically provided at creation of sorted map. The NavigableMap contains all the features of SortedMap, apart from that it provided methods which allows to navigate the Map. This is also important when we don't want to iterate over the whole Map but a small part of the Map. The only one implementation (in jdk) of NavigableMap is the TreeMap. Here is a list of the methods available in NavigableMap:
a) descendingKeySet() and descendingMap() : Both of these methods returns a keySet and the whole map respectively in the descending order. The set and map returned by these methods are backed by the original map hence changes in them will reflect in the original map also.
b) headMap(toKey), tailMap(fromKey) and subMap(fromKey, toKey): The headMap() returns the view of the underlying map whose keys are less than 'toKey'. The tailMap() is just reverse of headMap() and it returns the view of the underlying map whose keys are greater than 'fromKey'. The subMap() returns the view of the underlying map where keys lies between the passed fromKey and toKey.
c) ceilingKey(key), floorKey(key), higherKey(key) and lowerKey(key) : The ceilingKey(key) returns the lowest key in this map which is greater than or equal to the passed key. The floorKey(key) returns the biggest key which is less than or equal to the passed key. The higherKey() method returns the smallest element in this map that is greater than the element passed as parameter to the higherKey() method. lowerKey(key) is just opposite of higherKey(). For eg consider this code:
NavigableMap navigable = new TreeMap();
navigable.put("1", "1");
navigable.put("5", "2");
navigable.put("7", "3");
Object ceiling = navigable.ceilingKey("2"); //The lowest key which is greater than "2" is "5"
Object floor = navigable.floorKey("6"); //The biggest key which is lower than "6" is "5"
Object higherKey = navigable.higherKey("2"); //Returns "5" because the smallest element in the map which is greater than "2" is "5"
Object lowerKey = navigable.lowerKey("5"); //Returns "1" because the biggest element which is lower than "5" is "1"
d) ceilingEntry(), floorEntry(), higherEntry() and lowerEntry(): These methods work similarly to above methods with a difference that these methods returns the Map.Entry instead of Key.
e) pollFirstEntry() and pollLastEntry(): The pollFirstEntry() method pulls(removes) out the "first" entry (key + value) and returns it from the NavigableMap or returns null if the map is empty. The pollLastEntry() pulls (removes) the "last" entry from the map and returns it or returns null if the map is empty. Since a NavigableMap is a Sorted map hence the "First" will always be the smallest element and "Last" will be the largest key according to the element sorting order of the map. Examples:
NavigableMap navigableMap = new TreeMap();
navigableMap.put("1", "1");
navigableMap.put("2", "2");
navigableMap.put("3", "3");
Map.Entry first = navigableMap.pollFirstEntry(); // Removes and Returns Map.Entry with key = "1"
Map.Entry last = navigableMap.pollLastEntry(); // Removes ans Returns Map.Entry with key = "3"
Q 6. What is a BlockingQueue ?
A. A BlockingQueue is an extension of Queue interface which also works in FIFO (First In First Out) mechanism.
BlockingQueue is a queue which is thread safe to insert or retrieve elements from it. A BlockingQueue will block the dequeue operation when the underlying queue is already empty. It will also block the enqueue operations if the underlying queue is already full. The Thread which is trying to put/enqueue an item into the Queue will wait until some other thread dequeues an item and makes some space in the queue. Similarly a thread which is trying to pull/dequeue from an empty queue will be blocked till any other thread puts/enqueues an item into the queue. Blocking queues also have an additional feature to stop waiting when a specific timeout passes.
This functionality makes BlockingQueue a nice way to implement the Producer-Consumer problem, where a producer thread can puts elements until the top limit of BlockingQueue while the consumer thread can pull elements until the min limit is reached with the support of the blocking functionality.
Q 7. How do the remove(key) method internally works on HashMap ?
A. The remove(key) removes and returns the Entry associated with the passed key from the HashMap. The internal implementation of remove() first locates the bucket by the hashCode of the passed key. Now for all the elements in that bucket location, it will check the equality of the key against that key using equals() and removes the element which is found first in the bucket. After removing this element, it is returned to the caller. Refer the below code from HashMap.java:
final Entry removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry prev = table[i];
Entry e = prev;
while (e != null) {
Entry next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
Q 8. How Comparable and Comparator interfaces work ?
A. Both these interfaces are needed when sorting feature needs on custom objects. If an object posses only single sort property for eg. Employees needs to be sorted only on 1 property i.e their age then Comparable can be used. The drawback of using Comparable is that if the sort property needs to be changed then the implementation of Employee object needs to be changed. To overcome this problem Comparators were designed. Comparator provide functionality to apply sort on multiple fields of the object.
Comparable: To provide sorting functionality the candidate object itself needs to implement this interface and override the compareTo(Object). The return type of this method is an int. This method Compares this object with the specified object for sort. It returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object. For eg. consider an Employee class with 2 fields name and age:
public class Employee implements Comparable {
private int age;
private String name;
public int compareTo(Object o) {
Employee e = (Employee) o;
if (this.age > e.getAge()) {
return 1;
} else if (this.age < e.getAge()) {
return -1;
} else {
return 0;
}
}
}
Now if we want to sort a List of Employee objects on their age then we can use Collections.sort() as follows:
Collections.sort(employeeList);
Above method invocation will sort the Employee List in the ascending order of their age. What if we want to sort them on their name ? If we want to stick with Comparable then we need to change the implementation of compareTo() to use name property instead of age. What if we want to revert the sort again to age ? Or what if in same application at one place we need sort on age and other we want sort on name ? With Comparable it is not possible but we can achieve it using Comparator.
Comparator: Unlike Comparable, Comparator Interface have a method compare(obj1, obj2) which compares the passed obj1 and obj2. Since Comparator is not implemented by the candidate Object hence both the objects are passed to compare() method. To provide sorting functionality using Comparator, the candidate object need not to implement this interface. A separate class/inner class should be created which implements the Comparator interface. In the example above if we need sort on name and age respectively we can create 2 Comparator classes i.e EmployeeAgeComparator and EmployeeNameComparator.
public class EmployeeAgeComparator implements Comparator {
public int compare(Employee left, Employee right) {
if (left.getAge() > right.getAge()) {
return 1;
} else if (left.getAge() < right.getAge()) {
return -1;
} else {
return 0;
}
}
}
Now again using Collections api we can use this comparator to sort Employees. For eg.
Collections.sort(employeeList, new EmployeeAgeComparator()); // Sorts employee list as per their age
. . . . . . .
Collections.sort(employeeList, new EmployeeNameComparator()); // Sorts employee list as per their name
Q 9. What is difference between poll() and remove() method of Queue interface?
A. Both the poll() and remove() methods removes and returns the head element from the queue. The only 1 difference in both of them is that if the queue is empty then the invocation of poll() returns null and in case of remove() it throws NoSuchElementException if the queue is empty.
Q 10. What is Deque?
A. The Deque interface is an extension of the java.util.Queue. A Deque is a "Double Ended Queue" where insertion and removal of elements are allowed from both ends of the queue. Below are the details of the methods available in this interface:
a) add(element): Adds an element to the tail of the queue.
b) addFirst(element): Adds an element to the head of the queue.
c) addLast(element): Adds an element to the tail of the queue. It is equivalent to add()
d) offer(element): Adds an element to the tail and returns a boolean to explain if the insertion was successful.
e) offerFirst(element): Adds an element to the head and returns a boolean to explain if the insertion was successful.
f) offerLast(element): Adds an element to the tail and returns a boolean to explain if the insertion was successful.
g) iterator(): Returns an iterator for this deque.
h) descendingIterator(): Returns an iterator that has the reverse order for this deque.
i) push(element): Adds an element to the head.
j) pop(element): Removes an element from the head and returns it.
k) removeFirst(): Removes the element at the head.
l) removeLast(): Removes the element at the tail.
Comments
Post a Comment