🔑 Section 10 · Question #26

What is the Difference Between HashMap and Hashtable

Both HashMap and Hashtable are key-value associative arrays implementing the Map interface. However, Hashtable is an obsolete legacy class from Java 1.0, whereas HashMap is the...

🔑 HashMap equals hashCode 📄 Source Markdown

🟢 Junior Level

Both HashMap and Hashtable are key-value associative arrays implementing the Map interface. However, Hashtable is an obsolete legacy class from Java 1.0, whereas HashMap is the modern standard collection introduced in Java 1.2:

Feature HashMap Hashtable
Thread Safety ❌ Not thread-safe (high speed) ✅ Thread-safe (coarse synchronized methods)
Null Support ✅ Allows 1 null key and unlimited null values ❌ Rejects null keys and values (throws NPE)
Status in JDK Modern standard collection (Java 1.2+) Legacy obsolete class (Java 1.0)
Performance High (no lock contention, bitwise indexing) Low (global monitor lock on every operation)
Collision Resolution Chaining with Red-Black Tree treeification ($O(\log N)$) Singly-linked lists only ($O(N)$) 
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;

public class MapVsHashtableDemo {
    public static void main(String[] args) {
        // Modern approach
        Map<String, String> hashMap = new HashMap<>();
        hashMap.put(null, "Allowed"); // OK

        // Legacy approach
        Map<String, String> hashtable = new Hashtable<>();
        // hashtable.put(null, "Error"); // Throws NullPointerException!
    }
}

Analogy: Hashtable is like an old-fashioned bank vault with a single key where customers enter strictly one at a time: while one person checks their box, all other people wait outside in a bottleneck queue. HashMap is an open office filing shelf for a single worker (or ConcurrentHashMap with individual partitioned locker locks for concurrent access).

🟡 Middle Level

Comprehensive Comparison Matrix

Criterion HashMap Hashtable
Class Hierarchy Extends AbstractMap<K, V> Extends obsolete Dictionary<K, V>
Default Initial Capacity $16$ ($2^4$, power of two) $11$ (prime / odd integer)
Resize Expansion Formula $\text{newCap} = \text{oldCap} \ll 1$ ($2 \times$) $\text{newCap} = (\text{oldCap} \ll 1) + 1$
Bucket Index Calculation (n - 1) & hash (bitwise AND, 1 CPU cycle) (hash & 0x7FFFFFFF) % n (modulo division)
Perturbation Function (h = key.hashCode()) ^ (h >>> 16) None (uses raw key.hashCode())
Iterators Iterator (Strictly Fail-Fast) Iterator (Fail-Fast) + Enumeration (Fail-Safe)
Bucket Data Structure Singly-linked list $\to$ Red-Black Tree (TreeNode) Exclusively singly-linked list

Why Hashtable Is Considered an Anti-Pattern

  1. Coarse-Grained Monitor Locking: Every single public method in Hashtable is decorated with the synchronized keyword: 
    public synchronized V get(Object key) { ... }
public synchronized V put(K key, V value) { ... }

    A single object monitor lock (this) guards the entire structure. Even parallel read-only operations (get) lock each other out, stalling worker threads in an operating system wait queue.

  2. Vulnerability to Hash Collisions: Without treeification, a collision attack (Hash Flooding) or an unbalanced hash function degrades lookup complexity to true $O(N)$ with no recovery mechanism.
  3. Modern Replacements:
    • Single-threaded workloads: HashMap.
    • High-throughput multi-threaded workloads: ConcurrentHashMap (achieves orders of magnitude higher throughput via CAS and per-bucket locking).
    • Entire-map synchronized wrapping (if explicitly mandated): Collections.synchronizedMap(new HashMap<>()).

🔴 Senior Level

Indexing Arithmetic & Resize Mathematics: Modulo vs. Bitwise AND

The JDK architects in 1995 (Hashtable) and 1998 (HashMap) chose fundamentally contrasting mathematical models for bucket distribution:

1. The Hashtable Model:

int index = (hash & 0x7FFFFFFF) % tab.length;
  • The bitmask & 0x7FFFFFFF strips off the two’s-complement sign bit, transforming negative hashCode() values into positive integers in [0, Integer.MAX_VALUE].
  • Modulo division (%) compiles to the CPU instruction idiv, which requires 15–40 CPU clock cycles.
  • The resize formula (oldCapacity << 1) + 1 intentionally produces odd numbers ($11 \to 23 \to 47 \to 95$). Prime and odd numbers reduce hash collision clustering when working with raw, unmixed hash codes.

2. The HashMap Model:

int index = (table.length - 1) & hash;
  • Bitwise AND evaluates in a single CPU clock cycle.
  • Requires the table capacity to remain strictly a power of two ($2^k$).
  • Because a pure power-of-two mask ignores high-order bits, HashMap applies the supplementary bit-mixing perturbation: (h = key.hashCode()) ^ (h >>> 16).

Traversals: Enumeration vs. Iterator

Hashtable supports two distinct traversal APIs:

  1. Legacy Enumeration (hashtable.elements(), hashtable.keys()):
    • Lacks a remove() method.
    • Not fail-fast: It does not inspect modCount! If another thread mutates Hashtable while an Enumeration is traversing, no ConcurrentModificationException is thrown. However, the traversal may skip entries, loop unpredictably, or return stale duplicates.
  2. Collections Iterator (hashtable.keySet().iterator()):
    • Retrofitted in Java 1.2 when Hashtable was adapted to implement Map. It is fully fail-fast and throws ConcurrentModificationException on concurrent structural alterations.

Why Hashtable Remains in the Modern JDK

Why hasn’t OpenJDK deprecated or deleted Hashtable? The primary reason is backward compatibility, notably the foundational java.util.Properties class:

public class Properties extends Hashtable<Object, Object>

Inheriting Properties from Hashtable is widely documented as one of Java’s early design missteps (violating composition in favor of inheritance). Because of this inheritance hierarchy, callers can mistakenly insert non-String objects into a Properties instance via put(), breaking string-oriented methods like getProperty(String key).

4 Tricky Questions

1. Does wrapping a HashMap via Collections.synchronizedMap(map) make it identical to Hashtable?

Answer: No. Significant differences remain:

  1. Null Support: Collections.synchronizedMap(new HashMap<>()) permits one null key and unlimited null values; Hashtable throws NullPointerException.
  2. Treeification: In Java 8+, the wrapped HashMap dynamically treeifies heavily collided buckets into Red-Black Trees ($O(\log N)$); Hashtable always remains a singly-linked list ($O(N)$).
  3. Index Efficiency: HashMap computes indices via bitwise masking (n - 1) & hash (1 cycle) instead of modulo division hash % capacity (15–40 cycles).
  4. Lock Object Customization: Hashtable locks directly on this. synchronizedMap allows passing a custom external mutex object as a constructor argument: Collections.synchronizedMap(map, customLock).

2. Why does put(key, null) in Hashtable throw NullPointerException, even though the first check in put is if (value == null) throw new NullPointerException(); with no explicit check for key?

Answer: An explicit null check for key was unnecessary because calling a method on key naturally triggers an immediate JVM NullPointerException:

public synchronized V put(K key, V value) {
    if (value == null) {
        throw new NullPointerException(); // Explicit check for value
    }
    // ...
    int hash = key.hashCode(); // Implicit NullPointerException if key == null!
}

If key == null, dereferencing key.hashCode() immediately throws NullPointerException. For value, however, no methods are called, necessitating the explicit if (value == null) check.

3. Why is the initial capacity of Hashtable 11, while HashMap defaults to 16?

Answer:

  • In Hashtable, bucket indices are calculated via integer modulo hash % capacity. To minimize clustering and collisions when hashing arbitrary keys without bit-mixing, the capacity should be a prime or odd number. 11 is the nearest prime integer to 10.
  • In HashMap, bucket indices are calculated via bitwise masking (capacity - 1) & hash. This bitmask functions uniformly across all bits only when the capacity is an exact power of two ($2^k$). 16 ($2^4$) was selected as the optimal default power of two.

4. Will hashtable.elements() throw ConcurrentModificationException during concurrent structural modifications?

Answer: No. The hashtable.elements() method returns an Enumeration. The underlying Enumerator implementation does not track or validate the structural mutation counter modCount. Consequently, it never throws ConcurrentModificationException. While it does not throw an exception, it exposes the caller to silent data corruption, skipped nodes, or repeated element visits under concurrent mutation.

🎯 Interview Cheat Sheet

  • Core Difference: Hashtable is a synchronized legacy class from Java 1.0; HashMap is an unsynchronized, highly optimized collection from Java 1.2+.
  • Synchronization: Hashtable synchronizes every method on this (destroying parallel throughput). Modern concurrent code should use ConcurrentHashMap.
  • Null Handling: HashMap allows 1 null key and unlimited null values. Hashtable strictly forbids null keys and null values (throws NPE).
  • Index Math: HashMap computes indices via bitwise mask (n - 1) & hash (1 CPU cycle); Hashtable uses modulo arithmetic hash % capacity (15–40 CPU cycles).
  • Class Hierarchy: HashMap extends AbstractMap; Hashtable extends legacy Dictionary.
  • Persistence Reason: Hashtable survives in OpenJDK primarily to maintain backward compatibility for java.util.Properties extends Hashtable.