String Hashing
String hashing maps a string to an integer called its hash value, enabling O(1) average-time equality checks and set/map lookups for strings. Instead of co...
Converting Strings to Numbers for Fast Comparison and Lookup
String hashing maps a string to an integer called its hash value, enabling O(1) average-time equality checks and set/map lookups for strings. Instead of comparing two strings character by character in O(n), you compare their hash values in O(1), with the caveat that hash collisions require a fallback character comparison.
Polynomial rolling hash is the most common technique for competitive programming and algorithm design. Given a string S of length n, define hash(S) as the sum over i from 0 to n-1 of S[i] times p^i, taken modulo a large prime M. Here p is a prime base larger than the alphabet size, commonly 31 for lowercase letters (since 'a' maps to 1, 'b' to 2, and so on up to 26) or 131 for general ASCII. M is typically a large prime like 10^9 plus 7.
Precomputing prefix hashes enables substring hashing in O(1). Define h[0] equals 0 and h[i] equals h[i-1] plus S[i-1] times p^(i-1). The hash of the substring S[l..r] is (h[r+1] minus h[l]) divided by p^l modulo M. Division modulo M requires computing the modular multiplicative inverse of p^l, which is done using Fermat's little theorem in O(log M) time, or you can precompute all inverse powers in O(n).
Collisions occur when two different strings have the same hash. With a single hash function modulo M of about 10^9, the probability of a random collision between two strings is about 1 in 10^9. For applications requiring higher certainty, double hashing uses two independent (p, M) pairs and requires both hashes to match. The probability of a false positive drops to about 1 in 10^18.
String hashing enables efficient solutions to many problems. Checking whether two substrings are equal is O(1) after O(n) preprocessing. Finding the longest common substring of two strings can be done in O((n plus m) log(n plus m)) using binary search on length combined with hashing. Counting distinct substrings, detecting duplicate substrings, and many rolling-window problems all benefit from hashing.
Cryptographic hash functions like SHA-256 serve a different purpose: they must be collision-resistant under adversarial inputs. Polynomial rolling hashes are not cryptographically secure but are entirely appropriate for algorithmic purposes where the input is not adversarial.
Worked example: check whether two substrings of a 10,000-character string are equal, and perform 100,000 such queries. Precompute prefix hashes in O(n). Each query is then O(1). Total: O(n plus k) versus O(n times k) for naive character-by-character comparison.
Interview tip: mention the collision probability when proposing string hashing. Saying "I will use double hashing to reduce collision probability to approximately 1 in 10^18" demonstrates statistical awareness that impresses interviewers.