Data Structures - Introduction
- Abstract data types
- Linear Data Structures
- Linked List Introduction
- Single Linked List
- Stacks using Array
- Stacks using linkedlist
- Queues using array
- Queues using linkedlist
- Stack Applications
- Infix to Postfic Converstion
- Postfix Evaluation
- Dictionaries
- Introduction to Dictionaries
- Linear list representation
- Skip list representation
- Hash Table
- Introduction Hash Table
- Hash functions
- Collision Resolution
- Separate chaining
- Open addressing
- Rehashing
- Extendible hashing
- Trees
- Introduction to Tree
- Binary trees Representation
- Binary tree traversals
- Binary Search Tree
- AVL Tree
- Red Black Tree
- Splay Tree
- B Tree
- B+ Tree
- Comparison of Trees
- Graphs
- Introduction to Graph
- Graph Representation
- Breadth-First Search
- Depth-First Search
- Sorting
- Quick Sort
- Merge Sort
- Heap Sort
- Pattern Matching
- Introduction to pattern Matching
- Brute force Pattern Matching
- Boyer–Moore Pattern Matching
- KMP Pattern Matching
- Tries
- Introduction to Tries
- Standard Trie
- Compressed tries
- Suffix Trie
Extendible hashing
Extendible hashing is a dynamic hashing technique used in computer science and database systems to efficiently organize and search data. It is designed to provide a compromise between static hashing (which requires a fixed number of buckets) and dynamic hashing (which may involve frequent rehashing). Extendible hashing dynamically adapts the number of buckets as data grows, minimizing the overhead associated with rehashing.
Here's how extendible hashing works:
- Initialization: Initially, there is a single directory that contains a fixed number of empty buckets. The directory acts as an index or directory of the available buckets.
- Hashing: When a new key-value pair needs to be inserted or searched for, a hash function is applied to the key to determine the bucket in which the pair should be stored or searched. The hash function generates an index into the directory.
- Directory Structure: The directory contains entries, each of which corresponds to a specific bucket. Initially, all entries point to the same bucket. These pointers are usually represented as binary strings or integers.
- Bucket Splitting: When a bucket becomes full (i.e., it reaches a predefined load factor), it is split into two new buckets. This splitting operation is done by adding a single bit to the binary string associated with the directory entry that pointed to the full bucket. This effectively doubles the number of buckets available for storing data.
- Directory Expansion: As buckets are split and new ones are created, the directory's structure grows dynamically. The directory entries are updated to reflect the new bucket locations as they are created.
- Search and Insertion: When searching for a key or inserting a new key-value pair, the hash function generates an index into the directory. The directory entry at that index is used to determine the appropriate bucket to search or insert into.
- Merging: Over time, if some buckets become empty due to deletions or if the directory becomes sparsely populated, extendible hashing allows for merging. This involves reducing the number of buckets by removing a bit from directory entries and merging adjacent buckets to maintain a balanced structure.
Extendible hashing offers several advantages:
- It adapts dynamically to the data distribution, avoiding the need for frequent rehashing.
- It provides a good balance between space usage and search efficiency.
- It offers predictable performance for search, insertion, and deletion operations.
Next Topic :Introduction to Tree