Introduction to Hashing

Data structure often contains a lot of data that is difficult to search through. Hashing is an effective solution that can be used to map these large datasets to much smaller tables by utilizing a unique Hash function. This helps to quickly access the data and reduces the effort that would otherwise be required to search through every index value and level to get to the required data block.

Hashing is a computational technique in which a special set of functions transform information of varying length into a shortened fixed-length output, commonly known as a “Hash Code”, “Key”, or simply “Hash”. The data that the hashing process is applied to is usually referred to as a “Data Bucket”.

Hashing is often used for a variety of purposes, such as verifying passwords, linking filenames with their file paths in OS, graphic processing, and playing board games like Chess and tic-tac-toe.

In this article, you will learn the difference between two significant hashing methods – static hashing vs dynamic hashing.

What is Static Hashing?

This method of hashing allows individuals to access a specific set of data. This means the content in the directory is not fluctuating, it’s “Static” or constant. Through this hashing technique, the number of data buckets in memory stays the same.

Static Hashing Operations

• Insertion – When a data point is added to a static hashing system, the hash function (h) is used to work out the bucket address “h(K)” for the search key (k) in which the record is stored.
• Search − When trying to access a record, the same hash function can be employed to get the location of the bucket which contains the data.
• Delete − Search the associated address of a certain record and delete either that single record or a group of records stored in the memory that corresponds to the same address.
• Update – It is feasible to update a record once it has been identified through the use of a hash function.

Advantages of Static Hashing

• Provides the best possible results when dealing with databases of a limited size.
• It is possible to use the value of the Primary Key as a Hash Key.

Disadvantages of Static Hashing

• It is not capable of operating effectively with scalable databases and large sized databases.
• When the amount of data surpasses the available memory, a bucket overflow problem will arise.

This significant issue of bucket overflowing can be addressed in two ways:

Overflow chaining – When all the buckets are at full, a new bucket is generated to store the same hash result.

Linear Probing – When a hash function creates an address that already contains data, the next free bucket is assigned to the said data.

What is Dynamic Hashing?

This type of hashing allows users to find information in a changing data set. That is, data can be added or removed as needed, thus making it a ‘dynamic’ hashing approach. The size of the data buckets increases/decreases as per the number of records contained in them. A problem with static hashing is the potential bucket overflow. Dynamic hashing provides a way to avoid this issue, and is also known as the Extendible hashing method.

Dynamic Hashing Operations

• Insertion – It is possible to figure out the address of the bucket. If the bucket is already full, extra buckets can be added. In addition, extra bits can be included in the hash value and the hash function can be calculated again. If the buckets are not full, data can be added to them.
• Querying – Determine the depth of the hash index and applying the data from it to compute the address of the bucket.
• Delete − Executes a query to find the necessary data to delete.
• Update – It performs a query to update the data.

Advantages of Dynamic Hashing

• It is effective with scalable data.
• It has the capability to manage large amount of memory where the size of the data is consistently altering.
• It is capable to overcome the bucket flow issue effectively.

Disadvantages of Dynamic Hashing

• The position of the data in the memory varies depending on the bucket size. Therefore, if there is a huge increment in the data, keeping the bucket address list up-to-date can be a problem.

Static Hashing vs Dynamic Hashing

Below table summarizes the key points of differences between the two techniques of hashing:

Download the comparison table: Static vs Dynamic Hashing

Conclusion

When it comes to hashing, there are variations in the way it can be applied depending on whether the data set requires a fixed-length or a variable-length bucket. When picking a hashing technique, one must take into account the size of the data to be processed as well as the speed of the application.

Continue Reading:

MD5 vs CRC – Detailed Comparison

What is Cryptography? Detailed Explanation