面试之谜

Question

编写Java代码以查找仅包含以下字符的9个字母字符串: acegikmnoprstuvy

哈希字符串产生的位置: 932246728227799

如果哈希函数由以下伪代码定义：

hash (String s) { 
    h = 7 
    letters = "acegikmnoprstuvy" 
    for(i = 0; i < s.length; i++) { 
        h = (h * 37 + letters.indexOf(s[i])) 
    } 
    return h 
} 

例如，如果我们试图找到哈希字符串产生690336378753的7个字母字符串，答案将是"reports“。

Answer 1

哈希实际上是将字符串从基数37编码到基数10。为了反转哈希，我们将从基数10转换为基37。不如趁我们在看的时候查一下这些人物。

public class Hashcode {
  static final String ALPHABET = "acegikmnoprstuvy";

  public static long hash(String s) {
    long h = 7;
    for (int i=0; i<s.length(); i++) {
      h = (h * 37 + ALPHABET.indexOf(s.charAt(i)));
    }
    return h;
  }

  public static String unhash(long n) {
    String result = "";
    while (n>7) {
      result = ALPHABET.charAt((int)(n%37)) + result;
      n = n/37;
    }
    if (n != 7) {
      System.err.println("Error, hash parity incorrect.");
      System.exit(1);
    }
    return result;
  }

  public static void main(String[] args) {
    System.out.println(hash("reports"));
    System.out.println(unhash(690336378753L));
    System.out.println(unhash(932246728227799L));
    System.out.println(hash("mymitsapp"));
  }
}

Answer 2

从数学上看这个函数是做什么的。

输入for循环时，以h=7开始。for循环遍历单词中的字母。每次迭代更新h：h = h * 37 + next_letter

所以试着选一个单词，比如“加”。

循环1：h = 7 * 37 + "A"

循环2：h = (7 * 37 + "A") * 37 + "D"→7 * 37^2 + "A" * 37 + "D"

循环3：h = (7 * 37^2 + "A" * 37 + "D") * 37 + D→7 * 37^3 + "A" * 37^2 + "D" * 37 + "D"

所以您的散列将是7 * 37^3 + "A" * 37^2 + "D" * 37 + "D"。

在实际情况下，字母被转换为索引号，而且由于最大索引小于37，因此只能得到一个可能的解决方案。将散列重写为7 * 37^3 + "A" * 37^2 + "D" * 37 + "D"还可以清楚地将其写入基37作为7 "A" "D" "D"。

简短回答:只需将其转换为基数37，并移除前面的7。

Answer 3

因此，基本上，您将最终解决以下问题：word(hashcode,len) = let w: hash(w) = hashcode或具有更具体的功能：

word(hashcode,len) = let w: for(i = 0 , i < len , 1){w[len-i-1] * 37^i} + 909732178565539 - hashcode = 0

现在我们有了一个方程，下一步是解决它:将(hashcode-909732178565539)从十进制转换为基数37。在一个基数为37的数字中，每一个数字将代表你的单词中的一个字符。现在你需要做的就是把个位数转换成你的字符。