Java hashcodeメソッドってなに？

ハッシュコードって聞いたことありますか？
HashMapなどで使われていたりするんですが、地味に大事なんですよね。

んで、いきなりですが、今回はこちらの記事の続きになります。

Java ==とequalsは違う

2023.06.14

そもそもハッシュコードってなに？

一般的なハッシュコードの意味合いは、何らかのデータから、何らかの決まった計算をして、何らか得た値。ってことになりますｗ
何らかの決まった計算は、ハッシュ関数。何らか得た値はハッシュコード。もしくはハッシュ値と呼んだりします。

つまり、だから何？なわけですが。。
ある程度の決まった計算式（アルゴリズム）はあるにせよ、式自体にも値自体にもあまり意味はありませんｗ

ところが、こんな値を使うと幸せになれるケースがあります。
主な用途は検索。Javaで言えば、最初に書きましたがMapとかですね。HashMapクラスとか、Hashtableクラスなんて言うわけで。

まずは、HashMapの挙動を見てみる

HashMapから値を取り出すサンプル。ただし、キーは自作のクラス。
equalsとhashcodeメソッドをオーバーライドしてあります。

実行結果

当然ですが、「りんご」が取れます。

ところが、Keyクラスのhashcodeメソッドの部分を削除すると、こうなります。

つまり、値が取れていません。検索失敗ですね。
ちなみに、「りんご」１個だけのデータでも検索は失敗しますｗ

なぜ、hashcodeをオーバーライドしないと検索に失敗するのか？

失敗の理由は簡単で、

• HashMapは、hashcodeを使って検索している。
• equals同様に”値”(フィールド)自体のhashcodeが取得できていない。

ということです。
検索に使っている以上、”値”に関係する何らかの値（ハッシュコード）が正しくないと、正しく検索ができないってことです。

javadocを見ると、こんな感じです。

この実装は、ハッシュ関数が複数のバケットで要素を適切に分散させることを想定し、基本オペレーション(getおよびput)で一定時間の性能を提供します。
Java SE 17 API仕様 クラスHashMap(java.util.HashMap)より

つまり、ハッシュコードの使用を前提に、検索するってことですね。
javadocにもちょこっと書かれてますが、HashMapが保持しているデータは、キーのハッシュコードごとに分けて格納してあります。

んじゃ、ハッシュコードを使って、どんな検索してんの？

HashMap#get(k)で検索しようとしたときの動きは、ざっくりこんな感じ。

1. k(引数)のハッシュコードをはじく
2. はじいたハッシュコードから、格納している部屋（バケット）を見つける
3. バケットから、１つずつequalsを使って、kと同じ値のキーを見つける
4. 見つけたオブジェクトを返す

ということで、ハッシュコードが狂っていると、格納している場所と違う場所を探してしまうってことになり、見つからないわけですね。
ちなみに部屋（バケット）の数は、Java SE 17においてはデフォルトが16個だそうで。

ところで、ハッシュコードはどう計算されている？

何らかの決まった計算であれば、何でも良いわけですがｗ
それなりに分散させたいところです。

HashMapを使うときのキーって、結局のところStringが多いと思います。
というわけで、Stringの計算方法で見てみます。

この文字列のハッシュ・コードを返します。 Stringのハッシュ・コードは、次の方法で計算します。
s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]

int算術が使用されますが、ここで、s[i]は文字列のi番目の文字であり、nは文字列の長さであり、^は累乗を示します。 空の文字列のハッシュ値は0です。
Java SE 17 API仕様 String#hashCode() より

つまり、文字数分、ひたすら文字コードをもとに計算している。ってことですね。
“a”なら、aの文字コード97(0x61)。
“ab”なら、97(a:0x61) * 31 + 98(b:0x62) = 3105。
って感じ。
31は、素数だから。ってとこでしょうか。

hashcodeとequalsの関係

ここからは前回の話に少し戻りつつ、あらためて、ちょっとequalsメソッドのjavadocを確認してみます。
実は、JavadocのObject#equals()の解説に、こんな続きがあります。

APIのノート:
通常、このメソッドがオーバーライドされるたびにhashCodeメソッドをオーバーライドし、hashCodeメソッドの一般契約を維持するには、同等のオブジェクトが同等のハッシュ・コードを持つ必要があることを示します。
Java SE 17 API仕様 Object#equals(java.lang.Object) より

若干、日本語が不自由ですが意味は通じます・・・よねｗ

まず大前提ですが、hashcodeのオーバーライド有無によって、equalsメソッド自体の挙動が変わるものではありません。
ですが、今回見てきたHashMapのように、アルゴリズム上hashcodeの利用を前提にしているようなクラスからすると、話は変わってしまい・・。
hashcodeをオーバーライドしていないと正しい結果が出てこない。あるいは、たとえ正しくても本来の性能を発揮できないようなことがあるわけですね。

というわけで、原則、equalsをオーバーライドしたときは、hashcodeを一緒にオーバーライドする必要があるってことです。

けっきょく、ハッシュコードをオーバーライドするときに何を書けば良いの？

まず、javadocには、こうあります。

hashCodeの一般的な規則は次のとおりです。

Javaアプリケーションの実行中に同じオブジェクトに対して複数回呼び出された場合は常に、このオブジェクトに対するequalsの比較で使用される情報が変更されていなければ、hashCodeメソッドは常に同じ整数を返す必要があります。 ただし、この整数は同じアプリケーションの実行ごとに同じである必要はありません。
2つのオブジェクトがequalsメソッドに従って等しい場合、2つのオブジェクトのそれぞれで hashCodeメソッドを呼び出すと、同じ整数結果が生成される必要があります。
2つのオブジェクトがequalsメソッドに従って等しくない場合、2つのオブジェクトのそれぞれでhashCodeメソッドを呼び出すと、個別の整数結果が生成される必要はありません。 ただし、プログラマは、等しくないオブジェクトに対して異なる整数の結果を生成すると、ハッシュ表のパフォーマンスが向上する可能性があることに注意するようにしてください。

Java SE 17 API仕様 Object#hashCode()より

長いんで要約すると、

• オブジェクトの値が変わらない限り、同じ値を返すこと。
• equalsにおいて、A=Bならば、hashcodeで返す値もA=Bの関係が成り立つ何らかの整数。
• equalsにおいて、逆にA!=Bならば、hashcodeで返す値も（性能を考えれば）A!=Bが希望だけど、別にA=Bでも良い。

ということなんで、書くべきことは、equalsでオーバーライドした内容「比較すべき対象とその方法（≒同値性）」に合わせるってこと。
ですので、通常は一番上に書いたような感じで、比較すべき対象のフィールドのハッシュコードをそのまま利用するのが一番良いということになりますね。

ただ、javadocにあるように、極端ですが「return 0;」だけでも最悪は良いわけでｗ
とは言え、性能の観点からすればHashMapを使ってる意味は無いに等しくなりますね。

—
今回はここまでです。そのうち次回は残りのStringの件をやりますｗ