8 Oct - DS- Hashing
Duration: 1 hr 25 min
This video lesson is available to enrolled students.
AI Summary
An AI-generated summary of this video lecture.
This lecture provides a comprehensive introduction to hashing, a technique used to optimize search operations in data structures. The instructor begins by comparing the search time complexities of various data structures, highlighting that hashing offers constant time complexity O(1) in the average case. Key concepts covered include hash functions, hash tables, collisions, and collision resolution techniques such as linear probing and chaining. The lecture features multiple solved problems from GATE exams, demonstrating the application of these concepts in practical scenarios. The instructor explains the mechanics of open addressing, closed hashing, and the characteristics of a good hash function, concluding with a discussion on the advantages and disadvantages of different collision resolution methods.
Chapters
0:00 – 2:00 00:00-02:00
The lecture begins with an introduction to hashing, emphasizing that while data structures aim to store data efficiently, the most frequent operation is search. The slide lists search time complexities for various structures: Unsorted Array O(n), Sorted Array O(log n), Linked List O(n), Binary Tree O(n), Binary Search Tree O(n) in worst case, and AVL Tree O(log n). The instructor highlights that hashing optimizes search operations by providing constant time complexity O(1) for lookups in the average case, making it a powerful tool for managing and accessing data. This sets the stage for understanding why hashing is necessary despite the existence of other efficient data structures.
2:00 – 5:00 02:00-05:00
The concept of hashing is defined as a technique where search time is independent of the number of elements. The main idea is to use a key value, such as phone numbers or roll numbers, to directly find the address in memory. A hash function converts a large key into a smaller number that serves as an index in the hash table. The transformation is represented as H: K -> L, where K is the set of keys and L is the set of memory locations. An example is shown using a date (10/03/1989) where the sum of digits is calculated to find a hash value, demonstrating how a large key is mapped to a smaller index.
5:00 – 10:00 05:00-10:00
Collision is defined as the situation where two different sets of keys K1 and K2 will map to the same hash address. The technique to resolve this is called collision resolution. The instructor notes that irrespective of how good a hash function is, collisions are bound to occur. Characteristics of a good hash function are listed: it must be easy to compute and understand, efficiently computable (take less time), should uniformly distribute keys to avoid clustering, and must have a low collision rate. These characteristics are crucial for maintaining the performance of a hash table.
10:00 – 15:00 10:00-15:00
Linear probing is explained as a collision resolution technique where the hash table is searched starting from the position given by the hash function until a matching key or an empty slot is found. The position for a key k is calculated using the hash function h(k, i) = (h'(k) + i) mod m, where h'(k) is the primary hash function, i is the probe number, and m is the size of the hash table. Insertion involves probing until an empty slot is found. Search continues until the key is found or an empty slot is reached. Deletion is noted as interesting because simply deleting a key can cause search to fail, so slots of deleted keys are marked specially as 'deleted'.
15:00 – 20:00 15:00-20:00
A problem is solved involving a hash table with 10 buckets using linear probing and the hash function key % 10. The values 43, 123, 142 are inserted. The instructor calculates the hash for each: 43 % 10 = 3, 123 % 10 = 3, 142 % 10 = 2. Since 43 and 123 both hash to 3, a collision occurs. Linear probing is used to resolve it, placing 123 in the next available slot, which is index 4. The value 142 is placed at index 2. The instructor draws the table to visualize the placement and the probing sequence.
20:00 – 25:00 20:00-25:00
Another problem is presented: Keys 12, 18, 13, 2, 3, 23, 5, 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. The instructor works through the insertion process step-by-step. For instance, 12 hashes to 2, 18 to 8, 13 to 3. When 2 is inserted, it hashes to 2 (collision), so it probes to 3 (collision), then 4. Similarly, 3 hashes to 3 (collision), probes to 4 (collision), then 5. The final table state is compared with the given options to find the correct resultant hash table.
25:00 – 30:00 25:00-30:00
Open addressing, also known as closed hashing, is defined as a method where all elements are stored in the table itself. Collision is resolved by probing or searching through alternate locations in the hash table in a particular sequence. The instructor mentions that when searching for an element, one examines table slots one by one until the desired element is found or it is clear that the element is not in the table. It is noted that the size of the table must be greater than or equal to the total number of keys. Three types of open addressing are listed: linear probing, quadratic probing, and double hashing.
30:00 – 35:00 30:00-35:00
A problem is solved: Consider a hash table of size 11 that uses open addressing with linear probing and hash function h(k) = k mod 11. A sequence of records with keys 11, 4, 71, 13, 14 is inserted into an initially empty hash table. The instructor calculates the index for each key: 11 % 11 = 0, 4 % 11 = 4, 71 % 11 = 5, 13 % 11 = 2, 14 % 11 = 3. Since there are no collisions in this specific sequence, the last record (14) is inserted at index 3. The instructor draws the table to show the final positions.
35:00 – 40:00 35:00-40:00
A problem is solved: A hash table of length 10 uses open addressing with hash function h(k) = k mod 10 and linear probing. After inserting 6 values, the table is shown. The task is to find a possible order in which the key values could have been inserted. The instructor analyzes the table state, noting that 42 is at index 2, 23 at 3, 34 at 4, 52 at 5, 46 at 6, 33 at 7. By checking the options, the instructor verifies which sequence of insertions would result in this specific table configuration, considering collisions and probing.
40:00 – 45:00 40:00-45:00
A problem is solved: Consider a hash table of size seven, with starting index zero, and a hash function h(k) = k mod 7. Assuming the hash table is initially empty, the sequence 1, 3, 8, 10 is inserted using closed hashing. The instructor calculates the indices: 1 % 7 = 1, 3 % 7 = 3, 8 % 7 = 1 (collision, probe to 2), 10 % 7 = 3 (collision, probe to 4). The final table contents are determined as 1 at index 1, 3 at index 3, 8 at index 2, 10 at index 4. The options are compared to find the correct one.
45:00 – 50:00 45:00-50:00
A probability question is discussed: Consider a hash function that distributes keys uniformly. The hash table size is 20. The question asks after hashing of how many keys will the probability that any new key collides with an existing one exceed 0.5. The instructor explains that the probability of collision is the number of occupied slots divided by the total slots. So, n/20 > 0.5 implies n > 10. However, the instructor might be considering the birthday paradox or a different interpretation. The instructor calculates probabilities like 1/20, 2/20... until it exceeds 0.5, leading to the answer 10.
50:00 – 55:00 50:00-55:00
A problem is solved: Given a hash table T with 25 slots that stores 2000 elements, the load factor for T is calculated. The load factor is defined as the number of elements divided by the number of slots. So, load factor = 2000 / 25 = 80. The instructor emphasizes that a load factor greater than 1 is possible in open addressing but indicates a high probability of collisions. The options are checked, and 80 is identified as the correct answer.
55:00 – 60:00 55:00-60:00
A problem is solved: Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The instructor calculates the chain length for each slot. For example, 5 % 9 = 5, 28 % 9 = 1, 19 % 9 = 1, 15 % 9 = 6, 20 % 9 = 2, 33 % 9 = 6, 12 % 9 = 3, 17 % 9 = 8, 10 % 9 = 1. The maximum, minimum, and average chain lengths are calculated. The maximum chain length is 3 (at index 1), minimum is 0 (at index 0, 4, 7), and average is 1.
60:00 – 65:00 60:00-65:00
The advantages and disadvantages of linear probing are discussed. Advantages include being fast and simple, easy to implement, having good locality of reference, and performing well on standard hardware due to sequential memory access. Disadvantages include the primary clustering issue where collisions can lead to long probe sequences, and sensitivity to the hash function, requiring a high-quality hash function to avoid performance degradation.
65:00 – 70:00 65:00-70:00
The advantages and disadvantages of chaining are discussed. The idea is to make each cell of the hash table point to a linked list of records that have the same hash function value. The advantage is that chaining is simple. The disadvantage is that it requires additional memory outside the table for the linked list nodes. A diagram shows how multiple keys hash to the same slot and are linked together.
70:00 – 75:00 70:00-75:00
The instructor reviews the Gate 2009 problem regarding linear probing. The keys 12, 18, 13, 2, 3, 23, 5, 15 are inserted into a table of length 10. The instructor re-verifies the insertion order and the final table state, ensuring that the student understands how collisions are resolved and how the table is populated. The correct option is confirmed.
75:00 – 80:00 75:00-80:00
The instructor reviews the Gate 2014 problem regarding chaining. The hash table has 9 slots, h(k) = k mod 9, and keys are inserted in a specific order. The instructor re-verifies the chain lengths for each slot, calculating the maximum, minimum, and average chain lengths. The correct option is confirmed, reinforcing the concept of chaining and load factor.
80:00 – 85:00 80:00-85:00
The lecture concludes with a final summary of the key concepts covered. The instructor reiterates the importance of hashing for efficient search operations, the trade-offs between different collision resolution techniques like linear probing and chaining, and the characteristics of a good hash function. The instructor encourages students to practice more problems to solidify their understanding.
85:00 – 85:20 85:00-85:20
The video ends. The instructor signs off.
The lecture provides a thorough overview of hashing, starting with the motivation for using hash tables over other data structures due to their constant time search complexity. It defines hash functions and hash tables, explaining how keys are mapped to indices. The concept of collision is introduced, followed by a detailed discussion of collision resolution techniques, specifically linear probing and chaining. The instructor uses multiple GATE exam problems to demonstrate the practical application of these concepts, walking through step-by-step calculations for insertion, search, and deletion. The advantages and disadvantages of each technique are compared, highlighting issues like primary clustering in linear probing and memory overhead in chaining. The lecture concludes by reinforcing the importance of choosing a good hash function and understanding the load factor.