Java hashCode()メソッド詳細解読

1.WHY hashCode()?
集合Set中の要素は無秩序で反復できないが,2つの要素が重複しているか否かを判断する根拠は何であるか.「比較対象が等しいかどうかはもちろんObject.equal()を使う」とある猿は言う.しかし,Setには多数のオブジェクトが存在し,その後集合Setに追加されるオブジェクト要素の比較回数が次第に増加し,プログラムの実行効率が大幅に低下する.Javaではハッシュアルゴリズム(ハッシュアルゴリズムとも呼ばれる)を用いてこの問題を解決し,オブジェクト(またはデータ)を特定のアルゴリズムに従って1つのアドレスに直接マッピングし,オブジェクトのアクセス効率を大幅に向上させる.これにより、大量の要素を含む集合Setにある要素(オブジェクト)を追加する必要がある場合、まずこの要素のhashCode()を呼び出すと、この要素の実際の記憶位置に一気に位置決めすることができ、この位置に要素がなければ、このオブジェクトを説明するときに初めて集合Setに格納し、直接このオブジェクトをこの位置に格納することができる.この位置にオブジェクトが存在する場合は、equal()を呼び出して、この2つのオブジェクトが等しいかどうかを確認し、等しい場合はこの要素を捨てて保存せず、等しくない場合は他のアドレスにハッシュします.
2.HOW use hashCode()?
Java言語は猿設計equal()に5つの従わなければならない要求がある.
対称性a.equal(b)がtrueを返すと、b.equal(a)もtrueを返さなければならない.反射性a.equal(a)は「true」を返さなければならない.伝達性.a.equal(b)がtrueを返し、b.equal(c)がtrueを返すと、c.equal(a)は必ずtrueを返す.整合性.a.equal(b)が「true」を返すと、a,bの内容が変わらない限り、何度繰り返してもa.equal(b)は「true」を返さなければならない.いずれの場合も、a.equals(null)は、永遠に「false」を返します.a.equals(aとは異なるタイプのオブジェクト)は永遠に「false」である.hashCode()の戻り値とequals()の関係.
a.equals(b)が「true」を返す場合、aとbのhashCode()は等しくなければならない.a.equals(b)が「false」を返すと、aとbのhashCode()が等しいか、等しくないかのいずれかになります.
次に例を示します.実際のソフトウェア開発では,この2つの方法を書き換えたほうがよい.

public class Employee {
  int    employeeId;
  String   name;

  // other methods would be in here 

  @Override
  public boolean equals(Object obj)
  {
    if(obj==this)
      return true;
    Employee emp=(Employee)obj;
    if(employeeId.equals(emp.getEmployeeId()) && name==emp.getName())
      return true;
    return false;
  }

  @Override
  public int hashCode() {
    int hash = 1;
    hash = hash * 17 + employeeId;
    hash = hash * 31 + name.hashCode();
    return hash;
  }
}

3.共通クラスのhashCode()実装方法について重点的に紹介する.
StringクラスのhasCode()

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

      for (int i = 0; i < len; i++) {
        h = 31*h + val[off++];
      }
      hash = h;
    }
    return h;
  }

このコードが一番面白いのはhashの実現方法です.最終的に計算されるhash値は、次のとおりです.
 s[0]31n-1 + s[1]31n-2 + … + s[n-1]
s[i]はstringのi番目の文字で、nはStringの長さです.では、なぜここでは他の数ではなく31を使うのでしょうか.
31は奇素数であり、乗数が偶数であり、乗算がオーバーフローすると、2に乗算することはシフト演算に等価であるため、情報が失われる.素数を使うメリットは明らかではありませんが、習慣的には素数を使ってハッシュ結果を計算します.31乗算の代わりにシフトと減算を用いることで、31*i=(i<<5)−iのより良い性能が得られるという優れた特性がある.現在のVMでは、この最適化が自動的に実行されます.(From Effective Java)
ObjectクラスのhasCode()
ObjectクラスのhashCode()はNativeメソッドです.Nativeメソッドはどのように呼び出されますか?

public native int hashCode();

ObjectクラスのNativeメソッドクラスはここで見つけることができます.詳しくは別のブログをご覧ください

static JNINativeMethod methods[] = {
  {"hashCode",  "()I",          (void *)&JVM_IHashCode},
  {"wait",    "(J)V",          (void *)&JVM_MonitorWait},
  {"notify",   "()V",          (void *)&JVM_MonitorNotify},
  {"notifyAll",  "()V",          (void *)&JVM_MonitorNotifyAll},
  {"clone",    "()Ljava/lang/Object;",  (void *)&JVM_Clone},
};

ソースコードにはgetClass()(See line 58)などがあり、hashCode()(See line 43)はJVM_を指すと定義されているIHashCodeポインタ.
jvm.cppではJVM_が定義されていますIHashCode(line 504)関数は、ObjectSynchronizer::FastHashCodeを呼び出し、synchronizerに決定する.cppは、576行のFastHashCodeと530行のget_を参照できます.next_hashの実現.