Chapters:
- 0:00:00 - Announcement
- 0:00:41 - Why Implement Hash Table?
- 0:02:07 - Where we could use the Hash Table?
- 0:03:15 - New Project
- 0:03:40 - Nob build
- 0:07:54 - The Problem Description
- 0:08:48 - Downloading all the Works of Shakespeare
- 0:10:40 - Reusability of Nob
- 0:11:12 - Reading the File
- 0:13:09 - Tokenizing the File
- 0:16:23 - Better Tokenization
- 0:20:28 - Linear Associative Array
- 0:23:58 - Total Amount of Tokens
- 0:25:00 - find_key()
- 0:27:07 - Collecting Frequencies
- 0:29:03 - Nob Subcommands
- 0:31:13 - Smaller File
- 0:32:36 - File Path via Command Arguments
- 0:35:32 - Measuring Time
- 0:36:33 - Sorting Frequencies
- 0:37:39 - compare_freqkv_count()
- 0:38:16 - Generic Comparison in C
- 0:40:05 - Generic Comparison in Other Languages
- 0:40:45 - Generic Comparison in Rust
- 0:42:30 - Subtraction is All You Need
- 0:44:15 - Comparison is Basically Subtraction
- 0:44:39 - Descending Order
- 0:44:57 - Printing Top 10 Frequent Tokens
- 0:47:23 - Cleaning up logging
- 0:49:01 - Elapsed time
- 1:00:29 - Concatenating Files
- 1:02:07 - How Linear Search Works?
- 1:03:31 - The Hash Table
- 1:07:39 - Hacking Hash in Competitive programming
- 1:09:02 - Q: Have I done Competitive Programming before?
- 1:10:14 - What's the Competition in Competitive Programming?
- 1:11:11 - hash()
- 1:12:32 - naive_analysis()
- 1:15:05 - Iterating tokens
- 1:15:59 - Looking at the Hashes
- 1:17:33 - When Hashes Collide?
- 1:24:40 - Better Hash Function
- 1:26:55 - Open Addressing
- 1:28:44 - Probing Strategies
- 1:29:33 - Reflection
- 1:31:29 - Resolving Collisions
- 1:34:35 - Table Overflow
- 1:40:44 - Abstraction
- 1:46:41 - Adjusting Hash Table Parameters
- 1:47:34 - Sorting Final Results
- 1:48:59 - hash_analysis()
- 1:51:53 - Comparing execution time
- 1:54:05 - Sum is a bad Hash Function
- 1:55:25 - Testing Bigger Files
- 1:57:03 - djb2
- 2:03:18 - Further Abstraction
- 2:06:43 - Summary
- 2:07:08 - Potential Malicious File
- 2:07:53 - Just Do Dumb Things!
- 2:11:15 - Outro
References:
- https://twitch.tv/provod
- https://ocw.mit.edu/ans7870/6/6.006/s08/lecturenotes/files/t8.shakespeare.txt
- https://codeforces.com/
- http://www.cse.yorku.ca/~oz/hash.html
Support:
- BTC: bc1qj820dmeazpeq5pjn89mlh9lhws7ghs9v34x9v9
- Servers: https://zap-hosting.com/en/shop/donation/2038e94867b5e65cab2e72abf8ad956c/