Hashing In Data Structure

This is an PPT of Data Structure. It include the following topic "Hashing In Data Structure ".

1. DATA STRUCTURES PRESENTATION TOPIC: HASHING SUBMITED BY: YASH SOGANI MCA/25025/18

2. INTRODUCTION Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends on the efficiency of the hash function used.

3. FOR EXAMPLE:- Let a hash function H(x) maps the value at the index  x%10  in an Array. For example if the list of values is [11,12,13,14,15] it will be stored at positions {1,2,3,4,5} in the array or Hash table respectively.

4. IT’S REPRESENTATION L IST ={11,12,13,14,15} H(X)=[x % 10] 0 1 2 3 4 5 11 12 13 14 15 HASH TABLE

5. HASH TABLE A hash table is a data structure that stores elements and allows insertions, lookups, and deletions to be performed in O(1 ) time. A hash table is an alternative method for representing a dictionary.

6. Hash Table Operations – Search : Compute f(k) and see if a pair exists. – Insert : Compute f(k) and place it in that position. – Delete : Compute f(k) and delete the pair in that position. NOTE:- In ideal situation, hash table search, insert or delete takes O(1).

7. COLLISION When the hash value of a key maps to an already occupied bucket of the hash table, it is called as a Collision.

8. SEPARATE CHAINING To handle the collision, This technique creates a linked list to the slot for which collision occurs. The new key is then inserted in the linked list. These linked lists to the slots appear like chains. T hat is why, this technique is called as  separate chaining

9. FOR EXAMPLE:- FUNCTION:- K MOD 7

10. LINEAR PROBING The linear probing hash table is a fairly simple structure where data items are stored directly inside the hash element array. It gets its name by the way it handles the unique problems that exist when storing the data items in the table directly.

11. FOR EXAMPLE:- ADDING:-

12. SEARCHING:-

13. REFERENCES:- https://www.gatevidyalay.com/collision-resolution-techniques-separate-chaining / https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial / https://www.geeksforgeeks.org/hashing-data-structure/ http://www.cs.rmit.edu.au/online/blackboard/chapter/05/documents/contribute/chapter/05/linear-probing.html

14. THANK YOU