Mastery Points
0
String Hashing Concept in dsa
Context & Logic
String hashing transforms a string into a numeric value (hash). This is used in hash tables and algorithms like Rabin-Karp to allow fast string comparisons.
Example
function getHash(str) {
let hash = 0;
for (let i = 0; i < str.length; i++) {
// Simple polynomial rolling hash
hash = (hash * 31 + str.charCodeAt(i)) % 1000000007;
}
return hash;
}Step-by-Step Logic
1
Choose a prime number (e.g., 31) and a large modulus.
2
Iterate through the string.
3
Update the hash value by multiplying it by the prime and adding the character's ASCII value.
4
Take the result modulo the chosen large number at each step to prevent overflow.
Complexity Metrics
Time Efficiency
O(n)
Memory Footprint
O(1)