Hash Table Data Structure - Interactive Learning
Master Hash Table - DSA Learning Platform 🗂️ Master Hash Table Key-Value Storage O(1) Average Access Learn hash table operations with interactive animations and collision handling 📖 Understanding Hash Table Data Structure Introduction Hash Function Collision Handling Operations Applications What is a Hash Table? A Hash Table (also known as Hash Map) is a data structure that implements an associative array, mapping keys to values. It uses a hash function to compute an index into an array of buckets, from which the desired value can be found. The main advantage of hash tables is their O(1) average time complexity for insert, search, and delete operations, making them incredibly efficient for large datasets. Basic Hash Function Concept index = hash(key) % table_size When two keys hash to the same index, a collision occurs. Hash tables use various techniques to handle collisions, such as chaining (linked lists) or open addressing. 🔑 Key Characteristics Key-value pair storage O(1) average time for operations Uses hash function to compute index Handles collisions efficiently Dynamic resizing possible Unordered data structure 📊 Space Complexity Overall: O(n) where n is number of entries Load Factor: n / table_size How Hash Functions Work A hash function takes a key and returns an integer (hash code), which is then mapped to an index in the hash table using modulo operation. For Integer Keys index = key % table_size For String Keys (Sum of ASCII) hash = Σ(char_ascii) % table_size Properties of Good Hash Functions Deterministic: Same key always produces same hash Uniform Distribution: Keys spread evenly across buckets Efficient: Fast to compute Minimize Collisions: Different keys rarely get same hash 📍 Hash Function Example Key: "apple" ASCII Sum: 97+112+112+108+101 = 530 Table Size: 10 Index: 530 % 10 = 0 "apple" → Bucket[0] Collision Handling Techniques A collision occurs when two different keys hash to the same index. There are two main approaches to handle collisions: 1. Chaining (Separate Chaining) Each bucket contains a linked list of entries. When collision occurs, new entry is added to the list. Simple to implement Never runs out of space Performance degrades with many collisions 2. Open Addressing Find another empty slot using probing techniques. Linear Probing: Check next slot sequentially Quadratic Probing: Check slots at quadratic intervals Double Hashing: Use second hash function 📍 Chaining Example (This Demo) [0] "apple":5 → "apricot":8 → NULL [1] empty [2] "banana":3 → NULL [3] empty Hash Table Operations 📥 Insert (Put) Compute hash: index = hash(key) % size Go to bucket[index] If key exists, update value Otherwise, add new entry to bucket 🔍 Search (Get) Compute hash: index = hash(key) % size Go to bucket[index] Search through chain for matching key Return value if found, null otherwise 🗑️ Delete (Remove) Compute hash: index = hash(key) % size Go to bucket[index] Find and remove entry with matching key Relink chain if necessary ⏱️ Ti...
Subject: Data Structures with Animation | Chapter: Hash Table Data Structure