Prev Next

Java / Map and its implementations

1. List the differences between HashTable and HashMap in Java collections. 2. Similarities between HashMap and HashTable in Java. 3. What is a resource bundle in Java? 4. What is the Big-O notation for operations in a Hashmap? 5. Is HashMap faster compared to ArrayList in terms of search? 6. Difference between HashMap and ConcurrentHashMap. 7. Is ConcurrentHashmap good for frequently updating concurrent data structure? 8. What are the commonly used implementations of Map in Java? 9. Difference between Collections.synchronizedMap(Map) and ConcurrentHashMap. 10. Difference between Collections.synchronizedMap and Hashtable. 11. Why is ConcurrentHashMap faster than Hashtable in Java? 12. What are the different Reference types available in Java? 13. Which methods you need to override to use an object as key in HashMap ? 14. Why Map does not extend the Collection interface in Java Collections Framework? 15. How Remove method works internally in Java HashMap? 16. Explain NavigableMap in Java collection. 17. Explain rehashing process in Java HashMap. 18. How null key is handled in HashMap? 19. What is the data-structure behind the Java HashMap implementation? 20. Why are immutable objects in HashMap so effective? 21. Why null is not allowed in ConcurrentHashmap? 22. Does ConcurrentHashMap allow null keys and null values ? 23. Difference between remove() and clear() methods in HashMap. 24. Is hashcode method invoked internally when calling get and put method in Java? 25. How hash collision is handled in HashMap? 26. What are the interfaces that TreeMap implements? 27. What interfaces that HashMap implements? 28. Big O notation for TreeMap in Java. 29. Is TreeMap synchronized in Java? 30. Does TreeMap allow null key? 31. Key object constraints on a TreeMap. 32. Does IdentityHashMap use hashcode method? 33. What design pattern that Collections.synchronizedMap implement? 34. Does EnumMap allow null key? 35. Difference between HashMap and IdentityHashMap. 36. What is a ConcurrentSkipListMap? 37. How do you sort a TreeMap by comparing its value? 38. Default initial table size of ConcurrentHashMap. 39. Does Map implement Iterable?
Could not find what you were looking for? send us the question and we would be happy to answer your question.

1. List the differences between HashTable and HashMap in Java collections.
HashMap. HashTable.
HashMap is not synchronized and therefore it is not thread safe. HashTable is internally synchronized and therefore it is thread safe.
HashMap allows maximum one null key and any number of null values.HashTable does not allow null keys and null values.
Iterators returned by the HashMap are fail-fast in nature.Enumeration returned by the HashTable are fail-safe in nature.
HashMap extends AbstractMap class.HashTable extends Dictionary class.
HashMap returns only iterator to traverse.HashTable returns both Iterator as well as Enumeration for traversal.
HashMap is fast.HashTable is slow.
HashMap is not a legacy class.HashTable is a legacy class.
HashMap is preferred in single threaded applications. If you want to use HashMap in multi threaded application, wrap it using Collections. synchronizedMap() method.Although HashTable is there to use in multi threaded applications, now a days it is not at all preferred. Because, ConcurrentHashMap is better option than HashTable.
2. Similarities between HashMap and HashTable in Java.
  • Both store the data in the form of key-value pairs.
  • Both use Hashing technique to store the key-value pairs.
  • Both implement Map interface.
  • Both doesn't maintain insertion order for elements.
  • Both give constant time performance for insertion and retrieval operations.
3. What is a resource bundle in Java?

A resource bundle is represented by a text file containing keys and a text value for each key.

4. What is the Big-O notation for operations in a Hashmap?

Hashmap best and average case for Search, Insert and Delete is O(1) and worst case is O(n).

Hash tables are the implementation of associative arrays. Associative arrays, the abstract data structure mapping keys to values. Implementations of associative arrays using self-balancing binary search trees have lookup that is O(log n) in the worst case.

5. Is HashMap faster compared to ArrayList in terms of search?

The ArrayList has O(n) performance for every search, so for n searches its performance is O(n^2).

The HashMap has O(1) performance for every search (on average), so for n searches its performance will be O(n).

While the HashMap will be slower at first and take more memory, it will be faster for large values of n.

6. Difference between HashMap and ConcurrentHashMap.

In multiple threaded environment HashMap is usually faster than ConcurrentHashMap .

ConcurrentHashMap does not allow NULL values as well as key can not be null in ConcurrentHashMap .While In HashMap there can only be one null key .

ConcurrentHashMap is thread-safe while HashMap is not thread-safe .

7. Is ConcurrentHashmap good for frequently updating concurrent data structure?

Yes.

8. What are the commonly used implementations of Map in Java?
  • HashMap,
  • TreeMap,
  • Hashtable,
  • ConcurrentHashMap,
  • and LinkedHashMap.
9. Difference between Collections.synchronizedMap(Map) and ConcurrentHashMap.

Both maps are thread-safe implementations of the Map interface.

ConcurrentHashMap allows concurrent modification of the Map from several threads without the need to block them while synchronizedMap creates a blocking Map which will degrade performance.

synchronizedMap ensures data consistency and enables every thread to have an up-to-date view of the map.

ConcurrentHashMap is preferred where performance is critical and each thread only inserts data to the map, with reads happening less frequently while use synchronizedMap for data consistency across threads.

10. Difference between Collections.synchronizedMap and Hashtable.

Both are thread-safe implementations of the Map interface.

Both provide the same degree of synchronization.

HashTable is part of Java's legacy code.

The Hashtable class has all its methods synchronized i.e. the locking is done at the method level and hence one can say that the mutex is always at the Hashtable object (this) level.

11. Why is ConcurrentHashMap faster than Hashtable in Java?

ConcurrentHashMap divides the whole map into different segments and locks only a particular segment during the update operation, instead of Hashtable, which locks whole Map.

The ConcurrentHashMap also provides lock-free read, which is not possible in Hashtable. ConcurrentHashMap is faster than Hashtable, especially when a number of the reader is more than the number of writers.

12. What are the different Reference types available in Java?

The different available reference types are WeakReference and softReference (PhantomReference).

These reference types are defined in java.lang.ref package and provided to assist Java Garbage Collector in a case of low memory issues. If you wrap an object with WeakReference then it will be eligible for garbage collected if there are no strong reference. They can later be reclaimed by Garbage collector if JVM is running low on memory.

The java.util.WeakHashMap is a special Map implementation, whose keys are the object of WeakReference, so if only Map contains the reference of any object and no other, those object can be garbage collected if GC needs memory.

13. Which methods you need to override to use an object as key in HashMap ?

To use an object as key in HashMap, it needs to implement equals() and hashCode() method.

14. Why Map does not extend the Collection interface in Java Collections Framework?

Map interface is not compatible with the Collection interface.

Since Map requires key as well as value , for example, if we want to add key-value pair then we will use put(Object key, Object value). So there are two parameters required to add element to the HashMap object . In Collection interface add(Object o) has only one parameter.

Map supports valueSet , keySet as well as other appropriate methods which have just different views from the Collection interface.

15. How Remove method works internally in Java HashMap?

HashMap remove method calls removeEntryForKey method internally, which calculate the final hashValue of the key object, and then use that hashValue in the indexFor(int,int) method to find the first entry object in the appropriate bucket.

Since bucket is a LinkedList we start traversing from the first entry object which we retrieved indexFor method in the bucket. For each entry object in the bucket we compare whether hashValue and the key is equal to the calculated hashValue in the first step and the key passed as a parameter in the remove(key) method.

If desired Entry object is found , then we remove that single entry object from the LinkedList. Removing a single Entry object from the LinkedList is implemented just like removing a single object from the LinkedList.

Entry object returned by the removeEntryForKey method is then stored in the local variable e of type Entry in the remove(key) method. Return the removed entry if it is not null else return null.

16. Explain NavigableMap in Java collection.

NavigableMap Map was added in Java 1.6 that provides navigation capability to Map data structure. It provides methods such as lowerKey() to get keys which is less than specified key, floorKey() to retrieve keys which is less than or equal to specified key, ceilingKey() to get keys which is greater than or equal to specified key and higherKey() to return keys which is greater specified key from a Map.

Similarly navigable methods lowerEntry(), floorEntry(), ceilingEntry() and higherEntry() are available to retrieve map entries.

In addition to the navigation methods, it also enables creating sub-Map, for example, creating a Map from entries of an existing Map using tailMap, headMap and subMap. headMap() method returns a NavigableMap whose keys are less than specified, tailMap() returns a NavigableMap whose keys are greater than the specified and subMap() gives a NavigableMap between a range, specified by toKey to fromKey.

17. Explain rehashing process in Java HashMap.

If the number of elements in the map exceeds a given threshold defined by load-factor (default .75) it will re-size the map once it is 75% occupied.

Java HashMap re-size itself by creating a new bucket array of it's size twice of the previous size of HashMap and puts every old element into that new bucket array. This process is termed as rehashing because it also applies the hash function to find new bucket location.

18. How null key is handled in HashMap?

The null key is handled specially in HashMap using 2 separate methods putForNullKey(V value) and getForNullKey(). Null key is mapped always to 0th Index. This null key scenario is treated in isolated methods to eliminate null key code check and improve performance of get and put methods. The equals() and hashcode() method are not used in case of null key in HashMap.

19. What is the data-structure behind the Java HashMap implementation?

HashMap is backed by the Array of LinkedList.

20. Why are immutable objects in HashMap so effective?

Immutability allows caching the hashcode of different keys which makes the overall retrieval process very fast and suggest that String and various wrapper classes such as Integer provided by Java Collection API are very good HashMap keys.

21. Why null is not allowed in ConcurrentHashmap?

The reason is that if map.get(key) returns null, you can't detect whether the key explicitly maps to null vs the key isn't mapped. In a non-concurrent map, you can check this via map.contains(key), but in a concurrent one, the map might have changed between calls.

22. Does ConcurrentHashMap allow null keys and null values ?

No.

23. Difference between remove() and clear() methods in HashMap.

We can remove entries from HashMap using remove(key) or clear() methods. remove method removes the mapping for the key specified in the parameter while clear() method removes all the entries from the HashMap and returns void.

24. Is hashcode method invoked internally when calling get and put method in Java?

Yes, key object hashcode method is called internally when get or put method is calculated to identify the memory location in hashmap. It is ideal to cache hashcode to avoid calculating every time especially when key is immutable.

25. How hash collision is handled in HashMap?

Prior to Java8, map implementations such as Hashmap handles collision by chaining using a linked list when multiple elements (key) end up in same bucket location. This may degrade the performance from O(1) (one bucket location one key) to O(n) for that particular bucket.

In Java8, to address the performance degrade due to frequent collision, Java8 has started using a balanced tree instead of linked list for storing collided entries to improve performance from O(n) to O(log n).

Java8 still uses Linked list for collision however it converts to balanced tree when number of elements in the same bucket exceeds the TREEIFY_THRESHOLD constant defined by Hashmap. The TREEIFY_THRESHOLD value is 8 so when number of elements exceed 8 linked list switches to balanced tree.

26. What are the interfaces that TreeMap implements?

TreeMap implements,

  • NavigableMap is a subtype of java.util.SortedMap has navigation methods such as ceilingKey(), floorKey(), higherKey() and lowerKey().
  • AbstractMap provides a skeletal implementation of the Map interface, to minimize the effort required to implement this interface.
  • SortedMap provides a total ordering on its keys.
  • Cloneable and Serializable.
27. What interfaces that HashMap implements?

HashMap implements Serializable, Cloneable and Map interfaces.

It also extends java.util.AbstractMap.

28. Big O notation for TreeMap in Java.

TreeMap guarantees log(n) time cost for operatons like containsKey, get, put and remove.

29. Is TreeMap synchronized in Java?

TreeMap is not synchronized, so to achieve thread safety, we may make it synchronized by Collections.synchronizedSortedMap method.

30. Does TreeMap allow null key?

No. TreeMap doesn't allow null keys.

31. Key object constraints on a TreeMap.

The key object need to implement Comparable interface otherwise provide explicit comparator while constructing TreeMap object.

32. Does IdentityHashMap use hashcode method?

No. IdentityHashMap does not use hashCode method instead it uses System.identityHashCode() method. It neither use equals method instead uses == reference equality operator.

IdentityHashMap class is not a general-purpose Map implementation; it intentionally violates Map's general contract to use equals method when comparing objects.

This class is designed for use only in the rare case scenario where reference-equality semantics are required.

33. What design pattern that Collections.synchronizedMap implement?

Decorator design pattern.

34. Does EnumMap allow null key?

No, it does not allow null key however allow null values.

35. Difference between HashMap and IdentityHashMap.
HashMap. IdentityHashMap.
HashMap uses equals method to compare keys. IdentityHashMap uses == operator to compare its keys.
HashMap uses hashcode method to find bucket location. IdentityHashMap uses System.identityHashCode(object) to find bucket location.
HashMap may not be faster when compared to IdentityHashMap as it uses equals method for key comparison. IdentityHashMap may be faster than HashMap as it doesn't use equals method..
HashMap keys need to be immutable. IdentityHashMap doesn't require the key object to be immutable as it doesn't use hashcode or equals method.
36. What is a ConcurrentSkipListMap?

ConcurrentSkipListMap is a TreeMap equivalent concurrent collection.

ConcurrentSkipListMap Implements ConcurrentNavigableMap that keep its key elements sorted in a natural order. The order can also be defined by a custom comparator set while initializing the Map object (using constructor).

This map implementation is introduced in JDK 1.6.

ConcurrentSkipListMap guarantees O(log n) for a wide range of operations.

37. How do you sort a TreeMap by comparing its value?

You can't have the TreeMap itself sort on the values, since that defies the SortedMap specification, "A Map that further provides a total ordering on its keys". However, using an external collection, you can always sort Map.entrySet() either by key, values, or other sorting as needed.

package net.javapedia.algorithms;

import java.util.*;
import java.util.stream.Collectors;

public class SortMapByValueForlowestToHighest {

    public static void main(String[] args) {
        usingLinkedHashMap();
    }

    public static void usingLinkedHashMap() {
            Map<String, Integer> monthToExpense = new HashMap<>();
            monthToExpense.put("Jan",3);
            monthToExpense.put("Feb",5);
            monthToExpense.put("Mar",1);
            monthToExpense.put("Apr",0);
            monthToExpense.put("May",11);
            System.out.println(monthToExpense);
            monthToExpense= monthToExpense.entrySet().stream().sorted(Map.Entry.comparingByValue()).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1,e2)->e1, LinkedHashMap::new));
            System.out.println(monthToExpense);
    }

}

38. Default initial table size of ConcurrentHashMap.

Default size is 16.

39. Does Map implement Iterable?

Map is not an Iterable object, since it doesn't implement the Iterable Interface. We have to use keys() method to get access to an Iterable object, which will be used to iterate over the keys.

«
»
Queue and its implementations

Comments & Discussions