Hash tables: Samuel's tutorial скачать в хорошем качестве

Hash tables: Samuel's tutorial

Samuel's guide to hash tables (search by index, hash functions, chaining and open addressing). Timestamps: 00:00 - Introduction to hash tables 03:01 - Idea: search by index 07:35 - Hash functions 14:19 - Chaining 17:15 - Open addressing 23:18 - Links to further resources Correction: 16:01 - This is incorrect (a naive linked list will not enable binary search) Detailed description: This video provides a brief guide to hash tables. We first explain their key benefits (fast search, insertion and deletion), their introduction by H. P. Luhn in 1953, and their usefulness for implementing Sets and Maps. Next, we convey the key idea behind hash tables: search by index and how this enables fast operations. Hash functions of various kinds are described. These include static hash functions (like the division method and multiplication methods), random hash functions (and in particular universal hash function families) and cryptographic hash functions. We talk about applications of hash functions (which span hash tables, string search, passwords, signatures, digests and proof of work algorithms like the one used to secure the Bitcoin blockchain) and the use of the SipHash hash function by Python. We talk about chaining, a simple way to handle collisions, and how it performs in both worst-case and average-case scenarios. Finally, we discuss open addressing schemes like linear probing and its generalisation to double hashing. The number of probes required for unsuccessful search is described. We briefly mention re-ordering schemes (Brent's method and Robin Hood hashing) and close by outlining how CPython dictionaries handle collisions. Topics: #datastructures #hashtables #coding Slides (pdf): https://samuelalbanie.com/files/diges... References for papers mentioned in the video can be found at http://samuelalbanie.com/digests/2022... Recommended further reading: Some resources I would enthusiastically recommend are Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT press. https://mitpress.mit.edu/978026204630... Knuth, D. E. "The Art of Computer Programming, volume 3: Sorting and Searching", (Second Edition) 1998 https://www-cs-faculty.stanford.edu/~... Erickson, J. "Algorithms", http://jeffe.cs.illinois.edu/teaching... (the core textbook is made available under a creative commons license) For related content: Twitter:   / samuelalbanie   Research lab: https://caml-lab.com/ personal webpage: https://samuelalbanie.com/ YouTube:    / @samuelalbanie1   (Optional) if you'd like to support the channel: https://www.buymeacoffee.com/samuelal...   / samuel_albanie