基于指定Hash方法编写对应UnHash方法的面试技术题求解

Hey there! Let's work through reversing this hash function step by step—your interview problem is a classic example of reversing a polynomial rolling hash, so once you see the pattern, it's straightforward.

Let's start by understanding exactly what the hash is doing, because that's key to reversing it:

• We start with an initial value h = 7
• The string letters = "acdegiklmnoprsuw" gives each character a fixed index (0 for 'a', 1 for 'c', up to 15 for 'w'—there are 16 valid characters total)
• For every character in the input string, we update h using the formula:
  h = h * 37 + letters.IndexOf(s[i])

This is essentially treating the input string as a number in base-37, where each "digit" is the index of the character in letters. Each step shifts the current value left (multiply by 37) and adds the next digit (character index).

Your current code is trying to re-calculate the hash forward instead of reversing it, and the modulo operations with 7 are unrelated to the base-37 logic of the original hash. You need to work backwards from the final hash value to peel off each character index one by one.

To reverse the hash, we need to undo each step of the original function:

1. Start with the input hash value
2. For each step, extract the last character's index by taking the hash value modulo 37 (since h_prev * 37 + idx = h_current → idx = h_current % 37)
3. Use that index to get the corresponding character from letters
4. Update the hash value to (h_current - idx) / 37 to get back to the previous state of h
5. Repeat until we reach the initial value 7
6. Since we're peeling characters off from the end of the original string, we need to prepend each character to our result to get the correct order

Here's the working code:

static string unhashThis(Int64 integer) {
    const long initialHash = 7;
    string letters = "acdegiklmnoprsuw";
    StringBuilder unhashed = new StringBuilder(); // More efficient than string concatenation
    
    long current = integer;
    
    while (current != initialHash) {
        // Get the index of the last character added in the hash step
        int charIndex = (int)(current % 37);
        
        // Validate the index (catch invalid hash values)
        if (charIndex < 0 || charIndex >= letters.Length) {
            throw new ArgumentException("Input is not a valid hash value from hashThis.");
        }
        
        // Prepend the character (since we're working backwards)
        unhashed.Insert(0, letters[charIndex]);
        
        // Calculate the previous state of h
        current = (current - charIndex) / 37;
        
        // If we drop below the initial hash, the input is invalid
        if (current < initialHash) {
            throw new ArgumentException("Input is not a valid hash value from hashThis.");
        }
    }
    
    return unhashed.ToString();
}

Let's take a simple input to verify:

• Original string: "ac"
• hashThis("ac") calculation:
  1. First character 'a' (index 0): h = 7*37 + 0 = 259
  2. Second character 'c' (index 1): h = 259*37 +1 = 9584
• unhashThis(9584):
  1. Current = 9584 → 9584%37 =1 → character 'c', prepend to result → "c"
  2. Current = (9584-1)/37 = 259
  3. Current =259 →259%37=0 → character 'a', prepend → "ac"
  4. Current=(259-0)/37=7 → loop ends, return "ac"

Perfect—matches the original string!

内容的提问来源于stack exchange，提问作者Robert Maziar