String Hashing and Rolling Hash Quiz Quiz

Explore core concepts and techniques in string hashing and rolling hash with this engaging quiz. Strengthen your understanding of hash functions, collision prevention, modulus properties, and real-world applications relevant to efficient string processing.

1. Hash Function Output Range

   When applying a hash function to a string using modulus N, such as hash(s) mod N, what is the guaranteed range of possible output values for the hash?

   1. 1 to N-1
   2. 0 to N-1
   3. 0 to N
   4. 1 to N

   Explanation: The output of hash(s) mod N is always in the range 0 to N-1, as the modulus operation returns remainders starting from zero up to one less than the modulus. The distractor '1 to N' is incorrect because it includes N, which is never possible. '1 to N-1' excludes zero, which can be an output. '0 to N' is incorrect because N is not included in a modulus result.

2. Rolling Hash Update Efficiency

   Which key advantage does the rolling hash technique provide when calculating hash values for all substrings of length k in a long text?

   1. It reduces the original string size
   2. It requires no modulus operation
   3. It allows updating the hash in constant time for each window
   4. It guarantees no hash collisions

   Explanation: The main advantage of rolling hash is that it lets you update the hash value in constant time when moving from one substring to the next, significantly speeding up searching. Rolling hash does not prevent hash collisions, so the second option is incorrect. It doesn’t reduce the string size or eliminate the need for the modulus operation, making the last two distractors incorrect.

3. Potential Cause of Hash Collisions

   While comparing hashes of two different strings, which scenario is most likely to result in a hash collision when using a basic hash function with a small modulus value (e.g., mod 100)?

   1. The hashing process skips characters
   2. The hash always produces negative values
   3. Many different strings may share the same remainder after division
   4. Each character uses a unique prime number

   Explanation: A small modulus increases the chance that different strings will have the same remainder after division, leading to hash collisions. The second option is unrelated to the modulus's impact. The third option, using a unique prime for each character, can help reduce collisions. Hash functions typically use non-negative results, making the last option incorrect.

4. Application Scenario for Rolling Hash

   Which of the following problems is commonly solved using a rolling hash algorithm in practical applications?

   1. Sorting an array of numbers
   2. Counting how many times a character appears
   3. Efficient substring search within a large text
   4. Finding the longest common subsequence

   Explanation: Rolling hashes are widely used in substring search algorithms, enabling quick comparisons with constant-time updates for sliding windows. Finding the longest common subsequence often uses dynamic programming, not rolling hash. Counting character occurrences and sorting arrays don't benefit from rolling hash techniques, making those options incorrect.

5. Prime Modulus in Rolling Hash

   Why is it a common practice to choose a large prime number as the modulus when implementing rolling hash functions?

   1. It shortens the resulting hash values
   2. It increases the chances of overwriting data
   3. It reduces the probability of hash collisions
   4. It makes hash values always even

   Explanation: A large prime modulus helps distribute hash values more evenly, reducing the likelihood of collisions. It does not result in hash values always being even, so the second option is incorrect. Primes do not guarantee shorter hash values, and increasing collision resistance doesn't overwrite data, making the last two distractors inappropriate.