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

In a Nutshell

1. Hashing converts keys into hash values to support fast data storage and retrieval. 

2. Hash tables use hash functions to map keys to specific indexes. 

3. Common methods include separate chaining and open addressing for handling collisions. 

4. Hash functions used in data structures include division, mid-square, multiplication, and folding methods. 

5. Hashing is used in hash tables for efficient data storage and retrieval, while cryptographic hashing supports applications such as data integrity and digital signatures.

Ever wondered how computer systems can store and retrieve certain types of data efficiently? Hashing is an important technique in computer science that helps organise and access data efficiently. But what exactly are the mechanics behind hashing in data structures?

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!

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 applying a hash function to a key to generate a hash value, which is then used to determine an index for storing or retrieving data in a hash table.

Since hashing can locate data using a computed index rather than searching through every element sequentially, it can significantly improve retrieval efficiency. Hashing is widely used in applications that require efficient data storage and lookup.

What is a Hash Key?

In the context of hashing, a key is the input value used to identify or retrieve data from a hash table. A hash function processes this key to generate a hash value or hash code, which is then mapped to an index in the hash table.

In cryptographic hashing, the generated hash value can act as a digital fingerprint of the input and can be used for purposes such as data integrity checking.

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.

Hashing Flow

Key → Hash Function → Index → Store/Retrieve Data

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 table slot can store multiple elements, commonly using a linked list or another collection. When multiple keys map to the same hash table index, they are stored in the same bucket through separate chaining.

b) Open-address Hashing: Open-address hashing is a technique in which all elements are stored directly within the hash table. When a collision occurs, a probing method such as linear probing, quadratic probing, or double hashing is used to find another available slot.

Examples of Hashing in Data Structures

Consider the following two real-life examples of hashing in data structures:

a) Suppose student records are stored using student IDs as keys. A hash function converts each student ID into a hash table index, allowing the corresponding record to be retrieved efficiently.

b) In a library system, a book's unique identifier can be used as a key. A hash function maps the key to an index where information about the book can be stored or retrieved.

Types of Hash Functions

Common hash functions used in hash tables include the Division Method, Mid-square Method, Folding Method, and Multiplication Method. These methods are mainly used for distributing keys across a hash table and are different from cryptographic hash functions used in information security. Let’s explore them in detail below:

Method Match-Up

1. Division Method: Uses modulo operation 

2. Mid-square Method: Squares the key and uses middle digits 

3. Multiplication Method: Uses multiplication with a constant 

4. Folding Method: Splits and combines parts of the key

1) Mid-square Technique

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

a) Square the key k to obtain k².

b) Extract the required middle r digits or bits from k² to determine the hash value.

The extracted value can then be mapped to the valid index range of the hash table, if required.

Where:

k = key value

r = number of middle digits or bits selected

Here’s an example:

2) Division Technique

A simple and commonly used way to calculate a hash value is the division method. In this method, the remainder obtained when the key k is divided by the table size M is used as the hash value.

The formula goes as follows:

h(K) = k mod M

where

k = key value

M = the size of the hash table

3) Multiplication Technique

The multiplication technique consists of the following steps:

a) Choose a constant A such that 0 < A < 1.

b) Multiply the key k by A.

c) Take the fractional part of kA.

d) Multiply this fractional part by M, the size of the hash table, and take the floor of the result.

Here's the formula:

h(k) = ⌊M × ((kA) mod 1)⌋

Where

M = size of the hash table

k = key value

A = constant value

4) 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 number 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:

Use Cases of Hashing

Hashing has applications in both data structures and information security. In data structures, it supports efficient storage and retrieval through hash tables. In security applications, cryptographic or specialised password-hashing functions are used for purposes such as data integrity, digital signatures and password storage.

1) Password Storage: Password storage typically uses dedicated password-hashing algorithms with unique salts rather than storing plain passwords. During authentication, the entered password is processed using the same method and compared with the stored hash.

2) Data Integrity: Hashing helps verify 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 have occurred.

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

4) Digital Signatures: Cryptographic hash functions are commonly used in digital signature schemes to create a message digest. The signer uses a private key to generate the digital signature, and the corresponding public key is used to verify the signature and confirm the integrity and origin of the data.

Collision Check

When two keys map to the same index, a collision occurs. Techniques such as separate chaining, linear probing, and double hashing help resolve it.

Collision Resolution Techniques in Hashing

A collision occurs when two or more keys map to the same hash table index. The collision must then be handled using a suitable resolution technique, such as separate chaining or open addressing. Two commonly used open-addressing collision resolution techniques are:

1) Linear Probing

2) Double Hashing

Let’s explore these techniques in detail:

1) Linear Probing: When a key maps to an array index that is already occupied, a collision occurs. Linear probing checks subsequent slots sequentially until an available slot is found. Linear probing is a simple open-addressing technique for resolving collisions in hash tables. Here's an example to illustrate linear 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: Double hashing uses two hash functions. The first determines the initial index, while the second determines the step size used to probe alternative positions when a collision occurs.

The formula for double hashing is as follows:

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

Where i is the probe number, starting from 0 and increasing until an available slot is found.

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) = 13 - ( n % 13 )

The updated hash table will look like this:

Build stronger coding skills with our Programming Training Courses - strengthen your programming knowledge today!