Hashing.md

Hashing

Hashing

🧠 What is HashMap?

• A part of Java's Collection Framework.
• Implements the Map interface.
• Stores data as key-value pairs.
• Allows one null key and multiple null values.
• Unordered — does not maintain insertion order.

---

🛠️ Internal Working of HashMap

Step-by-step:

1. When you call put(key, value):

   • Java calls hashCode() of the key.
   • Calculates bucket index using:

     index = (n - 1) & hash(key);

   • If no collision → stores the entry.
   • If collision → resolves using chaining (linked list or tree).

2. When calling get(key):

   • Uses hashCode() to find the bucket.
   • Traverses the list/tree to find the matching key using equals().

---

📊 HashMap Data Structure (Java 8+)

• Array of Node<K, V>
• Each bucket:
  • Empty ➝ null
  • Single entry ➝ Node
  • Collisions ➝ Linked list or Tree (TreeMap-like)

Treeify Conditions:

• If number of entries in a bucket > 8
• And overall map size > 64
• Then linked list → Red-Black Tree (for faster lookup)

---

📦 Constructors of HashMap

HashMap<K, V> map = new HashMap<>();
HashMap<K, V> map = new HashMap<>(initialCapacity);
HashMap<K, V> map = new HashMap<>(initialCapacity, loadFactor);
HashMap<K, V> map = new HashMap<>(anotherMap);

Connect with me:

---