🍊 Hashing (Part 2) | Data Structures & Algorithms

#DataStructures #Algorithms #Hashing #ComputerScience This video provides an introduction to Hashing and Hash Tables, the fundamental concepts used to build efficient associative data structures. Presented by Hayden Smith, this lecture covers how hash tables work and the different strategies used to handle hash collisions. 🤔 What is Hashing? Unlike ordered containers like arrays, associative containers map keys (like strings) to values. Hashing is the technique that makes this possible. A hash function is used to take a key of any type and convert it into an integer. This integer is then used as an index to store the key's associated data in an array. This allows for very fast, direct access to data if you know its key. In the ideal case, hash table operations are O(1). 💥 The Problem: Hash Collisions A collision occurs when two different keys are hashed to the same array index. Since there are usually far more possible keys than there are slots in the array, collisions are inevitable and must be handled by a collision resolution strategy. ⚙️ Collision Resolution Strategies There are several ways to handle collisions. This lecture covers three main approaches: * Separate Chaining: In this method, each slot in the hash table array points to the head of a linked list. When a collision occurs, the new item is simply added to the list at that index. * Linear Probing: This is a type of "open addressing." If the target slot for an item is already occupied, the algorithm simply probes forward one slot at a time until it finds an empty one. *. Double Hashing: This is an improvement on linear probing. When a collision occurs, a second hash function is used to calculate a unique "step size" for probing through the array, which helps to reduce the clustering that can occur with linear probing. ⚖️ Performance The efficiency of a hash table depends heavily on the quality of its hash function and how well it handles collisions. Performance tends to degrade as the table becomes more full (i.e., as its "load factor" increases). View the full playlist: https://www.youtube.com/playlist?list=PLi2pCZz5m6GEftzPIxVH1ylwytux9WOGN