ハッシュアルゴリズム

前言
Javaでは、各オブジェクト(Object)に対応するhashcode,hashcodeがあり、その名の通りハッシュという意味で、オブジェクトを分散して格納し、ハッシュ(hash)アルゴリズムは特定のアルゴリズムに従ってアドレスバケツ(bucket:チェーンテーブル)にデータを直接指定し、集合に新しい要素を追加すると、この要素のhashcode()メソッドを呼び出します.この要素を置くべきバケツの位置に配置します.このバケツの位置に要素がなければ、このバケツの位置に直接保存することができます.このバケツの位置に別の要素がある場合は,そのequals()メソッドを呼び出して新しい要素と比較し,同じであれば保存せず,異なるであれば他のアドレスにハッシュする.
したがって、javaはeqaulsメソッドとhashCodeメソッドを次のように定義します.
1、2つのオブジェクトが同じであれば、hashCodeの値は必ず同じである.2.両オブジェクトのhashCodeが同一である場合、両オブジェクトは必ずしも同一ではない.
 
hashcode()について
1.hashcodeは検索に使用されます.データ構造を学んだことがあるなら、検索とソートの章には
例えばメモリにこのような位置がある
0     1     2     3     4     5     6     7    
私はクラスがあって、このクラスはIDというフィールドがあって、私はこのクラスを以上の8つの位置の1つに保存して、hashcodeを使わないで任意に保存して、それでは検索する時この8つの位置の中で1つずつ探して、あるいは二分法の1種類のアルゴリズムを使う必要があります.
しかしhashcodeを使うと効率が大幅に向上します.
私たちのクラスにはIDというフィールドがあります.では、hashcodeをID%8と定義し、残りの数を取得した場所にクラスを保存します.例えば私たちのIDが9で、9を除いて8の余数が1であれば、私たちはこのクラスを1という位置に存在し、IDが13であれば、求めた余数が5であれば、私たちはこのクラスを5という位置に置きます.これにより,後でそのクラスを検索する際にIDを8で割って余りを求めて直接格納場所を見つけることができるようになる.
2.しかし、2つのクラスが同じhashcodeを持っている場合、例えば9を8で割った残りの数と17を8で割った残りの数はすべて1です.このときどう判断しますか?この時点でequals()を定義する必要があります.
すなわち,hashcodeによって2つのオブジェクトがバケツに格納されているかどうかを判断するが,このバケツには多くのオブジェクトが存在する可能性があるので,equals()によってこのバケツに必要なオブジェクトを探す必要がある.
 
ステップアップ
ハッシュアルゴリズムhashCode()はハヒマを生成するために使用され、
ハヒマはハッシュ・ストレージ構造でオブジェクトを特定するためのストレージ・アドレスであり、utilパケットのようなhash付きの集合クラスは、オブジェクトを格納する際に(厳密にはオブジェクト参照)、アドレスを特定する必要があるHashMap,HashSetというストレージ構造を使用しているが、HashCode()はこの用途である.デフォルトでは、Objectクラスによって定義されたhashCodeメソッドは、オブジェクトの内部アドレスを整数に変換することによって、異なるオブジェクトに対して異なる整数を返すので、一般的には再定義が必要です.格納されたオブジェクトのhashCode()によってオブジェクトのHashSetにおける格納アドレスを決定し、equals()によって格納されたオブジェクトが重複しているかどうかを決定します.hashCode()、equals()はすべて自分で再定義する必要があります.hashCode()のデフォルトは前述していますが、equals()のデフォルトは比較のオブジェクト参照です.equals()を定義しない場合は、では、同じクラスで生成された2つのコンテンツが完全に同じオブジェクトをSetに格納することができます.彼らはequals()によって決定されるため、HashSetは彼の意味を失うことになります.以下を見てください.

import java.util.*;

/**
 * Description HashSet  
 *   equals（） hashcode()
 * @author usr1999  2014-5-11
 */
public class HashSetTest {

	public static void main(String[] args) {
		HashSet set = new HashSet();
		for (int i = 0; i <= 3; i++) {
			set.add(new Demo1(i, i));
		}
		System.out.println(set);
		set.add(new Demo1(1, 1));
		System.out.println(set);
		System.out.println(set.contains(new Demo1(0, 0)));
		System.out.println(set.add(new Demo1(1, 1)));
		System.out.println(set.add(new Demo1(4, 4)));
		System.out.println(set);
	}

	private static class Demo1 {
		private int value;

		private int id;

		public Demo1(int value, int id) {
			this.value = value;
			this.id = id;
		}

		public String toString() {
			return " value = " + value;
		}

		public boolean equals(Object o) {
			Demo1 a = (Demo1) o;
			return (a.value == value) ? true : false;
		}

		public int hashCode() {
			return id;
		}
	}
}

hashCode()とequals()をそれぞれ注釈して比較する
結果:
[ value = 2,  value = 1,  value = 3,  value = 0]
[ value = 2,  value = 1,  value = 3,  value = 0]
true
false
true
[ value = 2,  value = 4,  value = 1,  value = 3,  value = 0]
注記hashCode()
[ value = 1,  value = 0,  value = 2,  value = 3]
[ value = 1,  value = 0,  value = 1,  value = 2,  value = 3]
false
true
true
[ value = 1,  value = 0,  value = 1,  value = 2,  value = 3,  value = 4,  value = 1]
注記equals()
[ value = 2,  value = 1,  value = 3,  value = 0]
[ value = 2,  value = 1,  value = 1,  value = 3,  value = 0]
false
true
true
[ value = 2,  value = 4,  value = 1,  value = 1,  value = 1,  value = 3,  value = 0]
 
まとめ
hashCode()メソッドは、Map内の検索効率を向上させるために使用されるため、Mapは異なるhashCode()に基づいて異なるバケツに配置され、Mapは1つのオブジェクトを検索するときにhashCode()によって対応するバケツを見つけてからequals()メソッドに基づいて対応するオブジェクトを見つけます.Mapで要素を検索するには、次の2つの条件を満たす必要があります.
(1)obj 1.equals(obj 2)がtrueの場合、obj 1.hashCode() == obj2.hashCode()==true;
(2)obj 1.hashCode() == obj2.hashCode()がfalseの場合、obj.equals(obj2)==false.