GATE CSEIT\/Database\/ Hashing introduction with hashing function and hashing table<\/p>\n
[fvplayer id=”293″]<\/p>\n
Hashing is a technique used in databases, data structures, and indexing<\/strong> to store and retrieve data efficiently. It uses a hash function<\/strong> to map keys to a specific location in a hash table<\/strong>.<\/p>\n Key Benefits of Hashing:<\/strong><\/p>\n A hash function<\/strong> is a mathematical function that converts a key into a unique index (hash value).<\/p>\n Formula for Hash Function:<\/strong><\/p>\n h(K)=Kmod\u2009\u2009Mh(K) = K \\mod M<\/span>h<\/span>(<\/span>K<\/span>)<\/span>=<\/span><\/span>K<\/span><\/span>mod<\/span><\/span>M<\/span><\/span><\/span><\/span><\/span><\/p>\n where:<\/p>\n If we insert the key 25<\/strong> into a hash table of size 10<\/strong>, using h(25)=25mod\u2009\u200910=5h(25) = 25 \\mod 10 = 5<\/span>h<\/span>(<\/span>25<\/span>)<\/span>=<\/span><\/span>25<\/span><\/span>mod<\/span><\/span>10<\/span>=<\/span><\/span>5<\/span><\/span><\/span><\/span><\/span><\/p>\n So, 25 is stored at index 5<\/strong> in the hash table.<\/p>\n Good Hash Functions Should:<\/strong> A hash table<\/strong> is a data structure that stores key-value pairs<\/strong> and uses hashing for fast lookups.<\/p>\n Operations on a Hash Table:<\/strong> \u00a0If we need to search for key 25<\/strong>, we compute 1. Division Method (Modulo Method)<\/strong><\/p>\n h(K)=Kmod\u2009\u2009Mh(K) = K \\mod M<\/span>h<\/span>(<\/span>K<\/span>)<\/span>=<\/span><\/span>K<\/span><\/span>mod<\/span><\/span>M<\/span><\/span><\/span><\/span><\/span><\/p>\n \u00a0Simple and commonly used. 2. Multiplication Method<\/strong><\/p>\n h(K)=\u230aM(K\u00d7Amod\u2009\u20091)\u230bh(K) = \\lfloor M (K \\times A \\mod 1) \\rfloor<\/span>h<\/span>(<\/span>K<\/span>)<\/span>=<\/span><\/span>\u230a<\/span>M<\/span>(<\/span>K<\/span>\u00d7<\/span><\/span>A<\/span><\/span>mod<\/span><\/span>1<\/span>)\u230b<\/span><\/span><\/span><\/span><\/span><\/p>\n where 3. Folding Method<\/strong> 4. Mid-Square Method<\/strong> 5. Universal Hashing<\/strong> What is a Collision?<\/strong> Example: Collision Handling Techniques:<\/strong> Question:<\/strong> A hash function is defined as Solution:<\/strong> Final Hash Table (Using Linear Probing):<\/strong><\/p>\n Hashing<\/strong> is a technique for efficient data storage and retrieval<\/strong>. \u00a0Need more GATE practice questions or coding examples?<\/strong> Let me know!<\/p>\n Here’s a focused introduction to Hashing<\/strong> for GATE CSE\/IT \u2013 Databases<\/strong>, covering:<\/p>\n\n
\u00a0Hashing Function<\/strong><\/h3>\n
\n
Example:<\/strong><\/h3>\n
h(K) = K mod 10<\/code>:<\/p>\n
\u00a0Be fast to compute.
\u00a0Distribute keys uniformly<\/strong> across the table.
\u00a0Minimize collisions.<\/p>\n\u00a0Hash Table<\/strong><\/h3>\n
Insertion<\/strong> \u2013 Store data at the index calculated by the hash function.
Search<\/strong> \u2013 Retrieve data using the hash function.
Deletion<\/strong> \u2013 Remove data from the hash table.<\/p>\nExample of a Hash Table (Size = 10):<\/strong><\/h3>\n
\n\n
\n \nIndex<\/th>\n Key Stored<\/th>\n<\/tr>\n<\/thead>\n \n 0<\/td>\n –<\/td>\n<\/tr>\n \n 1<\/td>\n –<\/td>\n<\/tr>\n \n 2<\/td>\n 32<\/td>\n<\/tr>\n \n 3<\/td>\n 23<\/td>\n<\/tr>\n \n 4<\/td>\n 44<\/td>\n<\/tr>\n \n 5<\/td>\n 25<\/td>\n<\/tr>\n \n 6<\/td>\n –<\/td>\n<\/tr>\n \n 7<\/td>\n –<\/td>\n<\/tr>\n \n 8<\/td>\n –<\/td>\n<\/tr>\n \n 9<\/td>\n 39<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n h(25) = 5<\/code>, and directly access index 5<\/strong> \u2192 O(1) time complexity<\/strong>.<\/p>\n\u00a0Types of Hash Functions<\/strong><\/h3>\n
\u00a0M should be a prime number<\/strong> to reduce collisions.<\/p>\nA<\/code> is a fractional constant (e.g., 0.618<\/strong>).
\u00a0Works well with power-of-2 table sizes.<\/p>\n
\u00a0Splits key into parts, applies arithmetic operations, and combines the results.<\/p>\n
\u00a0Squares the key and extracts middle digits as the hash value.<\/p>\n
\u00a0Uses randomly chosen hash functions<\/strong> to minimize collisions.<\/p>\n\u00a0Collision in Hashing<\/strong><\/h3>\n
A collision<\/strong> occurs when two different keys<\/strong> hash to the same index<\/strong> in the hash table.<\/p>\n
For M = 10<\/code>, if keys 25<\/strong> and 35<\/strong> both hash to index 5<\/strong> (h(25) = 5<\/code>, h(35) = 5<\/code>), we have a collision<\/strong>.<\/p>\n
Open Addressing<\/strong> (Linear Probing, Quadratic Probing, Double Hashing)
Separate Chaining<\/strong> (Using Linked Lists)<\/p>\n\u00a0Example GATE Question (Hashing Function & Hash Table)<\/strong><\/h3>\n
h(K) = K mod 7<\/code>. Given keys 50, 700, 76, 85, 92, 73<\/strong>, insert them into a hash table of size 7<\/strong>.<\/p>\n
\u00a0Compute the hash values.<\/p>\n\n\n
\n Key<\/th>\n Hash Value ( h(K) = K mod 7<\/code>)<\/th>\nPlacement<\/th>\n<\/tr>\n<\/thead>\n \n\n 50<\/td>\n 50 mod 7 = 1<\/code><\/td>\nSlot 1<\/strong><\/td>\n<\/tr>\n \n 700<\/td>\n 700 mod 7 = 0<\/code><\/td>\nSlot 0<\/strong><\/td>\n<\/tr>\n \n 76<\/td>\n 76 mod 7 = 6<\/code><\/td>\nSlot 6<\/strong><\/td>\n<\/tr>\n \n 85<\/td>\n 85 mod 7 = 1<\/code><\/td>\nCollision<\/strong> (Use Linear Probing) \u2192 Slot 2<\/strong><\/td>\n<\/tr>\n \n 92<\/td>\n 92 mod 7 = 1<\/code><\/td>\nCollision<\/strong> (Use Linear Probing) \u2192 Slot 3<\/strong><\/td>\n<\/tr>\n \n 73<\/td>\n 73 mod 7 = 3<\/code><\/td>\nSlot 4<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n Index: 0 1 2 3 4 5 6 <\/span>
\nKeys: 700 50 85 92 73 - 76 <\/span>
\n<\/code><\/div>\n<\/div>\n\u00a0Summary<\/strong><\/h3>\n
Hash functions<\/strong> map keys to hash values.
Collisions<\/strong> occur when multiple keys map to the same index<\/strong>.
Collision handling techniques<\/strong> (Open Addressing & Separate Chaining) prevent data loss.
Common GATE questions<\/strong> test hashing functions, collision resolution, and hash table operations.<\/p>\nGATE CSEIT\/Database\/ Hashing introduction with hashing function and hashing table<\/a><\/h3>\n
Introduction to Hash Table and Hash Function<\/a><\/h3>\n
Hashing in Data Structure<\/a><\/h3>\n
\n