Hashing Strings: Basic Approach
You'll learn: How to convert a string into a hash number by treating each character as a digit in a base-conversion system.
The Core Idea
When you hash integers, you're already working with numbers. But strings? They're made of characters. To create a hash function for strings, we need to convert text into a number first.
The basic approach treats each character as a digit in a number system — just like decimal (base 10) or binary (base 2), but typically using a larger base (like 31 or 37).
How It Works
Think of the string "cat" as if it were a three-digit number in base-31:
- Each character has a numeric value (its ASCII code:
'c'=99,'a'=97,'t'=116) - Position matters — characters at different positions contribute differently
- We compute:
hash = (99 × 31²) + (97 × 31¹) + (116 × 31⁰)
The general formula for string s of length n:
hash = s[0]×base^(n-1) + s[1]×base^(n-2) + ... + s[n-1]×base^0
This is exactly like how decimal "425" means 4×10² + 2×10¹ + 5×10⁰.
Why This Works
- Different strings → different hashes: Rearranging characters changes the result (
"cat"≠"act") - Position-sensitive: The string's order matters naturally
- Uses all characters: Every character contributes to the final value
Common base choices: 31, 37, or any prime number to spread values evenly across the hash table.
Key Takeaway: The basic string hashing approach treats a string as a multi-digit number in a chosen base, where each character is a "digit" — converting text into an integer suitable for hash table indexing.