5:53
L-6.1: What is hashing with example | Hashing in data structure
Gate Smashers
Overview
This video introduces hashing as an efficient data storage and retrieval technique, primarily used in computer science and competitive exams. It explains that hashing maps larger data values (search keys) to smaller values using a hash function, storing them in a hash table. The core idea is to achieve constant-time (O(1)) insertion, deletion, and search operations. The video covers key terms like search key and hash table, demonstrates hash function calculation using the 'K mod N' method with an example, and briefly touches upon other methods like mid-square and folding. It concludes by introducing the concept of collisions, which will be addressed in a subsequent video.
How was this?
Save this permanently with flashcards, quizzes, and AI chat
Chapters
- Hashing is a technique for storing and retrieving data in constant time (O(1)).
- It's also known as a mapping technique, transforming larger values into smaller ones.
- Hashing is important for competitive exams like GATE and NET, as well as college coursework.
- The video aims to explain the core concepts of hashing over a series of videos.
Understanding hashing is crucial for efficient data management and is a frequently tested topic in technical exams, making it a valuable skill for students and professionals.
- A 'search key' is the identifier used to store and retrieve data (e.g., roll number for student data, passport number for passport data).
- A 'hash table' is a data structure, similar to an array, that stores these search keys.
- Unlike a standard array, hash tables allow for O(1) insertion, deletion, and search using a hash function, avoiding linear scanning.
These components form the fundamental building blocks of the hashing system, defining what data is stored and where it is stored efficiently.
Using a student's 'roll number' as the search key to store and retrieve their academic record.
- Hash functions convert search keys into hash values (indices) for the hash table.
- Common hash functions include 'K mod N', the mid-square method, and the folding method.
- The 'K mod N' method calculates the remainder when the key (K) is divided by the table size (N), determining the index.
- Other methods like mid-square involve squaring the key and extracting middle digits, while folding involves summing parts of a large key.
Hash functions are the engine of hashing; understanding how they work is key to grasping how data is placed and found within the hash table.
Using the 'K mod 10' hash function for the key 24: 24 mod 10 results in a remainder of 4, so the key 24 is mapped to index 4 in the hash table.
- Insertion involves calculating the hash value and placing the key at that index in O(1) time.
- Searching for a key also requires calculating its hash value and directly accessing the corresponding index, achieving O(1) efficiency.
- Deletion follows the same O(1) process: calculate the hash, find the key at the index, and remove it.
- The hash table can act as an index, pointing to the actual data record stored elsewhere (e.g., on disk).
The primary benefit of hashing lies in its ability to perform fundamental data operations (insert, search, delete) in constant time, significantly outperforming linear search methods.
To search for the key 67, calculate 67 mod 10 = 7. Go directly to index 7 in the hash table to find the data.
- A collision occurs when two different keys map to the same index in the hash table.
- For example, if 52 maps to index 2 (52 mod 10 = 2), and then 62 also maps to index 2 (62 mod 10 = 2), a collision happens.
- Resolving collisions is a critical aspect of hashing and will be discussed in future videos.
Collisions are an inevitable challenge in hashing that can degrade performance if not handled properly, necessitating specific strategies for resolution.
When both key 52 and key 62 are hashed using 'K mod 10', they both map to index 2, creating a collision.
Key takeaways
- Hashing provides a way to store and retrieve data in constant time (O(1)) by mapping keys to specific table indices.
- The efficiency of hashing relies on the choice of a good hash function and a suitable hash table size.
- Search keys are crucial for identifying and locating data within a hash table.
- Hash tables are array-like structures designed for fast data operations.
- Understanding hash functions like 'K mod N' is fundamental to implementing hashing.
- While hashing offers speed, collisions are a common issue that requires specific resolution techniques.
- Hashing is a foundational concept in data structures with significant applications in computing and data management.
Key terms
HashingSearch KeyHash TableHash FunctionConstant Time (O(1))MappingK mod NCollisionMid-square MethodFolding Method
Test your understanding
- What is the primary advantage of using hashing for data storage and retrieval?
- How does a hash function transform a search key into a location within a hash table?
- Explain the 'K mod N' hash function and provide an example of its application.
- What is a collision in the context of hashing, and why is it an important concept to address?
- How does the concept of a 'search key' differ from the 'hash value' generated by a hash function?