HashMap in Java

Let’s break down how HashMap works internally (Java 8+ implementation).

---

What Is a HashMap?

HashMap<K, V> is a hash table–based implementation of the Map interface.

It stores data as:

key → value

It provides average O(1) time complexity for:

• put()

• get()

• remove()

---

Core Data Structure

Internally, HashMap uses:

Array of buckets

Each bucket contains:

• A LinkedList (before Java 8)

• A LinkedList OR Red-Black Tree (Java 8+)

Structure simplified:

Node<K,V>[] table

Each array index is called a bucket.

---

How put() Works Internally

When you do:

map.put("apple", 10);

Step 1: Calculate Hash

It calls:

int hash = key.hashCode();

Then applies a hash spreading function:

(hash ^ (hash >>> 16))

This improves distribution.

---

Step 2: Calculate Bucket Index

index = (n - 1) & hash

Where:

• n = array length

• & = bitwise AND (faster than modulo)

This determines where the entry will go.

---

Step 3: Insert into Bucket

Now 3 cases:

Case 1: Bucket is empty

→ Insert new node.

Case 2: Same key already exists

→ Replace value.

Case 3: Collision (different key, same index)

→ Add node to:

• LinkedList (if small)

• Red-Black Tree (if too many collisions)

---

What Is a Collision?

A collision happens when:

Different keys → Same bucket index

Example:

hash("FB") == hash("Ea")

Both go to same bucket.

HashMap handles collisions by chaining.

---

Treeification (Java 8 Improvement)

If a bucket has more than:

8 nodes

It converts the linked list into a:

Red-Black Tree

Why?

• LinkedList lookup = O(n)

• Red-Black Tree lookup = O(log n)

This prevents performance degradation.

---

How get() Works

When you call:

map.get("apple");

Steps:

1. Compute hash

2. Find bucket index

3. Traverse bucket:

   • If LinkedList → iterate

   • If Tree → binary search

4. Compare using:

key.equals(existingKey)

Important:
equals() is used to find the correct key — not ==.

---

Resizing (Rehashing)

Default initial capacity:

16

Default load factor:

0.75

Resize condition:

size > capacity × loadFactor

So:

16 × 0.75 = 12

When 13th element is added:
→ capacity doubles to 32
→ all elements are rehashed

---

Why hashCode() and equals() Matter

HashMap uses:

1. hashCode() → to find bucket

2. equals() → to find exact key inside bucket

If you override one,
you MUST override the other.

Otherwise, HashMap breaks.

---

Internal Node Structure (Simplified)

static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

For tree buckets:

TreeNode extends Node

---

Time Complexity Summary

Operation	Average	Worst Case
put()	O(1)	O(log n)
get()	O(1)	O(log n)
remove()	O(1)	O(log n)

Worst case happens when many collisions occur.

---

Not Thread Safe

HashMap is not synchronized.

For concurrency use:

• ConcurrentHashMap

• Collections.synchronizedMap()

---

Tip

If we ask “How does HashMap work?” we could say in this order:

1. Array of buckets

2. hashCode()

3. Index calculation

4. Collision handling

5. Treeification (Java 8)

6. Resize mechanism

7. equals() importance

Difference between == and .equals() in Java

In Java, == and .equals() are both used to compare things — but they compare different aspects of objects.

---

== (Reference Comparison)

== checks whether two references point to the exact same object in memory.

It does NOT check if the contents are equal.

Example:

String a = new String("hello");
String b = new String("hello");

System.out.println(a == b); // false

Even though both contain "hello", they are different objects in memory.

However:

String a = "hello";
String b = "hello";

System.out.println(a == b); // true

Because Java uses the String Pool, both references point to the same object.

---

.equals() (Content Comparison)

.equals() checks whether two objects are logically equal (same content).

For String, Integer, and many other classes, .equals() is overridden to compare values.

Example:

String a = new String("hello");
String b = new String("hello");

System.out.println(a.equals(b)); // true

Because the contents are the same.

---

Important Difference Summary

Feature	==	.equals()
Compares	Memory address	Object content
Works for primitives?	✅ Yes	❌ No
Works for objects?	✅ Yes	✅ Yes
Can be overridden?	❌ No	✅ Yes

---

Special Case: Primitives

For primitive types (int, double, boolean, etc.):

int x = 5;
int y = 5;

System.out.println(x == y); // true

== compares actual values.

.equals() cannot be used with primitives.

---

Important Warning (Null Safety)

String str = null;
str.equals("hello"); // ❌ NullPointerException

Safer way:

"hello".equals(str); // ✅ Safe

---

Real-World Rule of Thumb

• Use == for primitives

• Use .equals() for object value comparison

• Use == for objects only when you want to check if they are the same instance

---

The difference between "==" and ".equals()" in Java

 In Java, "==" and ".equals()" are used to compare objects, but they have different purposes and behaviors:

"==" (Equality Operator)

The "==" operator checks referential equality, that is, it compares whether two objects reference exactly the same location in memory. This means that it checks whether both sides of the expression point to the same object. 

Example:

String str1 = new String("Hello");
String str2 = new String("Hello");
String str3 = str1;
System.out.println(str1 == str2); // false (different objects)
System.out.println(str1 == str3); // true (same reference)

".equals()"

The ".equals()" method is used to compare the contents of objects, not the memory reference. It is a method defined in the "Object" class and is often overridden by specific classes to provide a meaningful comparison implementation.

Example:

String str1 = new String("Hello");

String str2 = new String("Hello");

System.out.println(str1.equals(str2)); // true (same content)

In the above example, although "str1" and "str2" are different objects in memory, the ".equals()" method is overridden in the "String" class to compare the contents of the strings, resulting in "true".

Important Consideration

In many standard Java classes, such as "String", "equals()" is overridden to provide content comparison. However, in other classes, "equals()" may have the same behavior as "==" unless explicitly overridden.

Integer num1 = new Integer(5);

Integer num2 = new Integer(5);

System.out.println(num1 == num2);         // false (different references)

System.out.println(num1.equals(num2));    // true (same content)

In short, while "==" compares referential equality, ".equals()" compares the contents of objects. In many cases, especially when dealing with complex objects or user-defined classes, it is advisable to use ".equals()" to ensure correct content comparison.