Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Design HashMap
Bookmark
Direct Address
Chaining
Open Addressing
Input
Put, Get, Remove
Collision + Tombstone Reuse
Update + Re-insert
operations
=
put(1, 10), put(2, 20), get(1), put(12, 30), get(12), remove(1), get(1)
put(1, 10)
put(2, 20)
get(1)
=
?
put(12, 30)
get(12)
=
?
remove(1)
get(1)
=
?
0
1
2
3
4
5
6
7
8
9
10
11
12
index = key · no hashing · one slot reserved per possible key
put(1, 10)
put(2, 20)
get(1)
=
?
put(12, 30)
get(12)
=
?
remove(1)
get(1)
=
?
0
1
2
3
4
5
6
7
8
9
10
11
12
index = key · no hashing · one slot reserved per possible key
put(1, 10)
put(2, 20)
get(1)
=
?
put(12, 30)
get(12)
=
?
remove(1)
get(1)
=
?
0
1
10
2
3
4
5
6
7
8
9
10
11
12
put(1, 10)
done
put(1, 10)
put(2, 20)
get(1)
=
?
put(12, 30)
get(12)
=
?
remove(1)
get(1)
=
?
0
1
10
2
20
3
4
5
6
7
8
9
10
11
12
put(2, 20)
done
put(1, 10)
put(2, 20)
get(1)
=
?
put(12, 30)
get(12)
=
?
remove(1)
get(1)
=
?
0
1
10
2
20
3
4
5
6
7
8
9
10
11
12
key 1
read store[
1
]
put(1, 10)
put(2, 20)
get(1)
=
10
put(12, 30)
get(12)
=
?
remove(1)
get(1)
=
?
0
1
10
2
20
3
4
5
6
7
8
9
10
11
12
put(12, 30)
done
put(1, 10)
put(2, 20)
get(1)
=
10
put(12, 30)
get(12)
=
?
remove(1)
get(1)
=
?
0
1
10
2
20
3
4
5
6
7
8
9
10
11
12
30
get(12)
done
put(1, 10)
put(2, 20)
get(1)
=
10
put(12, 30)
get(12)
=
?
remove(1)
get(1)
=
?
0
1
10
2
20
3
4
5
6
7
8
9
10
11
12
30
get(12)
done
put(1, 10)
put(2, 20)
get(1)
=
10
put(12, 30)
get(12)
=
30
remove(1)
get(1)
=
?
0
1
2
20
3
4
5
6
7
8
9
10
11
12
30
key 1
store[1] ←
-1
cleared
put(1, 10)
put(2, 20)
get(1)
=
10
put(12, 30)
get(12)
=
30
remove(1)
get(1)
=
?
0
1
2
20
3
4
5
6
7
8
9
10
11
12
30
key 1
read store[
1
]
put(1, 10)
put(2, 20)
get(1)
=
10
put(12, 30)
get(12)
=
30
remove(1)
get(1)
=
-1
0
1
2
20
3
4
5
6
7
8
9
10
11
12
30
All operations complete
algo
master
.
io
Step:
Direct address: the key is the index, so there is nothing to hash
0 / 25
Input
Put, Get, Remove
Collision + Tombstone Reuse
Update + Re-insert
operations
=
put(1, 10), put(2, 20), get(1), put(12, 30), get(12), remove(1), get(1)
0 / 25
algo
master
.
io
Step:
Direct address: the key is the index, so there is nothing to hash
