Videos / DSA

Episode 8 of 22 · DSA, end to end

Sets and maps: the hash table, and the tree that keeps order

Chapters

1. From index to value0:00
2. Keys are not positions0:16
3. Set, map, three operations0:32
4. The two serious answers0:49
5. Why not just a vector1:08
6. Compute a place, or a direction1:24
7. What a hash function is1:40
8. Folding it into buckets1:57
9. Collisions are guaranteed2:16
10. Chaining, a list per bucket2:35
11. Probing the flat array2:53
12. The erase trap3:10
13. Load factor3:28
14. The threshold that triggers growth3:47
15. Rehash, and every index changes4:05
16. The doubling series4:23
17. The one slow insert4:40
18. Reserve it up front4:58
19. Open the dictionary in the middle5:16
20. The rule of the tree5:31
21. Sorted input, straight line5:47
22. Rotations and the height bound6:04
23. What order buys you6:22
24. Lower bound and upper bound6:39
25. A pile and a filed book6:55
26. The decision table7:10
27. Constants and cache misses7:26
28. The anti-hash test7:43
29. One bucket, quadratic time8:00
30. Salt the hash8:18
31. A pair as a key8:35
32. Must, and should8:52
33. The exclusive or bug9:11
34. Combining the halves properly9:27
35. Equality has to agree9:45
36. The custom key checklist10:04
37. The whole thing10:22

Sets and maps: the hash table, and the tree that keeps order. A row of numbered boxes. Box zero, box one, box two. Give an array a position and it hands you the value back instantly, because the address is arithmetic. Now the question this wh

Mark as watchedSaved in this browser only.