In data structure, hashing is a technique of mapping large number of data items to smaller tables using a special function called the Hash function for faster access. Sometimes the data structure is so huge that it gets almost next to impossible to search all the index values through all the levels in order to access to final data block. This is where hashing comes right in. What it does is it calculates the location of a data record on the disk directly without using the index structure. The address of each record is determined using a hashing algorithm, which converts a primary key value into a record address. So, there are two categories of indexing available using hash functions – dynamic hashing and static hashing.
What is Static Hashing?
Static Hashing is a method of hashing in which a fixed number of buckets is allocated to a file to store the records. The number of buckets is pre-allocated so when a search key value is provided, the hash function always computes the same address. The page of a file can be viewed as a collection of buckets, with one primary page and additional overflow pages. With static hashing, the location mechanism is the hash function and no data structures are involved. Here, the index entries are randomized in a way that the number of index entries in each bucket is roughly the same. However, there are certain downsides to this scheme too. If the initial number of buckets is too small and file grows, the performance degrades because of bucket overflows. On the other hand, if it is too large, a lot of space is allocated for anticipated growth and a significant amount of space goes to waste.
What is Dynamic Hashing?
Dynamic Hashing, on the other hand, is a technique used to overcome the limitations in static hashing like bucket overflow. Unlike in static hashing, it allows the number of buckets to vary dynamically to accommodate the growth or shrinkage of database files. It allows the hash function to be modified on demand which is good for databases that grow and shrink in size. As rows are added and deleted, it changes the number of buckets accordingly in order to minimize overflow of buckets. It embeds the handling of overflow records into its primary address space dynamically in order to avoid handle management of overflow buckets. The two commonly used forms of dynamic hashing are linear hashing and extendible hashing. Extendible hashing is a popular technique that handles bucket overflow by splitting a bucket into two, distributing the records between old and new buckets. Linear hashing is yet another popular form of dynamic hashing that allows a hash file to grow or shrink dynamically by allocating new buckets.
Difference between Dynamic and Static Hashing
Technique
– Static Hashing is a method of hashing in which a fixed number of buckets is allocated to a file to store the records meaning it uses a hash function wherein the number of bucket addresses is fixed. Here, the index entries are randomized in a way that the number of index entries in each bucket is roughly the same. Dynamic Hashing, on the other hand, allows the number of buckets to vary dynamically in order to accommodate the growth or shrinkage of database files.
Performance
– If the initial number of buckets is too small and file grows, the performance degrades because of bucket overflows. On the other hand, if it is too large, a lot of space is allocated for anticipated growth and a significant amount of space goes to waste. Dynamic hashing, on the other hand, allows the hash function to be modified dynamically which is good for databases that grow and shrink in size. As rows are added and deleted, it changes the number of buckets accordingly in order to minimize overflow of buckets.
Implementation
– Static hashing uses a fixed hash function to partition the set of all possible search-key values into subsets, and then maps each subset to a bucket. Dynamic hashing, on the other hand, uses a second stage of mapping to determine the bucket associated with some search-key value. Extendible and linear hashing does this mapping very differently.
Dynamic vs. Static Hashing: Comparison Chart
Summary
The number of buckets is fixed in static hashing and records with different search-key values point to the same bucket, in which case a collision may occurs. If you need to locate a specific record in a bucket with multiple keys, you have to search the entire bucket sequentially. Sometimes, a bucket has more records than it can contain. So, in this case, some overflow handling techniques must be invoked. In that case, dynamic hashing is used, which uses a dynamically changing function that allows the number of allocated buckets to grow and shrink in size as rows are added and deleted. It explicitly handles the overflow of buckets by embedding the overflow records dynamically into its primary address.