Hashing Data Structure

Hashing is a well-known technique to search any particular element among several elements. It minimises the number of comparisons while performing the search.

• Hashing is extremely efficient.
• The time taken by it to perform the search does not depend upon the total number of elements.
• It completes the search with constant time complexity O(1).

Hashing Mechanism

1. An array data structure called as Hash Table is used to store the data items.
2. Based on the hash key value, data items are inserted into the hash table.

Hash Key Value

• Hash key value is a special value that serves as an index for a data item.
• It indicates where the data item should be stored in the hash table.
• Hash key value is generated using a hash function.

Hash Function

A hash function is a function that maps any big number or string to a small integer value.

Hash function takes the data item as an input and returns a small integer value as an output.

• The small integer value is called a hash value.
• Hash value of the data item is then used as an index for storing it into the hash table.

Types of Hash Functions

There are various types of hash functions available, such as:

• Truncation Method
• Mid Square Hash Function
• Division Hash Function
• Folding Hash Function
• Multiplication Method

It depends on the user which hash function they want to use.

1. Truncation Method

The Truncation Method truncates a part of the given keys, depending upon the size of the hash table.

• Choose the hash table size.
• Then the respective rightmost or leftmost digits are truncated and used as hash code/value.

Example: Table size = 10, keys: 123, 42, 56

Note: If the table size is 100, we would truncate two digits.

2. Mid Square Method

In this method:

1. Square the given keys.
2. Take the respective middle digits from each squared value.
3. Use that as the hash value for the respective keys.

Example: keys: 123, 42, 56

Advantage: Provides good distribution even if keys have patterns.
Disadvantage: Slightly slower due to multiplication.

3. Folding Method

In this method:

1. Partition the key K into number of parts, like K₁, K₂, ..., Kₙ.
2. Add the parts together.
3. Ignore the carry (if any) and use it as the hash value.

Example: keys: 123, 43, 56

Variation: If keys are large (e.g., 123456789), we can fold into 3-digit parts: 123 + 456 + 789 = 1368. Then hash = 1368 % table_size.

4. Division Method

Choose a number m (usually a prime number) larger than the number of keys. The formula is:

Hash(key) = key % Table_Size

Example: Table size = 10, keys: 20, 21, 24, 26, 32, 34

Collision: Two different keys (24 and 34) produce the same hash value 4. This is called a collision.

5. Multiplication Method

Formula:

h(key) = floor(Table_Size * (key * A mod 1))

where A is a constant between 0 and 1 (Knuth suggests A ≈ 0.618).

Example: Table size = 100, key = 123, A = 0.618

• (123 × 0.618) = 76.014
• 76.014 mod 1 = 0.014
• 100 × 0.014 = 1.4
• floor(1.4) = 1

Advantage: Works well for any table size, not just prime numbers.

Characteristics of a Good Hash Function

A hash function is a method to convert a key (like a string, number, or object) into a fixed-size integer, usually used as an index in a hash table.

A good hash function is critical to ensure that operations like insert, delete, and search in a hash table are fast and efficient (ideally O(1) time).

1. Uniform Distribution

• The function should distribute keys evenly across all slots of the hash table.
• This avoids clustering and reduces collisions.
• Example: If your hash table has 10 buckets and you insert 100 keys, each bucket should ideally have around 10 keys.

2. Deterministic

• For the same input key, it should always produce the same hash value.
• If key = 25, then hash(25) should always return the same index.

3. Minimize Collisions

• A good hash function should try to produce unique hash values for different keys as much as possible.
• Fewer collisions mean faster operations.

4. Fast Computation

• The hash function must be computationally efficient.
• It should not take more time than the actual operation (search, insert, delete).

5. Hash Value Must Be in Range

• The hash value should always be within the bounds of the hash table size.
• Example: hash(key) = key % table_size; If table size is 10, the hash must return values from 0 to 9.

6. Handles Different Types of Input

• It should be able to handle integers, strings, or compound keys gracefully.

7. Less Clustering

• Should avoid placing too many keys into neighboring slots.
• This helps reduce primary clustering (especially in linear probing).

8. Should Use All Input Data

• Every part of the key should contribute to the final hash value.
• Ignoring part of the key can lead to more collisions.

Hash Table

A Hash Table is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

It provides fast access to data using a key, typically in O(1) time for insert, delete, and search operations (in average case).

How Does a Hash Table Work?

1. A key is passed into a hash function.
2. The hash function returns an index.
3. The key-value pair is stored at that index in an array.

Basic Operations on Hash Table

Example: Basic Hash Table Implementation in C

#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10

// Hash table array (stores integers for simplicity)
int hashTable[TABLE_SIZE];

// Initialize hash table with -1 (empty)
void initialize() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = -1;
    }
}

// Division hash function
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// Insert key into hash table
void insert(int key) {
    int index = hashFunction(key);
    hashTable[index] = key;
    printf("Inserted %d at index %d\n", key, index);
}

// Search for key in hash table
int search(int key) {
    int index = hashFunction(key);
    if (hashTable[index] == key) {
        return index;
    }
    return -1;  // Not found
}

int main() {
    initialize();
    
    // Insert keys
    insert(20);
    insert(21);
    insert(24);
    insert(26);
    insert(32);
    
    // Search for a key
    int key = 24;
    int result = search(key);
    if (result != -1) {
        printf("Element %d found at index %d.\n", key, result);
    } else {
        printf("Element %d not found in the hash table.\n", key);
    }
    
    return 0;
}

Output:

Inserted 20 at index 0
Inserted 21 at index 1
Inserted 24 at index 4
Inserted 26 at index 6
Inserted 32 at index 2
Element 24 found at index 4.

Note: This simple version does not handle collisions. When inserting 34, it would overwrite 24 at index 4. That's why collision resolution techniques are needed (covered in the next post).

Advantages of Hash Tables

• Fast access (O(1)) for search, insert, delete
• Efficient for large datasets
• Widely used in databases, compilers, caches

Disadvantages of Hash Tables

• Collisions reduce performance
• Not ordered (cannot retrieve data in sorted order)
• Needs resizing if too full (rehashing)
• Complex hash functions can increase computation time

Applications of Hashing

1. Data Retrieval in Hash Tables

Hash tables allow for constant time (O(1)) access to data. Common use in implementing maps, dictionaries, and sets in languages like C++, Java, Python, etc.

• Example: unordered_map in C++, dict in Python.

2. Database Indexing

Databases use hashing for indexing to quickly locate records. Helps in implementing primary keys and index-based queries.

3. Password Storage

In security, passwords are stored as hashed values. Even if data is stolen, the actual passwords are not revealed.

Example: Using SHA-256 or bcrypt for storing password hashes.

4. Compiler Symbol Tables

Compilers use hash tables to store identifiers (variables, functions) for quick lookup. Speeds up parsing and semantic checking phases.

5. Caching

Hashing is used to store frequently accessed data in cache for quick retrieval.

Example: Browser caches, CPU caches, DNS caching.

6. Routing and Load Balancing

Hashing helps in distributing requests evenly across servers. Consistent hashing is used in distributed systems like CDNs and cloud infrastructure.

7. Blockchain and Cryptography

Blocks in blockchain are identified by their hashes. Cryptographic hash functions (e.g., SHA-256) are core to digital signatures and proof-of-work.

8. Detecting Duplicates

Hashing is used to check for duplicate files or data by comparing hash values. Common in backup systems, file systems, and data deduplication.

9. File Searching

Hash tables are used in file systems and applications to quickly locate files using filenames or metadata.

10. Memory Addressing

Hashing helps in allocating memory slots and managing page tables in operating systems.

11. Pattern Matching Algorithms

Algorithms like Rabin-Karp use hashing to efficiently search for patterns in strings.

Collision in Hashing

A collision occurs when two different keys are hashed to the same index in the hash table.

Why Do Collisions Happen?

• The hash table is smaller than the total possible keys.
• The hash function isn't perfect and may produce the same index for multiple keys.
• It's mathematically unavoidable due to the pigeonhole principle when key space > table size.

Collision Resolution Techniques

Collision Resolution Techniques are the techniques used for resolving or handling the collision.

These will be covered in detail in the next post (Unit 8.4).

Hash Function Comparison

Practice Questions

Numerical Questions

1. Using the division method, insert keys [12, 22, 32, 42, 52] into a hash table of size 10.
2. Using the mid-square method, find the hash values for keys [15, 25, 35] with table size 10.
3. What will be the hash value of 123456 using the folding method (3-digit parts)?

Theory Questions

1. What is a hash function? Explain any three types of hash functions.
2. List and explain the characteristics of a good hash function.
3. What is collision in hashing? Why does it occur?
4. Compare the advantages and disadvantages of different hash functions.
5. Explain the working of a hash table with a diagram.