Hashing in Data Structure

What is Hashing?

Hashing is the process of mapping keys and values into a hash table using a hash function. Hashing is used for faster access to elements, which is determined by the efficiency of the hash function.

Components of hashing

There are primarily three components to hashing:

1. Key
2. Hash Function
3. Hash Table

Working of Hashing in Data Structures

• Hashing converts data into hash code, which is stored in a hash table.
• Hash code is used to obtain data from a table.
• Caches and databases are commonly utilized for quick search results.
• It can store data of any type, including integers, texts, and objects.
• When done correctly, this is a simple and efficient solution.
• It is commonly used in computer programming.

Importance of Hashing

• Efficient retrieval of large data sets.
• Hash codes serve as unique identifiers, ensuring data integrity.
• Structured storage, with an index for each entry in a hash table, ensures efficient storage and retrieval.

Limitations of Hashing

• Collisions happen when several inputs share the same hash value.
• The performance of the hashing algorithm is determined by the quality of the hash function.
• Poorly designed hash functions may result in more collisions, lowering algorithm performance.

Use cases of Hashing in Data Structure

• Password Storage: Passwords are hashed for secure storage; the system compares hashed passwords upon authentication.
• Data integrity: Creates hash values for files and messages to identify modifications or tampering.
• Data Retrieval: Hash tables use key-value pairs to retrieve data efficiently.
• Digital Signatures: Creates unique hash values for messages in digital signatures to ensure authenticity and integrity.

What is meant by a Hash Key?

A hash key, also known as a hash value or hash code, is a fixed-size numerical or alphanumeric representation produced by a hashing algorithm. It is created by hashing the input data, which might be a text string or a file.

What is the Hash Function?

A hash function is a function that accepts a set of arbitrary-size inputs and converts them into a table or other data structure with fixed-size elements.

Types of Hash Functions

The following are the primary types of hash functions:

1. Division Method
2. Mid Square Method
3. Folding method
4. Multiplication method

1. Division Method

Divides the key by a fixed number, typically a prime, and uses the residue as the hash code.

2. Mid-Square Method

Squares the key and uses a chunk of its middle digits as the hash code.

3. Folding Method

Divides the key into equal-sized parts, adds or concatenates them, and then calculates the modulus to obtain the hash code.

4. Multiplication Method

The key is multiplied by a constant (typically a fraction), and the fractional part is used as the hash code.

Features of Hash Function

• A message can be any length.
• Message processes have a set length.
• A message digest can be calculated quickly and easily.
• Message digests cannot be formed from the hash; they are irreversible.
• Small modifications have a significant impact on message values.
• The hash is collision-free since two distinct messages cannot result in the same hash value. 

What is Collision in Hashing?

When a hashing technique uses a hash function to obtain the same hash value for two or more keys, the term is referred to as a collision in a hash table.

Types of Collision Resolution Techniques in Hashing

There are two main Collision Resolution Techniques in Hashing:

1. Open hashing, separated chaining and closed addressing
2. Open addressing, closed hashing

Load Factor in Hashing

The load factor of a hash table is the number of objects in the hash table divided by its size. The load factor is the deciding factor when rehashing a prior hash function or adding new elements to an existing hash table. It helps us determine the efficiency of the hash function, i.e., if the hash function we employ distributes the keys uniformly in the hash table.