いけむランド

はてダからやってきました

String.hashCode() の変遷

Java

もう遠い昔の話だし、今さらどうでもいいことだけど、日本語資料が見当たらなかったので、まとめておく。


実は Java2 (1.2) 以降とそれより前で String.hashCode() のアルゴリズムが異なっている。

現在の hashCode

現在 (1.2 以降) のアルゴリズムは単純にすべての文字に適当な係数をかけて算出する。

public int hashCode()

この文字列のハッシュコードを返します。String のハッシュコードは、次の方法で計算します。
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
int 算術を使います。s[i] は文字列の i 番目の文字、n は文字列の長さ、^ は、べき乗を示します。空の文字列のハッシュ値は 0 です。


ちなみに Java で書くと以下のようになる。*1

public int hashCode()
{
  int hashCode = 0;
  int limit = count + offset;
  for (int i = offset; i < limit; i++)
    hashCode = hashCode * 31 + value[i];
  return hashCode;
}

以前の hashCode

一方、昔 (1.1 以前) のアルゴリズムは JLS1 の 20.12.10 に言語仕様として、明記されているもので現在のものよりもちょっと複雑に見える。

20.12.10 public int hashCode()
オブジェクトの長さに応じて，この String オブジェクトのハッシュコードを次のいずれかの方法で計算し，その値を返す。ここで，n を文字の並びの長さ ([http://www.y-adagio.com/public/standards/tr_javalang/javalang.doc.htm#13985:title=20.12.11]) とし，[tex:c_i] をインデクス i の文字とする。

  • n \leq 15 の場合，ハッシュコードは，int 演算を使用して \sum_{i=1}^{n-1} c_i 37^i で求められる。
  • n \gt 15 の場合，ハッシュコードは，int 演算を使用して \sum_{i=1}^{m} c_{i-k} 39^i で求められる。ここで，k=\lfloor \frac{n}{8} \rfloor，また m=\lceil \frac{n}{k} \rceil であり，文字列から 8 文字又は 9 文字だけをサンプリングする。


これを Java で書くと、以下のようになる。*2

public int hashCode() {
    int h = 0;
    int off = offset;
    char val[] = value;
    int len = count;

    if (len < 16) {
        for (int i = len ; i > 0; i--) {
            h = (h * 37) + val[off++];
        }
    } else {
        // only sample some characters
        int skip = len / 8;
        for (int i = len ; i > 0; i -= skip, off += skip) {
            h = (h * 39) + val[off];
        }
    }

    return h;
}

変わった理由

以前のアルゴリズムでは Java のコードを見ればわかるとおり、長い (16 文字以上の) 文字列の場合にすべての文字をハッシュの計算に使用しないことで、衝突が発生しやすかったという問題があったため、現在のようにすべての文字を計算に使用するアルゴリズムに変わったとのこと。

以前のアルゴリズムで衝突する例は Bug ID: 1258091 String.hashCode() produces the same value for too many unequal strings. にある。以下に実際にやってみた例を示す。

public class OldStringHashCode
{
  static public int getOldStringHashCode(String s)
  {
    int length = s.length();
    int hash = 0;
    int offset = 0;

    if (length < 16) {
      for (int i = length; i > 0; i--) {
        hash = (hash * 37) + s.charAt(offset++);
      }
    } else {
      int skip = length / 8;
      for (int i = length; i > 0; i -= skip, offset += skip) {
        hash = (hash * 39) + s.charAt(offset);
      }
    }

    return hash;
  }

  static public void main(String[] args)
  {
    String s1 = "abcdefghijklmnopqrstuvwxyz";
    String s2 = "a12d34g56j78m9!p@#s$%v^&y*A";
    System.out.println("[" + s1 + "] = " + getOldStringHashCode(s1));
    System.out.println("[" + s2 + "] = " + getOldStringHashCode(s2));
  }
}

% javac OldStringHashCode.java 
% java OldStringHashCode
[abcdefghijklmnopqrstuvwxyz] = -1412339411
[a12d34g56j78m9!p@#s$%v^&y*A] = -1412339411
%

*1:http://www.docjar.com/html/api/java/lang/String.java.html からアルゴリズムを実装するコードのみを抜粋した。

*2:ftp://ftp.gwdg.de/pub/languages/java/linux/JDK-1.1.8/i386/v3/jdk118_v3-glibc-2.1.3.tar.bz2 に含まれる src.zip より抜粋した。