ハッシュとハッシュ・コードの概要

ハッシュセットまたはマップ(Map)を学習するとき、equals()とhashCode()の2つの方法に慣れていないかもしれません.ハッシュ・セットに追加されたオブジェクトは、hashCode()メソッドを正しく実装してこそ、セットに重複する値が表示されないことを保証することができます.最近、『Thinking in Java』という本を読んでいると、そのシステムを紹介しているので、まとめてみましょう.
ハッシュ・コードの初歩的な理解
開発では、HashMapの使用に慣れていませんが、時には間違いを犯すこともあります.まず例を見てみましょう

//      ，      
class Person {
    private int cardId;
    public Person(int cardId) {this.cardId= cardId;}

    @Override
    public String toString() {
        return "Person#" + cardId;  //    
    }
}

//    
class Sex {
    private int  i = (int) (Math.random() * 2);

    @Override
    public String toString() {
        return i == 0? "male" : "female";  //        
    }
}

public class TestMap {
    public static void main(String[] args) throws Exception{
        detectSex(Person.class);
    }

    public static <T extends Person> void detectSex(Class<T> type) throws Exception {
        Constructor<T> person = type.getConstructor(int.class);
        Map<Person, Sex> map = new HashMap<>();  //    HashMap            
        for (int i = 0; i < 10; i++) {
            map.put(person.newInstance(i), new Sex());
        }
        System.out.println("map:" + map);
        Person p = person.newInstance(3);  //       3  ，  map       
        System.out.println("      " + p);
        if (map.containsKey(p))
            System.out.println(map.get(p));
        else
            System.out.println("   ");
    }
}

出力結果:

map:{Person#7=female, Person#0=female, Person#9=male, Person#3=female, Person#5=male, Person#8=female, Person#2=male, Person#4=male, Person#1=male, Person#6=male}
  Person#3  
   

このプログラムは簡単そうに見えますが、結果的にエラーが発生しました.PersonはデフォルトでObjectクラスに継承されているため、ObjectクラスのhashCode()メソッドを使用してハッシュコードを生成します(アドレスに基づいて一定のアルゴリズムで生成されます).明らかに、1回目の作成と2回目の作成のPerson 3アドレスが異なり、ハッシュコードが異なるため、この人は見つからない.したがって,hashCode()メソッドを正確な形式で実現しなければならない.もちろんhashCode()メソッドを上書きする場合もequals()メソッドを上書きする必要があります.このメソッドもObjectクラスから来ているので、正確な方法で実現する必要があります.ここでequals()メソッドについて述べるときは、以下の点に注意しなければなりません.
1)任意のxに対して,x.equals(x)は必ずtrueを返す.2)対称性任意のx,y,x.equals(y)とy.equals(x)の戻り値は同じである.3)伝達性は任意のx,y,zに対してx.equals(y)とy.equals(z)の戻り値が同じである場合,x.equals(z)の戻り値も同じである.4)整合性任意のx,yについて,x.equals(y)が何回実行されても,戻り値はtrueかfalseである.5)任意のxに対して!=null,x.equals(null)はfalseを返します.(生徒党として初めて自分が学んだ離散構造の知識にT-Tを使ったと感じた)
では、これらの理念を持ってからPerson類を修正します.

class Person {
    private int cardId; 
    public Person(int cardId) {this.cardId= cardId;}

    @Override
    public String toString() {
        return "Person#" + cardId;
    }

    @Override
    public boolean equals(Object obj) {
        return  (obj instanceof Person && (((Person) obj).cardId == cardId)); 

    }

    @Override
    public int hashCode() {
        return cardId;  //           
    }
}

再実行結果:

map:{Person#0=male, Person#1=male, Person#2=female, Person#3=female, Person#4=male, Person#5=female, Person#6=male, Person#7=male, Person#8=female, Person#9=female}
  Person#3  
female

比較時から比較番号までを比較し,番号をハッシュコードとするとhashCode()とequals()メソッドプログラムを上書きして正常に結果を出力する.
ハッシュの実装
ハッシュの実装方法を理解する前に、まずハッシュの意味を理解する必要があります.ハッシュは、(Map)などの場合に便利であるだけでなく、あるオブジェクトを通じて別のオブジェクトを検索することができます.その価値は、ハッシュがクエリーを迅速に行うことができる速度にあります.では、ハッシュはどのように実現されるのでしょうか.要素のセットを格納する最も速いデータ構造が配列であることを知っています.そのため、配列を使用してキーの情報を格納します.この配列が形成したテーブルは、ハッシュ・リスト、ハッシュ・テーブルとも呼ばれます.配列は、キー自体を保存するのではなく、アルゴリズムによってキーオブジェクトを変換した数字を保存します.この数字を配列の下付き文字として保存します.この数字をハッシュコードと呼びます.前述のPersonクラスのようにhashCode()メソッドが上書きされており、このメソッドはハッシュ関数と呼ばれ、ハッシュコードを生成するために使用されます.では、現在多くのオブジェクト、すなわち多くのキーがあり、配列が固定されているとしたら、格納できない現象はありませんか?答えは、異なるキー値が同じ下付き文字を生成し、衝突する可能性があります(衝突がなければ、このハッシュ関数を完全ハッシュ関数と呼びます).では、衝突をどのように解決しますか?解決策は、競合は通常、外部リンクによって処理され、配列は値を保存するのではなく、リストを保存し、リストの値に対してequals()メソッドを使用してクエリします(クエリが遅いのは明らかです).私たちが格納している数値が少なく、競合が発生しない場合は、配列の下で直接位置を決定することができ、インデックスの速度がかなり速くなります(これもHashSet、HashMapインデックスが速い理由です).図を見て理解してみましょう
Stringとequals()、hashCode()について
次の文を実行すると、

String s = new String("scau");
String s1 = new String("scau");

ここでは、図に示すように、2つのStringオブジェクトを「==」で比較するとfalseが返され、2つのオブジェクトが等しくないことが明らかになります.しかしequals()で比較するとtrue(Stringがequals()メソッドを覆っていることがわかる)を返すことができる.しかし、それらは同じメモリ領域に共通にマッピングされ、hashCode()は同じ値を生成します.テストしてみましょう

public static void main(String[] args) {
    String s = new String("scau");
    String s1 = new String("scau");
    System.out.println(s.hashCode() == s1.hashCode());
}

結果:true
Bingo!