19:I[42738,["32309","static/chunks/16a1051c-73f7d929dbf62293.js","47846","static/chunks/034d7036-dce40e87919d0db0.js","68526","static/chunks/fcf0fb0f-0d0fe13dc4428b32.js","34726","static/chunks/8777d6a5-3f486ccede479e9b.js","32075","static/chunks/32075-2bec0a25a2d7c61f.js","92718","static/chunks/92718-1248a2c81ad0a900.js","48734","static/chunks/48734-303381ecb69a6735.js","43456","static/chunks/43456-10541eaa9e81306f.js","13170","static/chunks/13170-784eca6f0877a13c.js","14667","static/chunks/14667-9460958e0222af83.js","64023","static/chunks/64023-d4c0b157bbe6a774.js","69043","static/chunks/69043-1e43b892c05d81f3.js","17219","static/chunks/17219-d1c3deb3f08d43a4.js","58967","static/chunks/58967-13ceaf1ea576a093.js","57601","static/chunks/57601-45dbf629c83c09aa.js","10554","static/chunks/10554-bccad16034ff5347.js","40232","static/chunks/40232-0a030f25a795d86d.js","56442","static/chunks/56442-d6836a9b9496f058.js","25266","static/chunks/25266-b55668a535a787a7.js","72515","static/chunks/72515-65f0a3c7f381746d.js","34159","static/chunks/34159-7f12f61339b5ace3.js","41543","static/chunks/41543-7e7fe7fc99d86165.js","75633","static/chunks/75633-dedc52f5948e8fce.js","52432","static/chunks/52432-126d8963dc69cf09.js","83596","static/chunks/83596-614e2af0a09a620b.js","96901","static/chunks/96901-5ebc2a5e68fad39c.js","23656","static/chunks/23656-6fcf6c6fc7d973e6.js","44575","static/chunks/44575-8a40a063c2636038.js","22250","static/chunks/app/(free)/%5Bcategory-slug%5D/%5Barticle-slug%5D/page-71b15814c732a72f.js"],"default"] 1b:I[37419,[],"IconMark"] 1a:T9d7,

Introduction:

In this article, we will be discussing the Hashing in Strings. Hashing refers to the process of converting a string into a numeric value, called a hash value, using a mathematical formula. It helps in comparing strings, searching efficiently, and solving complex problems like pattern matching.

Need of Hashing:

Hashing is essential as it helps in following operations:

1. Efficient Comparisons: Comparing large strings is slow. Hash values allow comparison in constant time.
2. Faster Lookups: Hash tables like dictionaries or unordered maps use hash values to store and retrieve strings quickly.
3. Detect Duplicates or Anagrams: Hashing helps in checking duplicates or determining anagram groups efficiently.
4. Pattern Matching: Algorithms like Rabin-Karp use string hashing to find substrings in linear time.

How Does String Hashing Work?:

String hashing treats each character as a number and combines them using a mathematical formula. A common formula is Polynomial Rolling Hash. Using this hash value is calculated as follows:

Hash(s) = (s[0] * p^0 + s[1] * p^1 + s[2] * p^2 + ... + s[n-1] * p^(n-1)) % m

where, s[i] is the character's ASCII or mapped value (like 'a' = 1),
p is a prime base (commonly 31 or 53) and
m is a large prime modulus to avoid overflow and reduce collisions.

Handling Collisions:

Two different strings can have the same hash, called a collision. To reduce this, we use a large m (like 1e9+7). We can also use double hashing (combine two different hash functions) or use a good base (p) that spreads values well.

Example:
Calculate Hash value of string s = "abc".
Solution:
Let us assume p to be 31 and m to be 1e9+9.
Now, we can map characters as following: 'a' = 1, 'b' = 2 and 'c' = 3.
Thus, Hash(s) = (1 * 31^0 + 2 * 31^1 + 3 * 31^2) % 1e9+9
Hash(s) = 2946.
Therefore, "abc" gets hashed to value 2946. 6:["$","