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

Differences between ArrayList and LinkedList

"ArrayList" and "LinkedList" are two different implementations of the "List" interface in Java, both used to store collections of elements. However, they have significant differences in terms of performance, memory usage, and behavior in specific operations. Here are some of the differences between "ArrayList" and "LinkedList".

Internal Storage

ArrayList

- Uses a dynamically resizable array to store the elements.
- Direct access to elements is fast using indexes.

LinkedList

- Uses a doubly linked list structure to store the elements.
- Direct access to elements is slower, as it requires traversing the list from the beginning or end.

Inserting and Removing Elements

ArrayList

- Inserting and removing elements in the middle of the list is slower as they require relocating elements in the array.
- The addition/removal at the end is efficient.

LinkedList

- Inserting and removing elements at any position is more efficient as they only involve updating the list pointers.
- Adding/removing at the beginning and end is a little slower due to navigating to the desired location.

Random Access (get)

ArrayList

- It offers direct access to elements using indexes, which is fast.

LinkedList

- Random access is slower as it requires traversing the list to the desired index.

Memory Usage

ArrayList

- Generally, it consumes less memory than LinkedList, as it stores the elements in a contiguous array.

LinkedList

- It consumes more memory due to the additional nodes required to store pointers in the doubly linked list structure.

Iteration and Sequential Operations

ArrayList

- Iteration is efficient using for or foreach loops.
- Good performance in sequential operations.

LinkedList

- Iteration is a little slower as it requires navigation through nodes.
- Performance on sequential operations is generally slower than ArrayList.

Recommended Use

ArrayList

- Recommended when random access and read operations are frequent.
- Good for lists that are not frequently modified after creation.

LinkedList

- Recommended when there are many insertion and removal operations at arbitrary positions.
- Good for lists that are frequently modified after creation.

In summary, the choice between "ArrayList" and "LinkedList" depends on the specific performance and behavior requirements of your application. If random access and read operations are more common, "ArrayList" may be more efficient. If frequent insertions and deletions are required, especially in the middle of the list, "LinkedList" may be more appropriate.