Hashing Non-Numeric Data: String Hash Functions

This chapter explores how hash tables handle non-numeric data types (such as strings and characters) and explains the internal mechanics of hash tables during resizing (rehashing). We will break down the two-step pipeline of a hash function—Hash Code Generation and Compression/Mapping—and discuss how these concepts lay the foundation for secure real-world applications like cryptography.

1. The Mechanics of Rehashing (Table Resizing)

When a hash table's load factor exceeds a certain threshold, it undergoes a process called rehashing to maintain its efficiency.

The Step-by-Step Resizing Process

If your initial hash table size is $10$:

1. Threshold Reached: As more elements are inserted, the load factor increases, risking high collision rates.
2. Table Destruction: The internal system destroys the old table of size $10$.
3. New Table Creation: A new table of double the size ($20$) is allocated in memory.
4. Element Redistribution: Every single element from the old table is re-evaluated. Because the table size has changed, the compression formula (e.g., key % new_size) yields different indices. The elements are mapped and moved to their correct new locations.

Amortized $O(1)$ Time Complexity

Because resizing requires iterating through all existing elements and re-inserting them, a single resize operation takes $O(N)$ time. However, because resizing happens infrequently (only when the table fills up), this cost is spread out over many insertions.

Therefore, the average (amortized) time complexity for insertion, deletion, and search remains $O(1)$. This is why we refer to hash table operations as constant time on average, rather than a strict worst-case $O(1)$.

2. Internal Storage in Unordered Maps

In standard libraries (such as C++'s std::unordered_map), data is stored as key-value pairs. To ensure retrieval works correctly, keys must be unique.

Node-Based Storage Representation

When you store a key-value pair, it is typically packaged inside a node structure at its designated bucket location:

If you insert another pair, such as Key 42 and Value 78, the hash table uses the unique key (42) to determine its storage location and retrieve it later.

3. Anatomy of a Hash Function

A hash function is not always a single mathematical formula. For complex or non-numeric data, it is split into a two-step pipeline:

The Two Components Explained

4. Hashing Non-Numeric Data (Strings & Characters)

When hashing a string like "rohit", we cannot directly apply a modulo operator (e.g., "rohit" % 20 is mathematically invalid). We must first generate an integer hash code.

The ASCII-Based Conversion Strategy

To convert a string into an integer, we can leverage the ASCII values of its individual characters.

Note: While actual ASCII values for lowercase letters are 'r' = 114, 'o' = 111, 'h' = 104, 'i' = 105, 't' = 116, the conceptual approach remains the same: we map each character to its integer value and aggregate them.

Conceptual Example:

Let's assume simplified mock values for demonstration:

• r $\rightarrow$ $89$
• o $\rightarrow$ $90$
• h $\rightarrow$ $72$
• i $\rightarrow$ $73$
• t $\rightarrow$ $84$

By summing or combining these values using a polynomial rolling approach, we generate a unique integer (the Hash Code). Once we have this integer, we apply the compression function:

C++ Implementation: Custom String Hash Function

Below is a practical implementation of a polynomial rolling hash function used to convert a string into a hash index:

#include <iostream>
#include <string>

// A simple polynomial rolling hash function
int getHashCode(const std::string& key) {
    int hash_code = 0;
    int prime_multiplier = 31; // A small prime number to reduce collisions
    
    for (char ch : key) {
        hash_code = hash_code * prime_multiplier + ch;
    }
    return hash_code;
}

// Compression function to map hash code to table size
int getTableIndex(const std::string& key, int table_size) {
    int hash_code = getHashCode(key);
    
    // Handle negative hash codes from integer overflow
    int index = hash_code % table_size;
    if (index < 0) {
        index += table_size;
    }
    return index;
}

int main() {
    std::string name = "rohit";
    int table_size = 20;
    
    int index = getTableIndex(name, table_size);
    
    std::cout << "String: " << name << std::endl;
    std::cout << "Hash Code: " << getHashCode(name) << std::endl;
    std::cout << "Mapped Table Index (Size " << table_size << "): " << index << std::endl;
    
    return 0;
}

5. Real-World Analogy: Secure Communication & Cryptography

The concept of hashing extends far beyond basic data structures into the realm of network security and cryptography.

The "Father-in-the-Middle" Analogy

Imagine you want to send a private message to your partner over the internet:

• The Vulnerability: If you transmit the message "I love you" in plain text, anyone sitting in the middle of the network connection (such as an ISP, a hacker, or an observant parent) can intercept, read, and understand the message instantly.
• The Solution: To prevent unauthorized access, the data must be transformed. In cryptography, we use secure hashing algorithms (like SHA-256) and encryption keys to scramble the plain text into an unreadable format (ciphertext) before sending it over the wire. Even if intercepted, the message looks like random gibberish to anyone without the decryption key.

Summary and Key Takeaways

• Amortized Complexity: Rehashing (resizing the table and redistributing elements) takes $O(N)$ time, but because it occurs infrequently, the average time complexity for hash table operations remains $O(1)$.
• Rehashing Steps: When resizing, the old table is destroyed, a new larger table is allocated, and all existing elements are re-mapped using the new table size.
• Unique Keys: Unordered maps require unique keys to correctly locate and retrieve values stored in internal nodes.
• Two-Step Hashing: Hashing non-numeric data requires a Hash Code Generator (to convert the data to an integer) followed by a Compression Function (to map the integer to a valid index).
• String Hashing: Strings are converted to integers by processing the ASCII values of their characters, often using a prime multiplier to minimize collisions.
• Security Foundation: The process of transforming readable input data into unique, irreversible, or encrypted values is the cornerstone of secure internet communication and cryptography.