Java.Collections.How is HashMap constructed?

🔧 How is a HashMap constructed?

🔹 At a high level, a HashMap is:

A hash table implementation that maps keys to values using a combination of array + linked list + (sometimes) red-black trees.

---

🔍 Internal Structure

✅ Core Components:

• An array of buckets (indexed via hash codes)
• Each bucket contains a linked list or tree of Node<K, V> entries

📦 Source structure (simplified):

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next; // for collision chaining
}

⚙️ Construction Process (Step-by-Step)

Map<String, Integer> map = new HashMap<>();

1. Initial Capacity & Load Factor
   • Default capacity = 16 buckets
   • Default load factor = 0.75 (i.e., 75% full → resize)
2. Insert key-value pair map.put("apple", 5)
   • Compute hash code of "apple"
   • Calculate bucket index: index = (n - 1) & hash
   • If bucket is empty → create new Node and insert
   • If bucket has collisions (i.e., same index) → use linked list or tree
3. Collision Handling
   • Uses linked list chaining for a few collisions
   • If collision chain exceeds 8 nodes and bucket size > 64 → converts to a red-black tree
4. Resize / Rehash
   • When size > (capacity × load factor) → array doubles, and entries are rehashed

---

🔄 Visual

+---------+          +------------------+
| Bucket0 |  --->    | key="apple"      |
+---------+          | hash=123456      |
| Bucket1 |  --->    | value=5          |
+---------+          | next --> null    |
       ...           +------------------+

If two keys have same index:

+---------+          +------------------+      +------------------+
| Bucket5 |  --->    | key="dog"        | ---> | key="god"        |
+---------+          +------------------+      +------------------+

📌 Constructors

HashMap()                      // default: 16 capacity, 0.75 load
HashMap(int initialCapacity)
HashMap(int initialCapacity, float loadFactor)
HashMap(Map<? extends K, ? extends V> m) // copy constructor

🧠 TL;DR:

HashMap is built from an array of buckets, each holding a linked list or tree of entries.
When you add an entry, it hashes the key, finds the correct bucket, and inserts the entry — handling collisions smartly, resizing as needed.