Java Collections Interview Questions Part 3: HashMap Internals, TreeMap, WeakHashMap and More

Q1. How does HashSet compare with TreeSet?

	HashSet	TreeSet
Backed by	HashMap (hash table)	TreeMap (red-black tree)
Order	None guaranteed	Sorted, natural or by Comparator
add / contains	O(1) average	O(log n)
Duplicate check	hashCode() and equals()	compareTo() or compare() returning 0
Mixed types	Allowed	Must be mutually comparable, else ClassCastException
null	One null allowed	Not allowed with natural ordering, even as the first element

Choose TreeSet when you need sorted output or range queries like ceiling() and headSet(); otherwise HashSet is faster.

Q2. What is Map.Entry?

Entry is a nested interface inside Map. Each key-value pair in a map is represented as an Entry with getKey(), getValue() and setValue(). You mostly meet it when looping over entrySet(), which is the efficient way to read keys and values together.

Map<String, Integer> stock = new TreeMap<>(Map.of("pen", 10, "book", 4));
for (Map.Entry<String, Integer> e : stock.entrySet()) {
    e.setValue(e.getValue() * 2);
    System.out.println(e.getKey() + " -> " + e.getValue());
}
// book -> 8
// pen -> 20

Map.entry(k, v) (Java 9) creates a standalone, immutable entry; calling setValue() on it throws UnsupportedOperationException.

Q3. Explain HashMap and how it works internally.

HashMap stores key-value pairs with unique keys. Duplicate values are fine. It allows one null key and any number of null values, does not keep any order, and is not synchronized. get() and put() are O(1) on average.

Inside, it keeps an array of buckets. For each key it takes hashCode(), mixes the high bits into the low bits, and uses (table length - 1) & hash to pick a bucket. Keys that land in the same bucket (a collision) are kept in a linked list, and equals() decides whether a key is already present. The default table has 16 buckets and a load factor of 0.75, so once there are more than 12 entries the table doubles and entries are spread out again.

Since Java 8, if one bucket grows past 8 entries (TREEIFY_THRESHOLD is 8) and the table has at least 64 buckets, that bucket is turned into a red-black tree, so the worst case becomes O(log n) instead of O(n). With a smaller table, HashMap resizes instead of treeifying. A tree bin goes back to a list when it shrinks to 6 entries or fewer during a resize.

Q4. What does LinkedHashMap add over HashMap?

LinkedHashMap extends HashMap and adds a doubly linked list through all entries, so iteration follows insertion order. It arrived in Java 1.4. It can also be created in access order (pass true as the third constructor argument), where every get() moves the entry to the end. Together with removeEldestEntry(), that gives you a simple LRU cache:

Map<String, Integer> cache = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<String, Integer> e) {
        return size() > 3;
    }
};
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
cache.get("a");                       // "a" is now most recently used
cache.put("d", 4);                    // evicts "b"
System.out.println(cache.keySet());   // [c, a, d]

Q5. Compare HashMap and LinkedHashMap.

	HashMap	LinkedHashMap
Structure	Hash table	Hash table plus doubly linked list
Iteration order	Not defined	Insertion order, or access order if requested
Memory	Less	Two extra links per entry
Since	Java 1.2	Java 1.4

Since Java 21, LinkedHashMap also implements SequencedMap, with firstEntry(), lastEntry(), pollFirstEntry() and reversed().

Q6. What is IdentityHashMap?

A Map that compares keys by reference (==) and uses System.identityHashCode() instead of equals() and hashCode(). Two different String objects with the same text are therefore two separate keys. It is meant for special jobs such as tracking which objects have already been visited during serialization or a deep copy, not for normal application data.

String k1 = new String("id");
String k2 = new String("id");
// HashMap with k1 and k2 has size 1
// IdentityHashMap with k1 and k2 has size 2

Q7. How does HashMap differ from Hashtable?

	HashMap	Hashtable
Thread safety	Not synchronized	Methods are synchronized
Speed	Faster in one thread	Slower, every call takes a lock
null	One null key, many null values	No null keys or values (NullPointerException)
Iteration	Fail-fast Iterator	Iterator, plus legacy Enumeration
Since	Java 1.2	Java 1.0, extends Dictionary

For a map shared between threads, use ConcurrentHashMap, not Hashtable. It allows concurrent reads and fine-grained locking on writes, and it also rejects null keys and values.

Q8. What is WeakHashMap?

A Map whose keys are held through weak references. In a normal HashMap, the map itself keeps every key alive, so a key object is never garbage collected while it is in the map. In a WeakHashMap, if nothing outside the map refers to a key any more, the collector may clear it, and the entry disappears from the map on a later operation.

It is used for caches or metadata attached to objects you do not own, where you do not want the map to cause a memory leak. Note that values are held strongly, so a value that refers back to its own key keeps the entry alive.

Q9. What are the key features of TreeMap?

• Entries are kept sorted by key, using natural order or a Comparator.
• It is a red-black tree, so get, put and remove are O(log n).
• Keys are unique; values may repeat.
• With natural ordering, keys must be mutually comparable, or you get ClassCastException.
• null keys are not allowed with natural ordering, not even in an empty map (the "first entry can be null" rule in old notes was removed in Java 7). null values are fine.
• As a NavigableMap it offers firstKey(), floorKey(), ceilingEntry(), headMap() and tailMap(), which are great for range lookups.

Q10. What are the key features of Hashtable?

• A legacy key-value class from Java 1.0 that extends Dictionary and was later made to implement Map.
• Uses a hash table, so keys are unique while values can repeat.
• Rejects null keys and null values.
• Every public method is synchronized.
• No defined iteration order.

Keep it only for old code. In new code use HashMap for one thread and ConcurrentHashMap for many.

Q11. What is PriorityQueue?

PriorityQueue is a Queue where poll() always removes the smallest element according to natural order or a Comparator. Internally it is a binary heap stored in an array, so offer() and poll() are O(log n) and peek() is O(1).

• Duplicates are allowed. (Some older answers say otherwise; that is wrong.)
• null is not allowed.
• Iterating with a for loop does not give sorted order; only repeated poll() does.
• For a max-heap, pass Comparator.reverseOrder().

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 3, 1));
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");   // 1 1 3 5

Q12. What is the Arrays class?

java.util.Arrays is a utility class of static methods for working with arrays: sort(), binarySearch() on a sorted array, fill(), copyOf(), copyOfRange(), equals(), toString() for printing, stream(), and asList(). Since Java 9 it also has compare() and mismatch().

One common trap: Arrays.asList() returns a fixed-size list backed by the array. You can set() elements, but add() or remove() throws UnsupportedOperationException. Wrap it in new ArrayList<>(...) if you need to grow it.

Q13. Why is ArrayList usually faster than Vector?

Vector's methods are synchronized, so every call acquires and releases a lock, even when only one thread ever uses the list. ArrayList has no locking, so it does less work per call. Modern JVMs can sometimes remove uncontended locks, but the overhead is still there in general.

Note that the lack of locking also means ArrayList is not safe to modify from several threads at once; it is faster precisely because it does not try.

Q14. For frequent lookups by index, should you use ArrayList or LinkedList?

ArrayList. It is backed by an array, so get(i) jumps straight to the element in O(1). LinkedList has to walk node by node from the nearer end, which is O(n). ArrayList implements the RandomAccess marker interface to advertise exactly this.

Some older answers to this question say the reason is that LinkedList is synchronized. That is incorrect: neither ArrayList nor LinkedList is synchronized. The difference is purely the data structure.

Q15. How do you make an ArrayList thread-safe?

Two standard options:

• Collections.synchronizedList(list) returns a wrapper whose methods lock on the wrapper. Single calls are safe, but iteration is not, so you must loop inside synchronized on the wrapper you got back.
• CopyOnWriteArrayList copies its internal array on every write. Reads and iteration need no locking and never throw ConcurrentModificationException. It suits lists that are read often and changed rarely, like listener lists.

List<String> fruits = Collections.synchronizedList(new ArrayList<>());
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Mango");

synchronized (fruits) {          // lock the wrapper, not the original list
    for (String f : fruits) {
        System.out.println(f);
    }
}

Quick revision

• HashMap: 16 buckets by default, load factor 0.75, doubles on resize.
• A bucket becomes a red-black tree past 8 entries, only if the table has at least 64 buckets.
• LinkedHashMap in access-order mode plus removeEldestEntry() is a ready-made LRU cache.
• TreeMap and TreeSet reject null keys with natural ordering, even when empty.
• PriorityQueue allows duplicates, rejects null, and is sorted only through poll().
• Use ConcurrentHashMap instead of Hashtable, and lock the wrapper when iterating a synchronizedList.

Frequently asked questions