代码之家  ›  专栏  ›  技术社区  ›  David Citron

证明:为什么Java.Lang.Stord.HasCODE()的实现与它的文档匹配?

  •  9
  • David Citron  · 技术社区  · 16 年前

    的JDK文档 java.lang.String.hashCode() famously 说:

    字符串对象的哈希代码计算为

    s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
    

    使用 int 算术,其中 s[i] 是* i *字符串的第个字符, n 是字符串的长度,并且 ^ 表示求幂。

    此表达式的标准实现是:

    int hash = 0;
    for (int i = 0; i < length; i++)
    {
        hash = 31*hash + value[i];
    }
    return hash;
    

    看着这个让我觉得我在学习算法课程的时候睡着了。这个数学表达式是如何翻译成上面的代码的?

    5 回复  |  直到 11 年前
        1
  •  12
  •   Laurence Gonsalves    16 年前

    我不确定您是否遗漏了文档中的“^表示求幂”(而不是xor)。

    每次通过循环时,哈希的前一个值乘以31 再一次 在添加到的下一个元素之前 value .

    我们可以通过归纳法证明这些东西是相等的,但我认为一个例子可能更多 清楚:

    假设我们正在处理一个4字符的字符串。让我们展开循环:

    hash = 0;
    hash = 31 * hash + value[0];
    hash = 31 * hash + value[1];
    hash = 31 * hash + value[2];
    hash = 31 * hash + value[3];
    

    现在,通过将哈希的每个值替换为以下语句,将这些值组合成一个语句:

    hash = 31 * (31 * (31 * (31 * 0 + value[0]) + value[1]) + value[2])
         + value[3];
    

    31*0为0,因此简化:

    hash = 31 * (31 * (31 * value[0] + value[1]) + value[2])
         + value[3];
    

    现在将两个内项乘以第二个31:

    hash = 31 * (31 * 31 * value[0] + 31 * value[1] + value[2])
         + value[3];
    

    现在将三个内部术语乘以前31个:

    hash = 31 * 31 * 31 * value[0] + 31 * 31 * value[1] + 31 * value[2]
         + value[3];
    

    并转换成指数(不再是Java):

    hash = 31^3 * value[0] + 31^2 * value[1] + 31^1 * value[2] + value[3];
    
        2
  •  24
  •   CookieOfFortune    16 年前

    展开循环。然后你得到:

    int hash = 0;
    
    hash = 31*hash + value[0];
    hash = 31*hash + value[1];
    hash = 31*hash + value[2];
    hash = 31*hash + value[3];
    ...
    return hash;
    

    现在您可以进行一些数学操作,插入0作为初始哈希值:

    hash = 31*(31*(31*(31*0 + value[0]) + value[1]) + value[2]) + value[3])...
    

    再简化一点:

    hash = 31^3*value[0] + 31^2*value[1] + 31^1*value[2] + 31^0*value[3]...
    

    这基本上就是给出的原始算法。

        3
  •  10
  •   Devin Jeanpierre    16 年前

    归纳法证明:

    T1(s) = 0 if |s| == 0, else s[|s|-1] + 31*T(s[0..|s|-1])
    T2(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
    P(n) = for all strings s s.t. |s| = n, T1(s) = T2(s)
    
    Let s be an arbitrary string, and n=|s|
    Base case: n = 0
        0 (additive identity, T2(s)) = 0 (T1(s))
        P(0)
    Suppose n > 0
        T1(s) = s[n-1] + 31*T1(s[0:n-1])
        T2(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] = s[n-1] + 31*(s[0]*31^(n-2) + s[1]*31^(n-3) + ... + s[n-2]) = s[n-1] + 31*T2(s[0:n-1])
        By the induction hypothesis, (P(n-1)), T1(s[0:n-1]) = T2(s[0:n-1]) so
            s[n-1] + 31*T1(s[0..n-1]) = s[n-1] + T2(s[0:n-1])
        P(n)
    

    我想我拿到了,要求提供证据。

        4
  •  9
  •   Bobby Eickhoff    16 年前

    看看前几个迭代,您会发现模式开始出现:

    hash0 = 0 + s0 = s0
    hash1 = 31(hash0) + s1 = 31(s0) + s1
    hash2 = 31(hash1) + s2 = 31(31(s0) + s1) + s2 = 312(s0) + 31(s1) + s2
    ...
    
        5
  •  0
  •   Community CDub    8 年前

    把字符串的散列码数出来是不是一点用都没有? 所有字符中 ?想象一下文件名或类名的完整路径放入哈希集中。或者使用字符串文档而不是列表的哈希集的人,因为“ HashSet always beats Lists “。

    我会做如下的事情:

    int off = offset;
    char val[] = value;
    int len = count;
    
    int step = len <= 10 ? 1 : len / 10;
    
    for (int i = 0; i < len; i+=step) {
       h = 31*h + val[off+i];
    }
    hash = h
    

    最后,hashcode只是一个提示。