Set stores unique elements, while Map stores unique keys mapped to values; hash-based implementations use buckets and hashing for average O(1) lookup, while tree-based implementations use Red-Black Trees for O(log n) lookup and sorted data.
Java provides different collection types for different problems.
Two important ones are:
Set→ stores unique elements.Map→ stores data in key-value pairs.
A simple way to remember:
Set
↓
{ 10, 20, 30, 40 }
No duplicate elements
Map
↓
{ 101 → "Aditya"
102 → "Rohit"
103 → "Rohan" }
Unique keys → values
The lecture starts with two important properties of Set:
- Duplicates are not allowed.
- Search/contains is generally constant time
O(1)for hash-based sets.
For Map:
- Data is stored as
(key, value). - Duplicate keys are not allowed.
- Operations such as
put(),get(), andcontainsKey()are generallyO(1)on average for aHashMap.
Suppose we have a list:
List<Integer> list = ...and we want to check whether 50 exists.
With a list, we may have to inspect elements one by one:
10 → 20 → 30 → 40 → 50
In the worst case:
O(n)
If the collection is large, this can become expensive.
A hash-based Set is designed for fast membership checking:
set.contains(50);Average:
O(1)
This makes Set useful for things such as:
- checking whether a username already exists,
- checking whether an email has already been registered,
- tracking unique users,
- checking whether an item has already been processed.
The notes use the idea of a website/email system as an example: if emails must be unique, a Set is a natural choice.
A Set is a collection that does not allow duplicate elements.
Example:
Set<Integer> set = new HashSet<>();
set.add(2);
set.add(3);
set.add(2);The final logical contents are:
{2, 3}
The second 2 is not added as a new element.
The lecture represents this idea visually on page 1 with a collection such as:
7 3 2
and emphasizes that duplicate values are not allowed.
set.add(2);Internally, for a HashSet, this is closely related to putting the element into an underlying HashMap.
Conceptually:
set.add(2);becomes something like:
map.put(2, PRESENT);where PRESENT is a dummy object.
This is one of the most important internal details of HashSet.
This is a common interview question.
How does
HashSetwork internally?
HashSet internally uses a HashMap.
The Set element becomes the key of the internal map.
The value is a dummy object called:
PRESENT
The lecture illustrates this on pages 4–5.
Conceptually:
HashSet
add("Aditya")
|
↓
internal HashMap
|
↓
"Aditya" → PRESENT
So:
set.add("Aditya");is conceptually similar to:
map.put("Aditya", PRESENT);where:
private static final Object PRESENT = new Object();The exact implementation details belong to Java's HashSet implementation, but the important concept is:
HashSet
↓
HashMap
↓
key = Set element
value = PRESENT
Because a HashMap already provides the machinery required for:
- hashing,
- buckets,
- collision handling,
- duplicate-key detection,
- fast lookup.
A Set only needs to answer:
"Does this element exist?"
It does not need an actual meaningful value.
So the implementation can simply use:
element → PRESENT
For example:
"Aditya" → PRESENT
"Rohit" → PRESENT
"Rohan" → PRESENT
The actual values do not matter.
A Map stores data as:
key → value
Example:
Map<Integer, String> map = new HashMap<>();
map.put(101, "Aditya");
map.put(102, "Rohit");
map.put(103, "Rohan");Conceptually:
101 → Aditya
102 → Rohit
103 → Rohan
The lecture uses a roll-number/name example on pages 1 and 3.
Here:
Key = Roll number
Value = Name
A Map does not allow two entries with the same key.
For example:
map.put(101, "Aditya");
map.put(101, "Rohit");The key 101 already exists.
So the second put() does not create another independent key.
Instead, the value associated with 101 is replaced.
Conceptually:
Before:
101 → Aditya
After:
101 → Rohit
So remember:
Map keys are unique. Values do not have to be unique.
Example:
101 → Aditya
102 → Aditya
103 → Rohit
This is completely valid.
Adds or updates a mapping.
map.put(101, "Aditya");Meaning:
101 → Aditya
Retrieves the value associated with a key.
map.get(101);Result:
Aditya
The lecture illustrates this on pages 1 and 8.
Checks whether a key exists.
map.containsKey(101);Result:
true
If the key doesn't exist:
false
| Feature | Set | Map |
|---|---|---|
| Stores | Elements | Key-value pairs |
| Duplicate elements | No | Keys cannot duplicate |
| Main lookup | contains() |
containsKey() / get() |
| Example | {10, 20, 30} |
{101 → "Aditya"} |
| Hash-based average lookup | O(1) |
O(1) |
Part of Collection hierarchy |
Yes | No |
One particularly important point:
Mapis not a subtype ofCollection.
The hierarchy shown on page 11 separates them:
Collection
|
Set
|
HashSet
|
LinkedHashSet
Map
|
HashMap
|
LinkedHashMap
and separately:
Map
|
HashMap
|
LinkedHashMap
Map
|
TreeMap
while:
Set
|
TreeSet
is used for the tree-based set.
This is the core of the lecture.
The basic idea is:
Key
↓
hashCode()
↓
hash
↓
bucket index
↓
bucket
↓
stored node
The lecture explains this flow on pages 3, 5, 6 and 7.
Internally, a HashMap maintains an array-like structure.
Think of it as:
Index
0 1 2 3 4
┌─────┬─────┬─────┬─────┬─────┐
│ │ │ │ │ │
└─────┴─────┴─────┴─────┴─────┘
Each position is called a bucket.
A key is assigned to one of these buckets.
For example:
HashMap
↓
┌─────┬─────┬─────┬─────┬─────┐
│ 0 │ 1 │ 2 │ 3 │ 4 │
└─────┴─────┴─────┴─────┴─────┘
The bucket index is determined using the key's hash.
The lecture simplifies this as:
index = hash % n
where:
hash= hash valuen= number of buckets
The page 5 diagram shows a five-bucket example.
Every Java object can provide a hash code through:
hashCode()For example:
key.hashCode();The hash value helps Java decide where the key should be stored.
Conceptually:
"Aditya"
↓
hashCode()
↓
some hash value
↓
bucket index
The lecture specifically demonstrates this with:
Aditya, Rohit
↓
hashCode()
on page 3.
Suppose:
number of buckets = 5
and suppose a key produces:
hash = 17
Using the simplified calculation from the lecture:
index = hash % n
= 17 % 5
= 2
Therefore:
key → bucket 2
Visualized:
0 1 2 3 4
┌──────┬──────┬──────┬──────┬──────┐
│ │ │ key │ │ │
└──────┴──────┴──────┴──────┴──────┘
↑
bucket 2
The lecture uses the same bucket idea throughout pages 2–7.
This is called a collision.
Example:
Key A → bucket 2
Key B → bucket 2
Both keys want the same bucket.
That is a collision.
The lecture shows this situation on page 2:
bucket 0
bucket 1
bucket 2
bucket 3
↓
Node
↓
Node
↓
Node
The lecture explains chaining using a linked list.
Instead of replacing the old element, Java keeps multiple nodes associated with the same bucket.
Conceptually:
Bucket 2
|
↓
┌──────────┐
│ Key A │
└────┬─────┘
↓
┌──────────┐
│ Key B │
└────┬─────┘
↓
┌──────────┐
│ Key C │
└──────────┘
This is called:
Separate chaining
The lecture contrasts this with open addressing, but the Java HashMap design discussed here uses chaining rather than open addressing.
The notes show a simplified node structure:
class Node<K, V> {
K key;
V value;
int hash;
Node<K, V> next;
}This gives us a very useful mental model.
Each node contains:
key
value
hash
next
For example:
┌────────────────────┐
│ hash │
│ key = 101 │
│ value = "Aditya" │
│ next ─────────────┼────→ next node
└────────────────────┘
The next pointer allows multiple entries to exist in the same bucket.
This node structure is illustrated on page 5.
Suppose we execute:
map.put(101, "Aditya");Conceptually, the process is:
map.put(101, "Aditya")
|
↓
calculate hash
|
↓
find bucket index
|
↓
check bucket
|
↓
┌────────┴─────────┐
│ │
Empty Not empty
│ │
↓ ↓
Create node Search nodes
The lecture breaks this into cases on pages 5–7.
Suppose the calculated bucket is 0.
0 1 2 3 4
┌─────┬─────┬─────┬─────┬─────┐
│ │ │ │ │ │
└─────┴─────┴─────┴─────┴─────┘
↑
empty bucket
Then Java creates a new node:
bucket[0] = new Node(key, value, hash, null)
Conceptually:
bucket[0]
|
↓
┌──────────────────┐
│ key = Aditya │
│ value = PRESENT │
│ hash │
│ next = null │
└──────────────────┘
The lecture shows this as Case 1: Bucket Empty on page 6.
Suppose another key maps to the same bucket.
Now:
bucket[0]
|
↓
Node 1
|
↓
Node 2
|
↓
Node 3
Java traverses the nodes.
Conceptually:
Node temp = head;
while (temp != null) {
...
temp = temp.next;
}The purpose is to determine:
- Does the key already exist?
- If not, where should the new node be added?
This is a very important interview concept.
Java does not simply check:
hash == hash
It also needs to compare the actual keys.
The lecture shows the condition conceptually as:
node.hash == hash
AND
node.key.equals(key)
on pages 6–7.
So duplicate detection is based on:
hashCode()
+
equals()
Suppose:
map.put(new Student(101), "Aditya");Later:
map.get(new Student(101));These may be two different Java objects.
Java needs a way to determine whether they represent the same logical key.
The normal contract is:
If two objects are equal according to
equals(), they must return the samehashCode().
The lecture demonstrates this idea with keys such as:
Aditya → 2023
Rohit → 2023
and shows the relationship between equals() and hashCode() on page 7.
This distinction is extremely important.
Two different keys can have the same hash.
Example:
Key A
hash = 100
Key B
hash = 100
They collide.
But they may still be different:
A.equals(B) == falseTherefore both can exist in the map.
Conceptually:
same hash
↓
same bucket
↓
check equals()
↓
false
↓
different keys → store both
If:
A.equals(B) == truethen they represent the same key and the existing mapping is updated.
Consider:
set.contains("Aditya");Because HashSet uses a HashMap, this is conceptually:
map.containsKey("Aditya");The lecture explicitly shows:
set.contains(Aditya)
↓
contains(key)
↓
map.containsKey(key)
on page 7.
So:
HashSet.contains(x)
↓
HashMap.containsKey(x)
This explains why HashSet can provide fast lookup.
The goal of hashing is to directly identify the bucket where a key should be.
Instead of searching every element:
Node 1
Node 2
Node 3
...
Node n
we first calculate:
hash → bucket
So the search is narrowed down immediately.
Ideal case:
Key
↓
hash
↓
bucket
↓
node
This is approximately:
O(1)
on average.
However, collisions can create multiple nodes in the same bucket.
Therefore, the performance is not literally guaranteed to be O(1) for every situation.
Another major concept is the load factor.
Load factor tells us how full the hash table is allowed to become before resizing.
The lecture represents it as:
load factor = elements / capacity
For example:
elements = 6
capacity = 5
gives:
6 / 5 = 1.2
The lecture also gives:
4 / 5 = 0.8
as an example.
The lecture notes the common Java HashMap configuration:
capacity = 16
load factor = 0.75
Therefore the threshold is:
16 × 0.75 = 12
So the lecture summarizes this as:
elements < 12
before the resize threshold is reached.
A useful mental model:
Capacity = 16
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| | | | | | | | | | | | | | | |
threshold
↓
12
If too many elements are stored relative to the number of buckets, collisions become more likely.
That means buckets can become longer:
bucket
↓
Node
↓
Node
↓
Node
↓
Node
Longer chains mean slower lookup.
Therefore, Java increases the table capacity.
The lecture describes this as:
resize
↓
double the array size
↓
rehash elements
The resize mechanism is discussed on pages 8–9.
Suppose:
capacity = 16
load factor = 0.75
Threshold:
16 × 0.75 = 12
Once the relevant threshold is crossed, the table grows.
Conceptually:
Before:
capacity = 16
After:
capacity = 32
The entries then need to be redistributed according to the new table size.
This is why resizing has a cost.
Normal insertion is usually:
O(1) average
But a resize requires moving/reorganizing entries.
Therefore, a resize operation is more expensive.
This is why load factor and capacity matter.
The overall design is a trade-off:
More buckets
↓
fewer collisions
↓
better lookup
↓
more memory
while:
Fewer buckets
↓
more collisions
↓
potentially slower lookup
↓
less memory
A major optimization was introduced in Java 8.
If a bucket's linked-list chain becomes sufficiently large, Java can convert that bucket's structure into a Red-Black Tree.
The lecture uses:
bucket size > 8
↓
Red-Black Tree
as the key threshold discussed in the lecture.
A linked list search is:
O(n)
in the worst case.
For example:
Bucket
↓
A → B → C → D → E → F → G → H
To find H, we may need to traverse many nodes.
But a balanced search tree can search in:
O(log n)
So:
Long linked list
↓
Red-Black Tree
↓
better worst-case lookup
The lecture compares:
Linked List → O(n)
Red-Black Tree → O(log n)
on page 9.
A Red-Black Tree is a self-balancing Binary Search Tree.
"Self-balancing" means it prevents the tree from becoming excessively skewed.
A simplified tree:
50
/ \
30 70
/ \ / \
20 40 60 80
The lecture uses a similar example on page 10.
Consider a normal BST.
If values are inserted in sorted order:
10
\
20
\
30
\
40
\
50
This starts looking like a linked list.
Searching can become:
O(n)
A self-balancing tree keeps the height controlled.
Therefore:
Balanced tree
↓
height ≈ log n
↓
search ≈ O(log n)
The lecture specifically identifies the Red-Black Tree as the self-balancing structure used for treeification.
Put everything together:
map.put(key, value)
|
↓
hashCode()
|
↓
calculate hash
|
↓
bucket index
|
↓
┌──── bucket ────┐
│ │
↓ ↓
empty non-empty
│ │
↓ ↓
create node compare nodes
|
hash + equals
|
┌─────────┴─────────┐
↓ ↓
same key different key
↓ ↓
update value collision chain
|
↓
linked list / tree
This combines the internal diagrams shown across pages 5–9.
Hash-based collections do not primarily exist to maintain insertion order.
When we need to preserve insertion order, Java provides:
LinkedHashMapLinkedHashSet
The lecture explains that these maintain an additional doubly linked list.
A LinkedHashMap is based on HashMap, but adds links between entries.
Conceptually:
Hash table:
bucket → Node
|
↓
Node
And additionally:
Node A ⇄ Node B ⇄ Node C
So each node has extra pointers such as:
before
after
The page 9 diagram shows a node containing:
key
value
hash
next
before
after
Suppose we insert:
map.put(1, "Aditya");
map.put(2, "Rohit");
map.put(3, "Rohan");The insertion order is:
Aditya → Rohit → Rohan
The doubly linked list helps maintain this order.
Conceptually:
head
↓
Aditya ⇄ Rohit ⇄ Rohan
↑
tail
So when iterating, the insertion order can be preserved.
LinkedHashSet provides Set behavior while preserving insertion order.
Example:
Set<Integer> set = new LinkedHashSet<>();
set.add(30);
set.add(10);
set.add(20);Iteration preserves:
30
10
20
instead of treating the set as an unordered hash structure.
The lecture groups LinkedHashSet and LinkedHashMap together because both use additional links to maintain ordering.
| Feature | HashMap | LinkedHashMap |
|---|---|---|
| Hashing | Yes | Yes |
| Key-value pairs | Yes | Yes |
| Average lookup | O(1) |
O(1) |
| Maintains insertion order | No guarantee | Yes |
| Additional links | No | Yes |
| Memory | Lower | Higher |
The extra linked-list structure requires additional memory.
So this is another trade-off:
HashMap
→ simpler
→ less overhead
LinkedHashMap
→ maintains order
→ extra memory/pointers
Hashing is not always the right solution.
Sometimes we want:
- sorted data,
- minimum/maximum values,
- range queries,
- ordered traversal.
For this, Java provides:
TreeMapTreeSet
The lecture explains these using a self-balancing BST / Red-Black Tree.
A TreeSet stores unique elements in sorted order.
Example:
Set<Integer> set = new TreeSet<>();
set.add(50);
set.add(20);
set.add(70);
set.add(10);
set.add(40);The values are maintained in sorted order:
10
20
40
50
70
The lecture's page 10 example shows a tree containing:
50
├── 30
│ ├── 20
│ └── 40
└── 70
├── 60
└── 80
and then shows the sorted order:
50, 60, 70, 80, 90
as part of its TreeSet discussion.
TreeMap is the Map equivalent.
It stores:
key → value
but maintains keys in sorted order.
Conceptually:
50
/ \
30 70
The tree is organized according to the keys.
So:
TreeMap<Integer, String>keeps its integer keys sorted.
A Binary Search Tree follows:
smaller values → left
larger values → right
For example:
50
/ \
30 70
/ \ / \
20 40 60 80
Here:
20 < 30 < 50
40 < 50
60 > 50
80 > 50
The lecture explicitly writes:
smaller value → left
higher value → right
on page 10.
The major advantage is ordering.
With a hash-based collection:
HashMap / HashSet
the main goal is fast lookup.
With tree-based collections:
TreeMap / TreeSet
the main goal includes maintaining sorted order.
This makes tree-based collections useful for:
- finding smallest value,
- finding largest value,
- range queries,
- ordered iteration,
- sorted keys/elements.
The lecture specifically calls out key sorting, largest/smallest values, and range queries.
| Operation / property | Hash-based | Tree-based |
|---|---|---|
| Average lookup | O(1) |
O(log n) |
| Ordering | Not guaranteed | Sorted |
| Main structure | Hash table | Red-Black Tree |
| Collision handling | Chaining/treeification | Not applicable |
| Range queries | Not the main strength | Strong |
| Min/max | Not the main strength | Efficient |
The key trade-off:
HashMap / HashSet
→ faster average lookup
→ no sorted-order guarantee
TreeMap / TreeSet
→ O(log n)
→ sorted structure
→ useful for range/order operations
This is an important difference.
The lecture explains that tree-based collections need to compare keys.
For example:
key1 < key2
or:
key1 > key2
But null cannot participate in normal key comparison using compareTo().
Therefore, the lecture notes that TreeMap and TreeSet do not allow null keys in this context, because comparison can result in a NullPointerException.
The lecture notes that HashMap can contain:
- one
nullkey - multiple
nullvalues
Example:
Map<Integer, String> map = new HashMap<>();
map.put(null, "Aditya");
map.put(101, null);
map.put(102, null);Conceptually:
null → Aditya
101 → null
102 → null
The lecture explains that the null key is handled specially and is associated with the 0 bucket/index.
Because HashSet internally uses HashMap, its null behavior follows the underlying map's ability to store a null key.
Therefore, a HashSet can contain a single null element.
Example:
Set<String> set = new HashSet<>();
set.add(null);
set.add(null);Only one logical null element exists because a Set cannot contain duplicates.
Remember:
HashMap / HashSet
↓
hash-based
↓
null can be handled specially
while:
TreeMap / TreeSet
↓
comparison-based
↓
null key cannot normally be compared
This difference comes directly from the internal data structures.
The lecture's final page provides a useful overall picture.
Collection
|
Set
|
+----------------+
| |
HashSet TreeSet
|
LinkedHashSet
Map
|
+-------------------+
| |
HashMap TreeMap
|
LinkedHashMap
The important relationship is:
Set → Collection hierarchy
Map → separate hierarchy
Map does not extend Collection.
Keep this diagram in your head:
HashSet
|
↓
HashMap
|
↓
key = Set element
value = PRESENT
Example:
set.add("Aditya");internally conceptually:
map.put("Aditya", PRESENT);This is one of the most useful facts for Java interviews.
Think of a HashMap as:
HashMap
|
↓
bucket array
|
┌────────────┼────────────┐
↓ ↓ ↓
bucket 0 bucket 1 bucket 2
| |
↓ ↓
Node Node
| |
↓ ↓
Node Node
|
↓
Node
Each node conceptually contains:
┌─────────────────────┐
│ hash │
│ key │
│ value │
│ next │
└─────────────────────┘
If the chain becomes sufficiently large:
Linked List
↓
Treeification
↓
Red-Black Tree
For:
map.put(key, value);think:
key.hashCode()
hash → bucket index
Is bucket empty?
Create a new node.
bucket
↓
new Node
Traverse the existing nodes.
Check the hash and key equality.
hash matches?
+
key.equals()?
Update the value.
existing key → new value
Add another node to the collision chain.
If the chain becomes large enough, treeification can occur.
If the map reaches its resize threshold:
resize
↓
larger table
↓
redistribute entries
This is the complete conceptual flow represented across the lecture's internal diagrams.
For objects used as keys, remember:
equals()
+
hashCode()
They must work consistently.
Important rule:
If
a.equals(b)istrue, thena.hashCode()andb.hashCode()must be the same.
Why?
Because HashMap first uses hashing to find the appropriate bucket.
Then it uses equality to determine whether the key is actually the same.
Conceptually:
key
|
↓
hashCode()
|
↓
bucket
|
↓
compare candidate keys
|
↓
equals()
This is why overriding equals() without correctly overriding hashCode() can cause incorrect behavior in hash-based collections.
Suppose:
class Student {
int rollNo;
String name;
}and we use:
Map<Student, String> map = new HashMap<>();The Student object becomes a key.
HashMap needs a consistent definition of:
Are these two Student objects the same key?
That is why equals() and hashCode() are important.
For example:
Student(101, "Aditya")
Student(101, "Aditya")
could be considered logically equal if the class defines equality that way.
Then their hash codes must also match.
These are different concepts.
Two different keys produce the same bucket.
Key A → bucket 2
Key B → bucket 2
A != B
Both can exist.
Two objects are considered the same key.
A.equals(B) == true
The new value replaces/updates the existing mapping.
Remember:
Collision ≠ duplicate
A collision only means:
"These keys ended up in the same bucket."
A duplicate means:
"These keys represent the same logical key."
A useful decision guide:
Use:
HashSet
Example:
unique email IDs
unique user IDs
visited IDs
Use:
HashMap
Example:
roll number → student name
user ID → user object
product ID → product
Use:
LinkedHashSet
LinkedHashMap
Example:
process items in the same order they were inserted
Use:
TreeSet
Example:
sorted scores
sorted IDs
Use:
TreeMap
Example:
student roll number → student
where the roll numbers should remain sorted.
| Collection | Stores | Ordering | Internal idea | Average lookup |
|---|---|---|---|---|
HashSet |
Unique elements | No guaranteed order | HashMap |
O(1) |
LinkedHashSet |
Unique elements | Insertion order | Hashing + linked list | O(1) |
TreeSet |
Unique elements | Sorted order | Red-Black Tree | O(log n) |
HashMap |
Key-value pairs | No guaranteed order | Hash table | O(1) |
LinkedHashMap |
Key-value pairs | Insertion order | Hash table + linked list | O(1) |
TreeMap |
Key-value pairs | Sorted by key | Red-Black Tree | O(log n) |
- Very fast average lookup.
- Good for membership checking.
- Good for key-value lookup.
- Efficient for large datasets.
- No sorted-order behavior.
- Hashing is required.
- Collisions must be handled.
- Resizing requires additional work.
- Memory is needed for the hash table and nodes.
- Hash-based performance.
- Maintains insertion order.
- Extra memory.
- Extra
before/afterlinks.
- Sorted data.
- Predictable ordered traversal.
- Useful for min/max.
- Useful for range-based operations.
O(log n)operations.
- Slower than average hash lookup.
- Requires comparison between keys/elements.
- Tree structure is more complex.
Key
↓
hashCode()
↓
hash
↓
bucket index
↓
bucket
Bucket
|
↓
Node → Node → Node
Long chain
↓
bucket becomes large
↓
Red-Black Tree
↓
O(log n)
HashSet
↓
HashMap
↓
element → PRESENT
Hash buckets
+
doubly linked list
↓
insertion order
Red-Black Tree
↓
sorted order
↓
O(log n)
Wrong:
Set = List but faster
Correct:
Set = unique elements
It is not.
Collection
|
Set
Map
They are separate interfaces.
It prevents duplicate keys, not values.
Valid:
101 → Aditya
102 → Aditya
Not necessarily.
same bucket ≠ same key
Java still checks key equality.
Custom objects used as hash keys need a correct equality/hash-code contract.
O(1) is the average expected lookup complexity.
Collisions and other internal behavior can affect performance.
The lecture specifically explains how large collision chains are optimized using treeification.
If you need:
sorted keys
range queries
smallest/largest
consider:
TreeMap
rather than HashMap.
LinkedHashMap and LinkedHashSet preserve order by maintaining extra links.
That means additional memory.
From the lecture:
HashMap
→ one null key
→ multiple null values
TreeMap
→ null key cannot normally be compared
→ may cause NullPointerException
A collection that does not allow duplicate elements.
A collection-like data structure that stores key-value mappings where keys are unique.
No. Map is a separate interface hierarchy.
HashSet internally uses a HashMap. Set elements become map keys and a dummy PRESENT object is used as the value.
When multiple keys map to the same bucket.
The lecture describes chaining using linked nodes, with treeification for sufficiently large buckets.
Hashing identifies the bucket, while equality determines whether the key is actually the same key.
Approximately:
O(1)
From Java 8+, the lecture describes conversion from a linked-list structure to a Red-Black Tree, improving the search behavior toward O(log n).
It controls when a hash table should resize.
load factor ≈ elements / capacity
0.75
The table grows, commonly by doubling its capacity, and entries are redistributed.
HashMap
→ hashing
→ average O(1)
→ no sorted-order guarantee
TreeMap
→ Red-Black Tree
→ O(log n)
→ sorted keys
HashSet
→ hashing
→ average O(1)
→ no sorted order
TreeSet
→ Red-Black Tree
→ O(log n)
→ sorted elements
To combine hash-based lookup with predictable insertion-order iteration.
SET
│
├── Unique elements
├── contains()
├── HashSet → average O(1)
├── LinkedHashSet → insertion order
└── TreeSet → sorted order, O(log n)
MAP
│
├── key → value
├── keys are unique
├── put()
├── get()
├── containsKey()
├── HashMap → average O(1)
├── LinkedHashMap → insertion order
└── TreeMap → sorted keys, O(log n)
HASHMAP INTERNALS
key
↓
hashCode()
↓
bucket index
↓
bucket
↓
Node
↓
next → next → next
COLLISION
different keys
↓
same bucket
↓
chaining
↓
large chain
↓
Red-Black Tree
HASHSET
HashSet
↓
HashMap
↓
element → PRESENT
LOAD FACTOR
elements / capacity
↓
threshold reached
↓
resize
↓
larger table
If you remember only one picture, remember this:
Java Collections
|
┌────────────────┴────────────────┐
| |
Collection Map
| |
Set ┌─────┴─────┐
| | |
┌──────┼──────┐ HashMap TreeMap
| | | |
HashSet Linked TreeSet LinkedHashMap
|
LinkedHashSet
And for the internals:
HashMap
|
↓
Bucket Array
|
┌──────┴──────┐
↓ ↓
empty bucket collision
| |
new Node linked nodes
|
chain becomes large
|
↓
Red-Black Tree
The core decision is therefore:
Need unique values?
↓
Set
Need key → value?
↓
Map
Need fast average lookup?
↓
HashSet / HashMap
Need insertion order?
↓
LinkedHashSet / LinkedHashMap
Need sorted data / range operations?
↓
TreeSet / TreeMap
The lecture's 11-page notes build exactly around these ideas: Set/Map fundamentals, bucket-based hashing, collision handling, HashSet's internal HashMap, load factor and resizing, treeification, linked ordering, tree-based collections, null handling, and the final collection hierarchy.
-
Set = unique elements.
-
Map = unique keys mapped to values.
-
Mapis separate from theCollectionhierarchy. -
HashSetinternally uses aHashMap. -
HashSetconceptually stores:element → PRESENT -
HashMapuses a bucket-based hashing structure. -
hashCode()helps locate the bucket. -
Collisions occur when multiple keys map to the same bucket.
-
The lecture describes collision handling through chaining.
-
equals()is used along with the hash to identify an existing key. -
Hash-based lookup is
O(1)on average. -
Load factor determines when resizing occurs.
-
The lecture uses the common
0.75load factor and capacity16, giving a threshold of12. -
Java 8+ can treeify sufficiently large collision chains into Red-Black Trees.
-
Tree-based lookup is
O(log n). -
LinkedHashMapandLinkedHashSetmaintain insertion order using extra linked-list connections. -
TreeMapandTreeSetmaintain sorted order using a self-balancing tree. -
Hash-based collections prioritize fast average lookup.
-
Tree-based collections prioritize sorted data and ordered/range operations.
-
HashMapcan have onenullkey and multiplenullvalues. -
Tree-based keys need to be comparable, so
nullkeys are problematic. -
Know these three families:
Hash* → fast average lookup
LinkedHash* → fast lookup + insertion order
Tree* → sorted order + O(log n)
- Why does
HashSetinternally useHashMap? - What exactly is stored as the value inside the internal
HashMapof aHashSet? - What is a hash collision?
- How does Java handle collisions in the lecture's model?
- Why are
hashCode()andequals()both important? - Can two different keys have the same hash?
- What happens when the same key is inserted into a
HashMapagain? - What is the purpose of the load factor?
- Why does a
HashMapresize? - What happens to a large collision chain from Java 8 onward?
- Why is a Red-Black Tree better than a long linked list?
- Why does
LinkedHashMapneedbeforeandafterreferences? - When would you choose
TreeMapoverHashMap? - Why is
TreeSetslower thanHashSetin typical lookup complexity? - Is
Mapa child interface ofCollection? - What is the difference between a collision and a duplicate key?
- How many
nullkeys can aHashMapcontain? - Why is
nullproblematic for aTreeMapkey? - What is the difference between
HashSet,LinkedHashSet, andTreeSet? - What is the difference between
HashMap,LinkedHashMap, andTreeMap?