How does HashMap work?

This is one of the classical interview question and generally asked for mid-senior experience level candidates. You will find details here How does HashMap work in Java

What improvements were made to the HasMap in Java 8?

The performance of HashMap was improved in Java 8 under high hash collision condition by using balanced trees (red-black trees) rather than linked lists to store map entries.

The idea is when number of items added to the same bucket, the items will be added to the bucket in a linked list. Hence the performance degrades when there are too many records in the same bucket.

In Java 8, when the number of items goes beyond a certain thresold, the bucket will switch to use balanced tree instead of linked list to store the items or entries. So in Java 8 in case of high hash collisions, the worst case performance will be in O(log n) time complexity. Until Java 8, the worst case time complexity was O(n) for the same situations.

The same technique has been implemented in LinkedHashMap and ConcurrentHashMap also. This technique has not been implemented for HashTable and WeakHashMap. This technique was not added to IdentityHashMap because there will be a rare chance of collisions due to its use of System.identityHashCode() for generating hash codes.

The following things were added to improve the performance of the HashMap:

TREEIFY_THRESHOLD

The value of the above field is 8 and it means when entries added and grows more than 8 entries in a bucket then the bucket will switch from linked list to balanced tree to store the entries. It enhances the speed of search for an entry in the bucket.

This tree is a Red-Black tree. It is first sorted by hash code. If the hash codes are the same, it uses the compareTo method of Comparable interface if the objects implement that interface, else the identity hash code is used.

UNTREEIFY_THRESHOLD

The value of the field is 6 and it means when the number of entries drop below six in a bucket then it switches from balanced tree to linked list for storing entries. The number of entries in a bucket drop when you remove entries from HashMap. UNTREEIFY_THRESHOLD comes into play after re-hashing.

MIN_TREEIFY_CAPACITY

The value of the field is 64 and it is the minimum number of buckets before a certain bucket is transformed into a Tree.

Why is the number of buckets always a power of two in HasMap?

It gives faster operation than using modulo operator. Modulo operator will give you negative on negative numbers and you won’t be able to put an entry into a negative bucket location.

What is the difference between Collection and Collections ?

Collection

It is an interface. A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered. The JDK does not provide any direct implementations of this interface: it provides implementations of more specific subinterfaces like Set and List. This interface is typically used to pass collections around and manipulate them where maximum generality is desired.

Collections

It is a class. This class consists exclusively of static methods that operate on or return collections. It contains various utility methods like sort(), addAll(), copy() etc.

How to search an element in ArrayList ?

Please refer to the example Searching an element in Java ArrayList

What are rules for HashMap ?

HashMap does not allow duplicate keys, however it may contain duplicate values.
HashMap allows null as the key and null as the value.

What is the difference between Hashtable and HashMap ?

There are several differences between HashMap and Hashtable:

Hashtable is synchronized, whereas HashMap is not. This makes HashMap better than Hashtable for non-threaded applications, as non-synchronized objects typically perform better than synchronized ones.

Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.

Iterator in the HashMap is a fail-fast iterator while the Enumerator for the Hashtable is not a fail-fast and throws ConcurrentModificationException if any other Thread modifies the map by adding or removing any element except Iterator’s own remove() method.

How many null keys are allowed in HashMap?

HashMap only allows one null key and many null values. As key can only be one.

Can you create a custom HashMap?

Yes, you can definitely create custom HashMap and you will find more details here How to create a custom Hashmap in Java

How do you create custom Object as a key in HashMap?

You can create custom Object as key for your HashMap.

Here is the tutorial Creating custom Object as key in HashMap.

What are fail-fast iterators in Java ?

A fail-fast system is nothing but immediately report any failure that is likely to occur through the change in the behaviour of the structure of the Collection since iteration has been begun on it. When a problem occurs, a fail-fast system fails immediately. Think of a situation, when we have called iterator on a Collection object, and another thread tries to modify the Collection object, then concurrent modification exception will be thrown.

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.

What are fail-safe iterators in Java?

Fail-Safe iterators don’t throw any exceptions if the collection is modified (by adding, removing or updating) while iterating over it. Because, they iterate on the clone of the collection not on the actual collection.

How do you convert Map to List ?

public static void main(String[] args) {

    Map<String, String> map = new HashMap<String, String>();
    map.put("a", "A");
    map.put("b", "B");
    Set<Entry<String, String>> set = map.entrySet();
    List<Entry<String, String>> list = new ArrayList<Entry<String, String>>(
            set);
    for (Entry<String, String> s : list) {
        System.out.println(s);
    }
}

Output

a=A
b=B

What is the difference between poll and remove methods in Queue interface?

Both poll and remove methods are used to remove elements from Queue and return the head of the Queue. When your Queue is empty and you call to remove method then it will throw exception whereas calling to poll method will return null.

When to use LinkedList or ArrayList ?

Please read through https://www.jeejava.com/arraylist-vs-linkedlist-in-java/

What is the difference between Enumeration and Iterator ?

Enumeration

It has methods – hasMoreElement() and nextElement()
It has longer method names.
It does not have remove() method.
It doesn’t allow a simultaneously navigation and modification on an underlying object. Therefore it has better performance than Iterator.
If you need only navigation ignoring a synchronization, then just use Enumeration.

Iterator

It has methods – hasNext(), next() and remove()
Iterator allows the caller to remove elements from the underlying collection during the iteration. Therefore it has performance drawbacks.
It has shorter method names.
If you need both navigation and synchronization, then use Iterator.

Is Iterator a Class ?

No. It is an interface.

Iterator takes the place of Enumeration in the Java Collections Framework. Iterators differ from enumerations in two ways:

Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics.
Method names have been improved.

Which one is faster ? ArrayList or Vector ? Why ?

ArrayList or Vector – which one is faster; it depends solely on the requirements on the application programming code where you want how to use. Sometimes you may neither want to use ArrayList nor Vector.

Look at the below major differences between them

Vector is synchronized but ArrayList is not. Therefore contents in Vector are thread-safe but not in ArrayList. So if you do not need thread-safety then use ArrayList because being Vector synchronized, it will hit performance.

Vector and ArrayList both store contents using array. So when elements gets inserted into either Vector or ArrayList both need to expand if either of them runs out of empty slots. A Vector defaults to doubling the size of its array, while the ArrayList increases its array size by 50 percent.

Time complexity for retrieving an element from both Vector and ArrayList is O(1). But removing an element from Vector or ArrayList except from end will cost you more time because it needs re-indexing. Time complexity for removing element at end is O(1) but from other location is O(n-i), where n is the number of elements and i is the index from where an element has to be removed and re-indexed(shift) from i.

What is Difference between Iterator and  ListIterator ?

Both are used to retrieve the data from collection. Iterator only traverse in forward direction, but ListIterator can traverse in both forward and backward direction. ListIterator has hasPrevious() and previous() method which is not available in Iterator.

How to use Collectors in Java 8?

Please go through the example Java 8 Collectors

Why keys are immutable in HashMap?

If keys are immutable objects, the object’s hashcode won’t change and it allows caching the hashcode of different keys which makes the overall retrieval process very faster.

On the other hand, for mutable objects, the hashCode might be dependent on fields that could change, if this happens you wont be able to find the key (and its value) in the HashMap since hashCode returns different value.

String, Integer and other wrapper classes are natural candidates of HashMap key, and String is most frequently used key as well because String is immutable and final,and overrides equals and hashcode() method. Other wrapper class also shares similar property.

Lets take the below example,

MyKey key = new MyKey(“hello”); //assume hashCode=12345

Put a value to myHashMap using the above key.

myHashMap.put(key, “value”);

Below code will change the key hashCode() and equals()  but it’s location is not changed when we set name to the key.

key.setName(“hi”); //assume new hashCode=54321

Now when we try to get the value from the HashMap using the key myHashMap.get(new MyKey(“hello”)); it will return null, because HashMap will try to look for key in the same index as it was stored but since key is mutated, there will be no match and it will return null.

Since an immutable object doesn’t change over time, it only needs to perform the calculation of the hash code once. Calculating it again will yield the same value. Therefore it is common to calculate the hash code in the constructor (or lazily) and store it in a field. The hashcode function then returns just the value of the field, which is indeed very fast.

Synchronized vs Concurrent collections in Java?

Both synchronized and concurrent collections provide thread-safety for multi-threaded environment for concurrent access but later provides scalability than former. Prior to Java 1.5, Java programmers had only synchronized collection for multi-threaded environment, which hampered scalability of the system. Java 1.5 introduced concurrent collections like ConcurrentHashMap, ConcurrentNavigableMap, BlockingQueue, which not only provide thread-safety but also improve scalability by using block level locking by partitioning the internal table.

How does HashSet work internally in Java?

This class implements Set interface backed by HashTable (actually hashMap instance). 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, such as, add, remove, contains and size, assuming the hash function disperses the elements properly among the buckets.

HashSet stores element internally in HashMap. Now in HashMap each element is stored as a key/value pair. So how HashSet stores element in it? You will see the below lines of code in HashSet class

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

So when you add elements to the HasSet then your elements are added as keys and PRESENT as values to the map using the following method in HashSet class

public boolean add(E e) {
	return map.put(e, PRESENT)==null;
}

Since keys are unique in a HashMap, it provides uniqueness guarantee of Set interface.

How do you use ConcurrentHashMap in Java?

Please refer to the example How ConcurrentHashMap works in Java

How do you sort collection objects in Java?

Sorting is implemented using Comparable and Comparator in Java and when you call Collections.sort() it gets sorted based on the natural order specified in compareTo() method while Collections.sort(Comparator) will sort objects based on compare() method of Comparator.

What is CopyOnWriteArrayList in Java?

Please refer to the example CopyOnWriteArrayList in Java.

What is NavigableMap in Java?

Please refer to the example NavigableMap in Java.