Overview
Week 09: Searching; introduction to hash tables
This week, we鈥檒l see how to perform searches on linear structures, and we鈥檒l begin our study of hashing and hash tables.
Searching linear structures
- Linear search
- Binary search
- Interpolation search
Introduction to hash tables
- Hash tables
- Horner hash
- Hash collisions
- Separate chaining
This video is re-used from a previous semester, but I think it covers everything well. Just ignore the last bit about a discussion board).
Learning Objectives
By the end of this module, you will be able to:
- Understand and implement binary search on a vector or array
- Understand how interpolation sort works, and use cases for interpolation sort
- Understand an implement a simple hash table
- Explain why hash collisions are a problem and give one solution for handling such collisions鈥攃haining.
To achieve this module鈥檚 objectives, please watch the introductory video (above), and complete the following:
Read: Essential Algorithms, Chapters 7 (searching) and 8 (hash tables)
Read / view the following content and complete any comprehension checks:
- Searching
- Introduction to hashing
- Collisions
- Separate chaining
Copyright 漏 2023鈥�2025 Clayton Cafiero
No generative AI was used in producing this material. This was written the old-fashioned way.