8.1 Hashing Techniques to Resolve Collision| Separate Chaining and Linear Probing | Data structure

Summary

This educational video delves into the concept of hashing, a technique for efficient data retrieval with constant time complexity. It introduces hashing methods, including division, folding, mid-square, and modulo multiplication, and discusses collision resolution strategies like chaining and open vs. closed addressing. The script provides a detailed example using division and closed addressing with a hash function (h(k) = 2k + 3) mod (M), illustrating how to handle collisions through chaining and linear probing. It also explains the process of linear probing for collision minimization and hints at upcoming coverage of quadratic probing and double hashing.

Takeaways

• 🔑 Hashing is a searching technique that provides constant time complexity, O(1), for data retrieval.
• 📚 Data structures like arrays, linked lists, and trees can be used for storing data in hashing.
• 🔍 Two common searching techniques are linear search, which has a time complexity of O(n), and binary search, with O(log n).
• 🚪 Collision occurs in hashing when two keys hash to the same index in the hash table.
• 🔄 There are various methods to calculate hash functions, including division, folding, mid-square, and modulo multiplication methods.
• 🔄‍🔧 Collision resolution techniques include open hashing (closed addressing) and closed hashing (open addressing).
• 🔗 Open hashing uses the chaining method, where a linked list is used to store multiple items at the same index.
• 🔍 Closed hashing involves linear probing, quadratic probing, and double hashing to find the next available slot in case of a collision.
• 🔄 Linear probing is a closed hashing technique that searches for the next free slot in a linear sequence after a collision.
• 📈 The total number of probes can be calculated to measure the efficiency of the hashing process.
• 🔢 The order of elements in the hash table after all insertions can be determined using the hashing and collision resolution methods described.

Q & A

What is hashing in the context of data structures?

Hashing is a searching technique used to store and retrieve data in constant time, typically using a hash table and a hash function to compute the address where data is stored.

Why is hashing preferred over other searching techniques like linear or binary search?

Hashing is preferred because it offers constant time complexity for search operations, regardless of the number of keys, unlike linear or binary search which have time complexities of O(n) and O(log n) respectively.

What are the common data structures used for storing data?

Common data structures used for storing data include arrays, linked lists, and trees.

What is a hash table?

A hash table is a data structure that implements an associative array, a structure that can map keys to values, using a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

What is a hash function and why is it important?

A hash function is a function used to map data of arbitrary size to fixed-size values, which are used as keys or addresses in a hash table. It is important because it determines the efficiency of the hash table by minimizing collisions.

What is a collision in hashing?

A collision occurs when two different keys hash to the same index in the hash table, which is a problem because only one value can be stored at a given index.

What are the different methods to resolve collisions in hashing?

Common methods to resolve collisions include chaining (using linked lists), open addressing (including linear probing, quadratic probing, and double hashing), and the modulo multiplication method.

What is chaining in the context of resolving hash collisions?

Chaining is a collision resolution technique where each cell of the hash table contains a linked list of all the items that hash to the same index.

What is linear probing and how does it work?

Linear probing is an open addressing technique used to resolve collisions. When a collision occurs, the algorithm searches for the next available slot in the hash table by moving linearly through the table.

What is the difference between open addressing and closed addressing in hashing?

Open addressing is a method of collision resolution where an alternative address is found within the hash table itself. Closed addressing, on the other hand, refers to the use of a hash table and a hash function without explicitly stating the collision resolution technique, often implying chaining.

How is the division method used to calculate a hash function in hashing?

The division method involves taking the key value, multiplying it by a constant (often 2), adding a constant, and then taking the modulus of the hash table size to determine the index in the hash table.

Can you provide an example of how to store keys in a hash table using the division method and linear probing?

Sure. Given a hash function h(k) = 2k + 3 mod 10 for a hash table of size 10, to store the key value 3, you would calculate h(3) = (2*3 + 3) mod 10 = 9, so the key 3 would be stored at index 9. If there's a collision, linear probing would be used to find the next free slot.