Hashing in Data Structure: Usage, Types, and How It Works in DSA

Ever wondered how search engines dig up what you need in the blink of an eye or how data stays secure in the ever-expanding and vulnerable digital landscape? The secret lies in Hashing, a powerful trick in Data Science. It has emerged as a game-changer in Data Management and Computer Science as it organises and retrieves data at lightning speed. But what exactly are the mechanics behind Hashing in Data Structure?

This blog dives deep into this topic, exploring exciting use cases, examples, types of Hashing in Data Structure, collision resolution methods and more. So, read on and learn how this groundbreaking technique powers efficient algorithms for handling everything from superfast search operations to much-needed data security!

Table of Contents

1) What is Hashing in Data Structure?

2) What is a Hash Key?

3) How Hashing Works in Data Structures?

4) Types of Hash Functions

5) Use cases of Hashing In DSA

6) Collision Resolution Techniques in Hashing

7) Conclusion

What is Hashing in Data Structure?

In Data Structure, Hashing is a fundamental concept that's the backbone of efficient data retrieval and storage mechanisms. It involves converting a large and complex key into smaller, fixed-size value, subsequently used as an index to store the data in a hash table.

Since it enables direct access to the data instead of going through each element sequentially, this process substantially reduces the time it takes to find an item. Hashing enables data analysts to handle large datasets easily and dramatically improves applications' performance.

What is a Hash Key?

In the context of Hashing, a hash key (hash value or hash code) is a fixed-size alphanumeric or numeric representation generated by a Hashing algorithm. It's derived from the input data, like a text string or file, through Hashing.

It involves applying a mathematical function to the input data, which creates a unique hash key typically of fixed length, regardless of the input size. The resulting hash key serves as a digital fingerprint of the original data and can be commonly used for data integrity checks. To further enhance your understanding, reviewing Data Structure Interview Questions can help you grasp key hashing concepts and their practical applications.

How Hashing Works in Data Structures?

The backbone of Hashing is the process of mapping data to a fixed-size array. This mapping is achieved through a hash function, a mathematical algorithm which transforms input data into a numerical value corresponding to an array index. The result is a streamlined approach to storing and retrieving data, which contributes to improved efficiency in diverse applications.

Types of Hashing in Data Structure

The two types of Hashing widely used in the Data Structure are closed-address Hashing and open-address Hashing:

a) Closed-address Hashing: Closed-address Hashing (separate chaining) is a Hashing technique in which each slot in the table stores a linked list of elements with the same hash value. In case of a collision, multiple elements are mapped to the same hash value and stored in the same slot through separate chaining.

b) Open-address Hashing: Open-address Hashing, also called linear probing, is a Hashing technique in which every element is stored directly within the hash table. During a collision, the algorithm looks for an alternative slot in the hash table through a probing sequence to place the element.

Examples of Hashing in Data Structures

Consider the following two real-life examples of Hashing in Data Structure:

a) In schools, the teacher assigns each student a unique roll number. Later on, the teacher uses that roll number to retrieve information about the student.

b) A library has a vast number of books. The librarian assigns one unique number to each book. This number helps identify the books' position on the bookshelf.

Master the art of representing large datasets quickly in our comprehensive Data Visualisation Training With D3 Course - Sign up now!

Types of Hash Functions

There are four primary types of hash functions; namely the division method, mid square method, folding method and multiplication method. These are the basic tools of modern Cryptography used in information security to authenticate messages, transactions, and digital signatures. Let’s explore them in detail below:

Mid-square Technique

The following steps are needed to calculate the mid-square hash technique:

a) k x k, or k2

b) Using the middle r digits, determine the hash value

The formula goes as follows:

h(K) = h(k x k)

(where k = key value)

Here’s an example:

Division Technique

The quickest way to create a hash value is through division. In this hash function, the k-value is divided by M, and the result is used.

The formula goes as follows:

h(K) = k mod M

where

k = key value

M = the size of the hash table

Multiplication Technique

The multiplication technique consists of the following steps:

a) Determine a constant value. A, where (0, A, 1)

b) Add A to the key value and multiply.

c) Consider kA's fractional portion.

d) Multiply the outcome of the previous step by M, the hash table's size.

Here's the formula:

h(K) = floor (M (kA mod 1))

Where

M = size of the hash table

k = key value

A = constant value

Consider the following example:

Folding Technique

The folding technique involves two steps:

a) Except for the last component (which may contain fewer digits than others), the key-value k must be divided into a predetermined number of pieces, like k1, k2, k3,..., kn, each having the same amount of digits.

b) Add each element individually. Then, the hash value is calculated without considering the final carry, if any.

Here's the formula:

k = k1, k2, k3, k4, ….., kn

s = k1+ k2 + k3 + k4 +….+ kn

h(K)= s

Where, ‘s’ refers to the addition of the parts of key k.

Consider this example:

Get acquainted with the essential concepts of Data Structure in our Data Structure and Algorithm Training - Register now!

Use cases of Hashing In DSA

Here are some exciting use cases of Hashing in Data Structure:

1) Password Storage: Hash functions are typically used to store passwords securely. Instead of storing the actual passwords, the system saves their hash values. For the purpose of authentication, when a user inputs a password, it gets hashed and compared with the stored hash value.

2) Data Integrity: Hashing ensures data integrity by generating hash values for messages or files. By comparing hash values before and after transmission or storage, it's possible to determine if any changes or tampering has occurred.

3) Data Retrieval: Hashing is utilised in Data Structures such as hash tables, which privide efficient data retrieval based upon key-value pairs. The hash value serves as an index for storing and retrieving data quickly.

4) Digital Signatures: Hash functions are integral to digital signatures. They generate a unique hash value for a message, following wich it's encrypted with the signer's private key. The public key enables verification of the message's authenticity and integrity.

Collision Resolution Techniques in Hashing

Hashing in Data Structure encounters collision if two keys are assigned the same index number in a hash table. This creates a problem because each index is supposed to store only one value. Hashing employs several collision resolution techniques to manage a hash table's performance, including:

1) Linear Probing

2) Double Hashing

Let’s explore these techniques in detail:

1) Linear Probing: Hashing results in an array index already occupied to store a value. In such a case, Hashing probes linearly for the next empty cell. Linear probing is the easiest way to resolve any collisions in hash tables. Here's an example to illustrate liner probing:

Let's use the following key-value pairs: (7, 45), (14, 32), (29, 67), (20, 89), (35, 21), (50, 54), (23, 76), (41, 90), (56, 12). The hash table size ( T ) is 30, and the hash function is ( text{hash}(n) = n % T ).

Here’s how the hash table will look:

2) Double Hashing: This technique uses two hash functions. The second hash function is used when the first function creates a collision and provides an offset index to store the value.

The formula for double Hashing is as follows:

(firstHash(key) + i * secondHash(key)) % sizeOfTable

Where i is the offset value, it keeps incrementing until it finds an empty slot.

Here’s an example to illustrate double Hashing:

Let's use the following values: (22, 45, 31, 17, 29, 56, 73, 12, 38, 49, 6).

The hash table size ( T ) is 20. The hash functions are:

a) ( h1(n) = n % 20 )

b) ( h2(n) = n % 13 )

The updated hash table will look like this:

Conclusion

Hashing is a game-changing tool in the world of Data Structures, turning complex data handling into fast, efficient, and secure operations. Its impact is undeniable, from ultrafast searches to data protection. Mastering Hashing in Data Structure, particularly understanding the SHA-256 Algorithm, not only deepens your understanding of algorithms but also equips you with skills to optimise data-driven solutions by efficiently handling graph-related problems. Mastering these concepts not only deepens your understanding of algorithms but also equips you with skills to solve a wide range of data challenges.

Acquire the skills for implementing different modelling data in our up-to-date Advanced Data Science Certification - Sign up now!