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
Rehashing
Rehashing is a concept primarily used in computer science and data structures, specifically in the context of hash tables or hash maps. Hash tables are data structures that allow efficient storage and retrieval of key-value pairs. They work by using a hash function to map keys to specific locations (buckets) in an array, where the associated values are stored.
Rehashing is the process of resizing a hash table and redistributing its elements when the current size of the table no longer efficiently accommodates the number of elements it contains. The primary goal of rehashing is to maintain a low load factor, which is the ratio of the number of stored elements to the total number of buckets in the hash table. A low load factor helps ensure that the hash table remains efficient in terms of time complexity for insertion, retrieval, and deletion operations.
Here's how rehashing typically works:
- Check the Load Factor: Periodically or after each insertion operation, the hash table checks its load factor. If the load factor exceeds a predefined threshold (often around 0.7 or 0.8), it indicates that the table is becoming crowded, and rehashing is needed.
- Create a New Hash Table: A new, larger hash table (usually with double the number of buckets) is created. The number of buckets is increased to reduce the load factor and make the table more efficient.
- Rehashing Process: Each element in the old hash table is rehashed, meaning their keys are mapped to new bucket positions in the larger table using the updated hash function. This process redistributes the key-value pairs among the new buckets.
- Transfer Elements: The key-value pairs are transferred from the old table to the new table based on their new hash values. This involves copying the data from the old table to the appropriate locations in the new table.
- Update References: Any references or pointers to the old hash table are updated to point to the new hash table.
- Dispose of the Old Table: Once all elements have been transferred, the old hash table can be deallocated or discarded.
Next Topic :Extendible hashing