Collections Interview Questions(Theoretical)

1. What is HashMap and Map?

    Map is an interface. Contains methods to manipulate Key-Value based collections. The main methods of Map interface are put(K,V), get(K), Collection<V> values(), Set<K> keySet(), containsKey(), containsValue()
    HashMap is one of implementations of the Map interface based on hashcodes of objects used as keys.

    
2. Difference between HashMap and HashTable? Can we make hashmap synchronized?

    Both implement Map interface. HashTable is synchronized. It is recommended to use HashMap wherever possible. HashTable doesn't allow null keys and values. HashMap allows one null key and any number of null values.
    We can make it synchronized
        Map m = Collections.synchronizedMap(new HashMap());


3. Difference between Vector and ArrayList?

    Both implement List interface. ArrayList is not synchronized. 


4. List vs Set vs Map. Purposes and definitions.

    All three are interfaces.

    List -- storing values in specified order. Provides methods to get the element by its position get(i), finding the element, ListIterator. Known implementations: ArrayList, Vector, LinkedList. The list should be used when the order in which the elements are stored matters.

    Set -- storing only different objects and at most one null element. Known implementations: TreeSet (iterate over the elements in order defined by Comparator, or if the elements implement comparable; provides log(n) performance for basic operations), HashSet -- stores values in buckets defined by their hashcodes. Each bucket is a singly linked list. Provides constant time performance for basic operations. LinkedHashSet

    Map -- for storing key-value pairs. The map cannot contain duplicate keys. Provides three collection views: a set of keys, a collection of values, set of key-value mappings. Know implementations HashMap, EnumMap, TreeMap, LinkedHashMap, WeakHashMap.


5. What is an Iterator?

    It is an interface that contains three methods:  next(), boolean hasNext(), void remove()
    It allows iterating over the collection
    If the class implements iterator then it can be used in foreach loop


6. Pros and cons of ArrayList and LinkedList

    ArrayList -- fast random access.
    LinkedList -- slow random access. Implements Queue interface. Fast deletion of the element.
    If lots of random reads are anticipated use ArrayList.
    If lots of iterations over the whole list and lots of add/delete -- use LinkedList.


7. TreeSet vs LinkedHashSet

    LinkedHashSet is backed by LinkedHashMap. LinkedHashMap is backed by doubly linked list to enforce ordering on the elements contained in the Map.
    If the ordering of the elements in the Set matters to you but you don't want to use a comparator you may use LinkedHashSet since it will enforce order in which the elements were added to the set. Otherwise, use TreeSet


8. Differences between Hashtable, ConcurrentHashMap and Collections.synchronizedMap()

    ConcurrentHashMap allows concurrent modification of the Map from several threads without the need to block them. Collections.synchronizedMap(map) creates a blocking Map which will degrade performance, albeit ensure consistency (if used properly).
    Use the second option if you need to ensure data consistency, and each thread needs to have an up-to-date view of the map. Use the first if performance is critical, and each thread only inserts data to the map, with reads happening less frequently.


9. How are hash codes computed?

    if hashCode() method is defined then it is called to calculate the hashcode
    if it's not defined the default implementation in Object class does the following:

        public int hashCode() {
            return VMMemoryManager.getIdentityHashCode(this);
        }
        
        
        What is the significance of ListIterator? What is the difference b/w Iterator and ListIterator?

    ListIterator allows to perform iteration both ways (first-->last and last-->first)
    From JavaDoc: ListIterator is 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


10. Is it possible that hash code is not unique?

    It's totally possible. Actually, a totally valid hashCode() function could look like this

    int hashCode(){ return 57; 
    
    
     What are the advantages of ArrayList over arrays?
    
        1. ArrayList comes with a number of utility methods (e.g. contains, remove, addAll)
        2. Type safety
        3. Dynamic sizing
        On the other hand, arrays are a little bit faster and take less memory (packing). Arrays are also able to contain values of primitive types while ArrayList can only contain Objects.
    

11. The principle of storing data in a hashtable
    
        HashSet. add(element) -> element.hashCode() -> mod bucketsCount -> store
    HashMap. add(key, value) -> key.hashCode() -> mod bucketsCount -> store(value)


12. Can we put two elements with equal hash code to one hashmap?

    Yes.The hash code of the objects doesn't matter, Only the hashcode of keys. But even if you want to put the keys with the same hashcode, it will be ok, since it just means that key-value pairs will be put into the same bucket


13. Iterator and modification of a List. ConcurentModificationException.

    The iterators returned by this class's iterator method are fail-fast: if the set is 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. So, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

    Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.