Hashing (Concept & Techniques)- Data Structure

This presentation offers an in-depth exploration of advanced hashing techniques, designed specifically for students with a foundational understanding of data structures and algorithms

1. Hashing (Concept & Techniques)

2. What is Hashing? Hashing is a technique that maps data of arbitrary size → fixed-size value (index) using a hash function. Enables fast insertion, search, deletion .

3. Hashing Techniques A. Open Addressing (In-Table Collisions) Linear Probing: h'(key, i ) = (h(key) + i ) % table_size Quadratic Probing: h'(key, i ) = (h(key) + i^2) % table_size Double Hashing: h'(key, i ) = (h1(key) + i *h2(key)) % table_size B. Chaining Each index holds a linked list of colliding keys. C. Perfect Hashing Maps n keys → n slots without collisions. Ideal for static datasets .

4. Hash Table Array-like structure using hash function to store keys. Features: Fast operations: O(1) average time Requires collision handling Pseudo Code (Insertion using Chaining):

5. Hash Function Converts key → index Properties: Fast Uniform Deterministic Common Types: Division: h(key) = key % table_size Multiplication : h(key) = floor( table_size * (key * A % 1)) String Hashing: ASCII sum, polynomial rolling hash

6. Advantages of Hashing Techniques Fast Access: O(1) average for search, insert, delete Efficient Memory: Optimized storage if table size chosen well Flexible: Can store different types of keys Widely Used: Databases, caching, symbol tables Open Addressing Advantages: Simple structure, no extra memory for linked lists Cache-friendly Easy to implement Perfect Hashing Advantages: No collisions → O(1) search guaranteed Ideal for static datasets

7. Disadvantages of Hashing Techniques Collisions require handling (chaining or probing) Poor hash function → clustering & uneven distribution Fixed-size table → overflow or need for resizing Cannot maintain sorted order of elements Open addressing: performance degrades with high load factor

8. Applications of Hashing Database Indexing – fast retrieval of records Symbol Tables – in compilers and interpreters Caching – storing frequently accessed data Password Storage – hashing + salting Cryptography – MD5, SHA algorithms Sets & Maps – key-value pairs in programming languages

9. AVL Tree Self-balancing Binary Search Tree (BST) Balance Factor (BF) = height(left) - height(right) Rotations: LL, RR, LR, RL Pseudo Code (Insertion):

10. Red- Black Tree Self-balancing BST using colors (Red/Black) Properties: Root is black Red nodes cannot have red children Every path from root → leaf has same black height Node Structure:

11. Rotations Left Right

12. BST Insertion Red-Black Tree Insertion

13. Fixing Violations After Insertion

14. Binomial Heap A Binomial Heap is a collection of Binomial Trees that satisfies the Min-Heap (or Max-Heap) property. Each tree in the heap follows heap-order property (parent ≤ children for min-heap). Efficient for mergeable priority queues . Properties: A Binomial Tree of order k has 2^k nodes . Height of tree = k Number of nodes at depth i = C(k, i ) (binomial coefficient)

15. Basic Operations Merge Two Heaps Insert Key Find Minimum Delete Minimum

16. Fibonacci Heap A Fibonacci Heap is a collection of heap-ordered trees with a relaxed structure , allowing very fast amortized operations. Optimized for algorithms that require lots of decrease-key operations , like Dijkstra’s algorithm . Properties: Each tree satisfies min-heap property (parent ≤ children). Nodes are linked circularly in a root list Maintains pointer to the minimum node for O(1) access. Lazy consolidation — trees are merged only when necessary.

17. Basic Operations Insert Node Find Minimum Extract Minimum Decrease Key

18. Array, Structure and Binary List Array : Contiguous elements, random access O(1) Structure : Groups multiple data types Binary List : Efficient 0/1 storage used in sets, bitmap indexing